<s>[INST] Prove $1/2^1 + 2/2^2 +....+ n/2^n < 2$ using induction This is another problem with induction that I'm sure requires some "thinking outside the box" which is something I cannot apply with my way of solving these problems.
I need to now how I can complete the induction step and I need a solution using induction.
 [/INST] To use straight induction:
The basis is trivial: When $n=1$,
$$\frac1{2^1} = \frac12 < 1$$
Now suppose that for some natural number $n$,
$$\frac1{2^1}+\frac2{2^2}+\cdots+\frac{n}{2^n} < 2
$$
Then we can put all those terms over the same denominator $2^n$ to get, on the left hand side $\frac{k}{2^n}$ with $k\in\Bbb N$. Since this is less than $2$, 
$$\frac1{2^1}+\frac2{2^2}+\cdots+\frac{n}{2^n} \leq 2 - \frac1{2^n}$$
Then 
$$
\frac12\left(\frac1{2^1}+\frac2{2^n}+\cdots+\frac{n}{2^n} \right)< \frac12\left(2 - \frac1{2^n}\right) \\
\frac1{2^2}+\frac2{2^3}+\cdots+\frac{n}{2^{n+1}} \leq 1 - \frac1{2^{n+1}} 
$$
Now add to both sides:
$$
\frac1{2^1}+\frac1{2^n}+\cdots+\frac{1}{2^n}+\frac{1}{2^{n+1}} = 1-\frac{1}{2^{n+1}} \\
+\left[\frac1{2^2}+\frac2{2^3}+\cdots+\frac{n-1}{2^n}+\frac{n}{2^{n+1}}  \leq 1 - \frac1{2^{n+1}}\right]\\
$$ to get $$
\frac1{2^1}+\frac2{2^2}+\cdots+\frac{n}{2^n}+\frac{n+1}{2^{n+1}} \leq 2-\frac1{2^n} < 2
$$
which establishes induction.
</s>