Show that $\sum_{i=1}^n \frac{i}{2^i}<2$

Question

My task is to show: $$\sum_{i=1}^n \frac{i}{2^i} < 2$$ There is also a hint: try to bound this sum term by term with a geometric progression.
I have tried following: $$\sum_{i=1}^n \frac{1}{2^i} = \sum_{i=0}^n \frac{1}{2^i} - 1 = \frac{1 - (\frac{1}{2})^{n+1}}{1 - \frac{1}{2}} - 1 = 1 - (\frac{1}{2})^n $$ and $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$ But I'm not sure if I am thinking about it the right way. I can't progress from this point further. Problem looks quite simple and basic, but I don't know 'the smart trick' there.

Answer 1

Transforming this seems to be the way to go. Note $$\sum_{i=1}^n \frac{i}{2^i} =\sum_{k=1}^{n}\left(\sum_{i=k}^{n}\frac{1}{2^i}\right)$$

As each term, $\frac{1}{2^i}$ is added $i$ times. Now, using the formula for the sum of geometric progressions, we have $$\sum_{i=k}^{n}\frac{1}{2^i}=\frac{1}{2^{k-1}}-\frac{1}{2^n}<\frac{1}{2^{k-1}}$$

So the sum becomes $$\sum_{k=1}^{n}\left(\sum_{i=k}^{n}\frac{1}{2^i}\right)<\sum_{k=1}^{n}\frac{1}{2^{k-1}}=2-\frac{1}{2^{n-1}}<2 $$

Answer 2

$$S:=\frac01+\frac12+\frac24+\frac38+\cdots\frac{n-1}{2^{n-1}}+\frac n{2^n}=\\ \frac12\left(\frac{0+1}1+\frac{1+1}2+\frac{2+1}4+\cdots\frac{n-2+1}{2^{n-2}}+\frac {n-1+1}{2^{n-1}}\right).$$

Then

$$2S-S=\frac11+\frac12+\frac14+\cdots\frac1{2^{n-2}}+\frac1{2^{n-1}}-\frac n{2^n}<2.$$

---

This result makes is difficult to avoid computing the sum as a by-product,

$$S=2-\frac1{2^{n-1}}-\frac n{2^n}.$$

Answer 3

Let $$f(x):=\sum_{i=1}^n x^i=x\frac{1-x^n}{1-x}<\frac x{1-x}=g(x)$$ for $x$ in $(0,1)$.

Then by differentiation, noting that $f(0)=g(0)=0$, the requested sum verifies

$$\sum_{i=1}^n\frac i{2^i}=\left.x\sum_{i=1}^n ix^{i-1}\right|_{x=1/2}=\frac12f'\left(\frac12\right)<\left.xg'(x)\right|_{x=1/2}=\frac12\frac1{\left(1-\dfrac12\right)^2}=2.$$