Exercise from discuss.com.hk (1)

Problem:

$\lim\limits_{n \to \infty} \frac{n}{2^n}\sum\limits_{k = 0}^{n}\frac{2^k}{k}$.

Solution:

Let $L(n) = \frac{n}{2^n}\sum\limits_{k = 0}^{n}\frac{2^n}{n}$

$\begin{eqnarray} & & L(n + 1) \\ &=& \frac{n + 1}{2^{n + 1}}\sum\limits_{k = 0}^{n + 1}\frac{2^k}{k} \\ &=& \frac{n + 1}{2^{n + 1}}\left(\sum\limits_{k = 0}^{n}\frac{2^k}{k} + \frac{2^{n + 1}}{n + 1}\right) \\ &=& \frac{n + 1}{2^{n + 1}}\sum\limits_{k = 0}^{n}\frac{2^k}{k} + 1 \\ &=& \frac{n + 1}{2^{n + 1}}\frac{2^n}{n}\frac{n}{2^n}\sum\limits_{k = 0}^{n}\frac{2^k}{k} + 1 \\ &=& \frac{n + 1}{2^{n + 1}}\frac{2^n}{n}L(n) + 1 \\ &=& \frac{n + 1}{2n}L(n) + 1 \end{eqnarray}$

Assuming we know that the limit exists, we can simply take limits on both sides to get:

$L = \frac{1}{2}L + 1$

That gives the easy answer $L = 2$.