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

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!!
