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

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