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.
 A: Hint: If $a_n=1/2+2/2^2+...+n/2^n$ then $$a_{n+1}=\left(\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots+\frac{1}{2^{n+1}}\right)+\frac{1}{2}a_n$$
So $a_{n+1}<1+\frac{1}{2}a_n$.
A: Suppose 
$\sum_\limits{k=1}^{\infty} k r^k$ converges  (and it does if r<1)
$S - rS = \sum_\limits{k=1}^{\infty} (n+1 - n) r^k = \sum_\limits{k=1}^{\infty}  r^k\\
S = \frac {r}{(1-r)^2}$
$\sum_\limits{k=1}^{\infty} k (\frac 12)^k = \frac {\frac 12}{(1-\frac 12)^2} = 2$
$\sum_\limits{k=1}^{n} k (\frac 12)^k < \sum_\limits{k=1}^{\infty} k (\frac 12)^k$
But that is not a proof by induction, is it?
Rather than prove that 
$a_n = \frac 12 + \frac 24 \cdots + \frac {n}{2^n} < 2$ it will be easier if we try to prove something more restrictive.  
Proposition:
$a_n = \frac 12 + \frac 24 \cdots + \frac {n}{2^n} = 2 - \frac {n+2}{2^n}$
Proof by induction:
base case:
n = 1
$\frac 12  = 2 - \frac {3}{2}$
Inductive hypothesis:
Suppose $a_n = \frac 12 + \frac 24 \cdots + \frac {n}{2^n} = 2 - \frac {n+2}{2^n}$
we will need to show:
$a_{n+1} <2-\frac {n+3}{2^{n+1}}$
$a_{n+1} = a_n + \frac {n+1}{2^{n+1}}\\
a_{n+1} = 2 - \frac {n+2}{2^n} + \frac {n+1}{2^{n+1}}$
Based on the inductive hypothesis
$a_{n+1} = $$2 - \frac {2(n+2)-(n+1)}{2^{n+1}}\\
2 - \frac {n+3}{2^{n+1}}\\
$
QED
A: 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.
