How can I prove this statement by induction?

Question

I would like to prove that $2^0 + 2^{-1} + 2^{-2} +...+ 2^{-n} \leq 2$ by induction.

I got the induction basis as $2^0 \leq 2$, but I couldn't find a induction step that could help me to prove that.

Any suggestions? Thank you

Answer 1

${\bf Hint}\ \ 1 + 1/2 + 1/4+\cdots + 1/2^n\ \le\ 2,\ $ when divided by $\,2\,$

$\Rightarrow\ 1/2 + 1/4 + 1/8+\cdots + 1/2^{n+1} \le 1$

Adding $\,1\,$ to the prior equation we infer $\,P_n \Rightarrow\, P_{n+1}$

Remark $\ $ Essentially we exploited a recurrence for the expression $\,f_n$

$$ f_{n+1} = 1 + f_n/2,\quad f_0 = 1 $$

therefore $\ \color{#c00}{f_n \le 2}\,\Rightarrow\, f_{n+1} = 1+\color{#c00}{f_n}/2\, \le\, 1+\color{#c00}{2}/2\,\le\, 2$

that is $\ \ f_n \le 2\,\Rightarrow\, f_{n+1}\le 2,\ $ which is the induction step $\,P_n\Rightarrow P_{n+1}$

Answer 2

This is one of those cases where in order for induction to work, you actually need to prove something stronger. Try replacing $\leq 2$ with $=2-2^{-n}$.

Answer 3

$2^0 + 2^{-1} + 2^{-2} +... + 2^{-n} <= 2$

For the first case note that $2^0 \leq 2$ is true and also $0 \leq 2- 2^0$. In fact $2- 2^0 = 2^0$

Next notice that $2^k - 2^{k-1} = 2^{k-1}$

You can prove by induction that $2-(2^0 + 2^{-1} + 2^{-2} +...+ 2^{-n}) = 2^{-n}$

Answer 4

Base case:

$n = 0$

$2^0 = 1 < 2$. Okay.

Just for good measure a second base case:

$n = 1$

$2^0 + 2^{-1} = 1 + 1/2 < 2$. Okay.

Induction step:

Assume true for $n = k$

So $2^0 + 2^{-1} + .... + 2^{-k} \le 2$ so

$2^0 + 2^{-1} + ..... + 2^{-k} + 2^{-(k+1)} \le 2 + \frac 1{2^{k+1}}$...

Hmmm, that doesn't work. Can. I prove stronger.

Note: $2^0 = 1 = 2- \frac 1{2^0} < 2$

$2^0 + 2^1 = 1 + \frac 12 = 2 - \frac 1{2^1} < 2$

Maybe I can prov $2^0 + 2^{-1} + ..... + 2^{-n} = 2 - \frac 1{2^n} < 2$ instead.

Well, I've shown the base cases. Induction:

$n = k$

So $2^0 + 2^{-1} + .... + 2^{-k} = 2 - \frac 1{2^{k}} \le 2$ so

$2^0 + 2^{-1} + ..... + 2^{-k} + 2^{-(k+1)} = 2 -\frac 1{2^{k}} +\frac 1{2^{k+1}}=$

$2 -(\frac 1{2^{k}} -\frac 1{2^{k+1}} ) = 2 - \frac{2 - 1}{2^{k+1}} = 2 -\frac 1{2^{k+1}} < 2$

Done.

(As it's a stronger result the weaker result $2^0 + 2^{-1} + .... + 2^{-n} \le 2$ must also be true.)