Prove that $\sum_{i=1}^n \frac{i}{2^i} < 2 $ by bounding term-to-term with a geometric series.
I thought you'd use $\sum_{i=1}^n (\frac{1}{2})^i $ = 2 somehow but the inequality is not inclusive to 2. Also, it's supposed to be done term-to-term.
Could anyone explain how to do it by bounding? Thanks.
On
$$\begin{array}{lcl} \displaystyle \sum_{i = 1}^n \dfrac{i}{2^i} & = & \displaystyle \sum_{i = 1}^n \sum_{j = 1}^i \dfrac{1}{2^i} \\[3mm] & = & \displaystyle \sum_{j = 1}^n \sum_{i = j}^n \dfrac{1}{2^i} \\[3mm] & = & \displaystyle \sum_{j = 1}^n \dfrac{\dfrac{1}{2^j} - \dfrac{1}{2^{n + 1}}}{1 - \dfrac{1}{2}} \\[3mm] & = & \displaystyle \sum_{j = 1}^n \left(\dfrac{1}{2^{j - 1}} - \dfrac{1}{2^n}\right) \\[3mm] & = & \displaystyle \sum_{j = 0}^{n - 1} \dfrac{1}{2^j} - \dfrac{n}{2^n} \\[3mm] & = & \displaystyle \dfrac{1 - \dfrac{1}{2^n}}{1 - \dfrac{1}{2}} - \dfrac{n}{2^n} \\[3mm] & = & \displaystyle 2 - \dfrac{1}{2^{n - 1}} - \dfrac{n}{2^n} \\[3mm] & = & \displaystyle 2 - \dfrac{n + 2}{2^n} \\[3mm] & < & \displaystyle 2 \end{array}$$
$\sum_{i=1}^n\frac{i}{2^i}=\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\frac{4}{16}+...$
$x_0=0, x_{n+1}=x_n+\frac{n+1}{2^{n+1}}$
$x_{n+1}-x_n=\frac{n+1}{2^{n+1}}$
$x_{n+2}-x_{n+1}=\frac{n+2}{2^{n+2}}$
$\frac{x_{n+2}-x_{n+1}}{x_{n+1}-x_n}=\frac{n+2}{2^{n+2}}\frac{2^{n+1}}{n+1}=\frac{1}{2}\frac{n+2}{n+1}=\frac{1}{2}(1+\frac{1}{n+1})$
So, the ratio between the difference of consecutive terms when $n\ge2$ is always $\le\frac{2}{3}$. The first term in the series starting there is 1/2, so the series is bounded above by $\frac{1/2}{1-2/3}=3/2.$ Add in the first term and we get $\sum_{i=1}^n\frac{i}{2^i}<2$.