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$.

  • 6
    $\begingroup$ 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? $\endgroup$ – Simply Beautiful Art Sep 3 at 13:31
  • $\begingroup$ @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? $\endgroup$ – ComSciStu Sep 3 at 13:59
  • $\begingroup$ 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$? $\endgroup$ – 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$.

  • $\begingroup$ 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]? $\endgroup$ – ComSciStu Sep 3 at 17:48
  • $\begingroup$ $\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$. $\endgroup$ – fleablood Sep 3 at 19:23
  • $\begingroup$ 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$. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – ComSciStu Sep 3 at 17:16
  • $\begingroup$ 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}$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.