Question

Prove the following by induction. In each case, n is apositive integer.
2^n ≤ 2^n+1 - 2^n-1 -1.

Answer 1

Answer with explanation:

We are asked to prove by the method of mathematical induction that:

$2^n\leq 2^{n+1}-2^{n-1}-1$

where n is a positive integer.

• Let us take n=1

then we have:

$2^1\leq 2^{1+1}-2^{1-1}-1\\\\i.e.\\\\2\leq 2^2-2^{0}-1\\\\i.e.\\2\leq 4-1-1\\\\i.e.\\\\2\leq 4-2\\\\i.e.\\\\2\leq 2$

Hence, the result is true for n=1.

• Let us assume that the result is true for n=k

i.e.

$2^k\leq 2^{k+1}-2^{k-1}-1$

• Now, we have to prove the result for n=k+1

i.e.

To prove:  $2^{k+1}\leq 2^{(k+1)+1}-2^{(k+1)-1}-1$

Let us take n=k+1

Hence, we have:

$2^{k+1}=2^k\cdot 2\\\\i.e.\\\\2^{k+1}\leq 2\cdot (2^{k+1}-2^{k-1}-1)$

( Since, the result was true for n=k )

Hence, we have:

$2^{k+1}\leq 2^{k+1}\cdot 2-2^{k-1}\cdot 2-2\cdot 1\\\\i.e.\\\\2^{k+1}\leq 2^{(k+1)+1}-2^{k-1+1}-2\\\\i.e.\\\\2^{k+1}\leq 2^{(k+1)+1}-2^{(k+1)-1}-2$

Also, we know that:

$-2<-1\\\\i.e.\\\\2^{(k+1)+1}-2^{(k+1)-1}-2<2^{(k+1)+1}-2^{(k+1)-1}-1$

(

Since, for n=k+1 being a positive integer we have:

$2^{(k+1)+1}-2^{(k+1)-1}>0$  )

Hence, we have finally,

$2^{k+1}\leq 2^{(k+1)+1}-2^{(k+1)-1}-1$

Hence, the result holds true for n=k+1

Hence, we may infer that the result is true for all n belonging to positive integer.

i.e.

$2^n\leq 2^{n+1}-2^{n-1}-1$  where n is a positive integer.

Answer 2

Answer:

We rewrite the inequality as follows:

$2^n \leq 2^{n+1} - 2^{n-1} - 1\\1 \leq 2^{n+1} - 2^{n} - 2^{n-1}\\1 \leq 4\cdot 2^{n-2} - 2 \cdot 2^{n-1} - 2^{n-1}\\1 \leq (4-2-1) \cdot 2^{n-2}\\1 \leq 2^{n-2}$

Which is true because n was given to be a positive integer.