Proof by induction, $1/2 + ... + n/2^n < 2$

Question

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

Answer 1

Hint: $$ \begin{align} \frac{1}{2^1} + \frac{2}{2^2} + ... +\frac{k-1}{2^{k-1}} + \frac{k}{2^k} + \frac{k+1}{2^{k+1}} &=\qquad\;\;\frac12\Big(\frac{1}{2^1} + \frac{2}{2^2} + \dots +\frac{k-1}{2^{k-1}} + \frac{k}{2^k}\Big) \\ &\quad+\Big(\frac{1}{2^1} + \frac{1}{2^2}+\frac1{2^3} + \dots + \;\;\frac{1}{2^k}\;\;+\frac1{2^{k+1}}\Big) \end{align} $$ On the right hand side, the first summand corresponds to the induction hypothesis, and you can bound the second summand by...

Answer 2

You can try to do the following: write

$$ \frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{k}{2^k} + \frac{k+1}{2^{k+1}} = $$ $$ \frac{1}{2} + \frac{1}{2^2} + \cdots + \frac{1}{2^k} + \frac{1}{2^{k+1}} + $$ $$ \frac{1}{2}\left(\frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{k}{2^k}\right).$$

Use that the first summand is bounded by $1$, and, by induction hypothesis, the second one is strictly less than $\frac{1}{2} \cdot 2.$ This finishes the inductive step.

Answer 3

Hint:

It's a sum of an arithmetico-geometric progression:

$$S_{n}={\frac {a-(a+nd)\,r^{n}}{1-r}}+{\frac {dr\,(1-r^{n})}{(1-r)^{2}}}$$

Here $d$ is the common difference, $r$ is the common ratio, $n$ denotes the number of terms and $a$ is the first term.

Answer 4

In that case a possible trick to use induction is to prove the stronger condition

$$\frac{1}{2} + \frac{2}{2^2} + \ldots +\frac{n-1}{2^{n-1}} + \frac{n}{2^{n}} <2-\frac{n+1}{2^{n-1}}<2$$

and the induction step becomes

$$\frac{1}{2} + \frac{2}{2^2} + \ldots + \frac{n}{2^n} + \frac{n+1}{2^{n+1}}\stackrel{Ind. Hyp.}<2-\frac{n+1}{2^{n-1}}+ \frac{n+1}{2^{n+1}}\stackrel{?}<2-\frac{n+2}{2^{n}}$$

and the last inequality holds indeed

$$2-\frac{n+1}{2^{n-1}}+ \frac{n+1}{2^{n+1}}\stackrel{?}<2-\frac{n+2}{2^{n}}$$

$$\frac{n+1}{2^{n-1}}- \frac{n+1}{2^{n+1}}\stackrel{?}>\frac{n+2}{2^{n}}$$

$$4(n+1)-(n+1)\stackrel{?}> 2(n+2)$$

$$3n+3\stackrel{?}>2n+4$$

wich is true for $n>1$.

Answer 5

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