3

I want to prove that $$\frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^n} \leq 1$$ only by induction!

I check for the first one, $\frac12 \leq 1 $ correct.
Then I assume for $n=k$ : $$\frac12 + \frac14 + \dots + \frac{1}{2^k} \leq 1$$ And Try and prove for $n=k+1$

$$\frac12 + \frac14 + \dots + \frac{1}{2^k} + \frac{1}{2^{k+1}} \leq 1$$ But I know that $$\frac12 + \frac14 + \dots + \frac{1}{2^k} \leq \frac12 + \frac14 + \dots + \frac{1}{2^k} + \frac{1}{2^{k+1}} \leq 1$$ and so:

But I am stuck, this tells me that the sum for $n=k+1$ is always $1$ , not $S \leq 1$ I am so confused, because I can't use the geometric series sum formula.. any help would be appreciated!

CSch of x
  • 1

3 Answers3

3

$\frac12 + \frac14 + \dots + \frac{1}{2^k} + \frac{1}{2^{k+1}} \leq 1 \iff \frac14 + \dots + \frac{1}{2^k} + \frac{1}{2^{k+1}} \leq \frac12 \iff \frac12 + \dots + \frac{1}{2^{k-1}} + \frac{1}{2^{k}} \leq 1$.

The last step is multiplying by $2$.

2

Hint : Prove the following stronger hypothesis induction : $$\frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^n} = 1 - \frac{1}{2^n}$$

TheSilverDoe
  • 29,720
1

We can instead try to prove the following

$$\frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^n} \leq 1-\frac1{2^n}\le 1$$

then the induction step becomes

$$\frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^n}+ \frac{1}{2^{n+1}} \le 1-\frac1{2^n}+ \frac{1}{2^{n+1}}= 1-\frac1{2^n}\left(1- \frac{1}{2}\right)=1-\frac1{2^{n+1}}$$

and we are done.

user
  • 154,566
  • Gio's proof does not count as induction? (I am curious) – CSch of x Sep 23 '20 at 14:15
  • @StackOMeow Indeed it doesn't seem a classical proof by induction but it contains the induction step $P(k) \implies P(k+1)$ then I think we can consider it fine. – user Sep 23 '20 at 14:24
  • Not new: https://math.stackexchange.com/a/1448629/42969. – Martin R Sep 23 '20 at 15:28
  • @MartinR Yes, it is very similar, indeed my idea was use inequality. User TheSilverDoe used the same idea with equality. – user Sep 23 '20 at 15:42