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