Induction proof: $\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +...+\frac{n}{2^n}$ $<2$ 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
 A: 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!!
A: 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.
A: 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.$$ 
