# How can I prove an infinite sequence with induction

Given a infinite sequence that converges at 1:

$$\sum_{n=1}^{\infty} \frac{1}{2^n} = 1.$$

How can I formally prove this using induction?

Normally I would go about showing a base case, for some value of $$n$$, to prove this is actually right, but this seems to be misleading.

Not sure what I am missing, but any pointer as to how to engage proving inifinite sequences with induction would be much appreciate, as I have found no helpful information so far.

My point however formally is to prove with induction that the sequence when the $$\lim_{n \to \infty} \frac{1}{2^n} = 1$$.

• Presumably you meant to start with $n=1$ or have $2^i$ in the summand. And can you prove $\sum_{n=1}^N\frac1{2^n}=1-\frac1{2^N}$ by induction? – Simply Beautiful Art Sep 3 at 13:31
• @SimplyBeautifulArt I'm not completely sure I understand how you formally arrive at the $1 - \frac{1}{2^N}$. What is the $N$ in this case (or what does it represent)? I can see you set the upper-limit $\infty$ to $N$, but was is the idea behind doing so in an inifinite sequence? – ComSciStu Sep 3 at 13:59
• Can you show that it holds for $N=1$? Can you show it holds for $N=k+1$ if it holds for $N=k$? Can you deduce the limit as $N\to\infty$? – Simply Beautiful Art Sep 3 at 14:00

You can't do induction on a limit of an infinite sequence but you can on every finite sequence.

So You can prove that $$\sum\limits_{n=1}^M \frac 1{2^n} = 1-\frac 1{2^M}$$ by induction.[1]

And from that you can conclude $$\sum\limits_{n=1}^\infty \frac 1{2^n}=\lim\limits_{M\to \infty}\sum\limits_{n=1}^M \frac 1{2^n} =\lim\limits_{M\to \infty}(1-\frac 1{2^M}) =1 -\lim\limits_{M\to \infty}\frac 1{2^M}$$.

And we can prove $$\lim\limits_{M\to \infty}\frac 1{2^M}=0$$[2].

====

[1]: Base case: $$\sum\limits_{n=1}^1 \frac 1{2}^n = \frac 12 = 1 - \frac 12$$.

Inductive step:

Assume $$\sum\limits_{n=1}^k \frac 1{2^n} = 1-\frac 1{2^k}$$ then

$$\sum\limits_{n=1}^{k+1} \frac 1{2^n} = 1-\frac 1{2^k}+ \frac 1{2^{k+1}}=$$

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

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

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

[2].... seems kind of weird to jump from natural number induction to analysis of limits but...

For any $$\epsilon; 1> \epsilon > 0$$ then $$M = \frac 1\epsilon > 1$$ and $$n > \log_2 M$$ then $$2^n > M =\frac 1\epsilon$$ and $$0< \frac 1{2^n} < \epsilon$$.

• iterating over your solution-example above kinda makes sense to me. However the approximation is that the $\lim_{n \to \infty} \frac{1}{2^n} = 1$, however above you calculate this to be an approximation of 0? The [2] part don't make much sense to me, however the [1] part does. Can you perhaps elaborate on [2]? – ComSciStu Sep 3 at 17:48
• $\lim_{n\to \infty} \frac 1{2^n} = 0$ because $\frac 12, \frac 14, \frac 18,\frac 1{16}....\to 0$. But the $\lim_{n\to \infty} (1-\frac 1{2^n}) = 1$ because $\frac 12, \frac 34, \frac 78, \frac {15}{16} ...\to 1$. This follows as $\lim (1-\frac 1{2^n}) = 1 - \lim \frac 1{2^n}$ (if it exists). Proving $\lim \frac 1{2^n} = 0$ is a standard exercise. The definition of $\lim_{n\to\infty} a_n = L$ is that for any $\epsilon > 0$, we can find an $M$ so that $n>M\implies|a_n-L|<\epsilon$. And if $n>\log_2(\frac 1\epsilon)$ then $2^n>\frac1\epsilon$ and $|0-\frac 1{2^n}|<\epsilon$. – fleablood Sep 3 at 19:23
• Or we can prove $\lim (1 -\frac 1{2^n}) = 1$ directly. If $\epsilon > 0$ then whenever $n>\log_2(\frac 1\epsilon)$ then $2^n>\frac 1\epsilon$ and $0<\frac1{2^n} < \epsilon$. So $|(1-\frac 1{2^n})-1|=|-\frac 1{2^n}|=\frac 1{2^n}<\epsilon$. So $\lim_{n\to \infty}(1-\frac 1{2^n}) = 1$. – fleablood Sep 3 at 19:29

In general, $$\sum_{k=0}^n r^k =\frac{1-r^{n+1}}{1-r},$$ which can be proved by induction, shows that the limit is $$1/(1-r)$$ if $$r^{n+1} \to 0$$.

• How would I translate this to the sequence listed above? In that case all I have is the actual limit of 1, for the sequence of $\frac{1}{2^n}$. What I want is to prove that the sequence sum converges to 1. – ComSciStu Sep 3 at 17:16
• Set $r=1/2$. Then, according to the formula, the sum after $n$ terms (starting at 0) is $(1-1/2^n)/(1-1/2) = 2-1/2^{n-1}$. If you start at $n=1$, the sum is $1 -1/2^{n-1}$. – marty cohen Sep 3 at 18:59

First of all as $$n$$ varies sum will vary, therefore you can not prove by induction that for every $$n$$ sum is 1. But instead you can prove (by induction) $$r+r^{2}+...+r^{n}=\frac{r(1-r^{n})}{1-r} .$$ For $$r=\frac{1}{2}$$, sum is $$1-\frac{1}{2^{n}}$$, so infinite sum is $$1$$. To find the sum of infinite series, we find the limit of sequence of partial sums, induction is not a good idea.