<s>[INST] Proof by induction, $1/2 + ... + n/2^n < 2$ So I'm having trouble with proving this homework question by induction. 
$$
\frac{1}{2^1} + \frac{2}{2^2} + ... +\frac{n-1}{2^{n-1}} + \frac{n}{2^n} <2
$$
I know how to prove that the series converges to 2 (using things like the ratio method), but actually using induction is where I get confused.
Base case is easy, n=1.
$$
\frac{1}{2^1}<2
$$
Induction case we assume that
$$
\frac{1}{2^1} + \frac{2}{2^2} + ... +\frac{k-1}{2^{k-1}} + \frac{k}{2^k} <2
$$
Then we get to fun old induction. How do I show that
$$
\frac{1}{2^1} + \frac{2}{2^2} + ... +\frac{k-1}{2^{k-1}} + \frac{k}{2^k} + \frac{k+1}{2^{k+1}} <2 ?
$$
 [/INST] Denote $$S_n=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots+\frac{n}{2^n}.\tag1$$Then $$\frac{1}{2}S_n=\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\cdots+\frac{n}{2^{n+1}}.\tag2$$Thus by $(1)-(2)$, we obtain $$\frac{1}{2}S_n=\left(\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots+\frac{1}{2^n}\right)-\frac{n}{2^{n+1}}< 1-\frac{n}{2^{n+1}}<1,$$ which implies $$S_n < 2.$$
</s>