Induction proof: $\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +...+\frac{n}{2^n}$ $<2$

Question

Prove by induction the following. $$\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +\dots+\frac{n}{2^n}<2.$$

Caveat: The $<$ will be hard to work with directly. Instead, the equation above can be written in the form,

$$\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +\dots+\frac{n}{2^n}=2-\text{something}.$$

First, find the "something" and then use that form of the equation to prove the assertion.

I can't seem to figure out the form that this equation can be written as. Also, once I find the form how would I do the proof. I understand it involves using a Basic Step and an Induction Step

Answer 1

Show that $$\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +\dots+\frac{n}{2^n}\leq 2-\frac{An+B}{2^n}$$ for some $A,B\geq 0$. Then the base case is satisfied if $$\frac{1}{2}\leq 2-\frac{A+B}{2}$$ that is $A+B\leq 3$. The induction step works if for all $n\geq 1$, $$2-\frac{An+B}{2^n}+\frac{n+1}{2^{n+1}}\leq2-\frac{A(n+1)+B}{2^{n+1}},$$ that is $$n+1\leq (2An+2B)-(A(n+1)+B)=An+B-A.$$ It follows that $A=1$ and $B=2$ and we may conclude that:

For all $n\geq 1$, $$\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +\dots+\frac{n}{2^n}\leq 2-\frac{n+2}{2^n}$$

P.S. Looking back to the the induction proof steps it is easy to realize that the above inequality is actually an equality!!

Answer 2

This question is circling in rounds.

Because, as everybody knows, the sum tends to $2$ so that in

$$\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +...+\frac{n}{2^n}+ r_n=2,$$ the expression of $r_n$ must be exact!

If you try with an inequality such as

$$\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +...+\frac{n}{2^n}+ r_n<2,$$

induction will require $r_n\ge\dfrac{n+1}{2^{n+1}}$ to absorb the next term, but if $r_n$ is not tight sooner or later the sum with the remainder will exceed $2$.

---

Robert Z. found a nice workaround.

Answer 3

Let the sum of the $n$ first terms be $S_n$. We have the recurrence

$$S_{n+1}=S_n+\frac{n+1}{2^{n+1}}$$ or

$$2^{n+1}S_{n+1}=2\cdot2^nS_n+n+1.$$

This hints the change of variable that leads to

$$R_{n+1}=2R_n+n+1.$$

This is a linear recurrence which we will solve a usual:

• homogeneous part, $R_{n+1}=2R_n$, so that $R_n=R_12^{n-1}$.

• particular solution found by indeterminate coefficients, using a linear ansatz: $-n-2$.

Now, using the initial condition $R_1=1$,

$$S_n=2-\frac{n+2}{2^n}.$$

---

We can complete the inductive proof:

$$S_1=\frac12=2-\frac{1+2}{2^1}<2,$$

$$S_n=2-\frac{n+2}{2^n}<2\implies S_{n+1}=2-\frac{n+2}{2^n}+\frac{n+1}{2^{n+1}}=2-\frac{(n+1)+2}{2^{n+1}}<2.$$