Exercise from discuss.com.hk (2)

Problem:

$\lim\limits_{n \to \infty}\sum\limits_{k = 1}^{n - 1}\frac{k}{2^k(n - k)}$

Solution:

Let $p = n - k$, so we have

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

Notice the first term look very much like the previous post, so we will use the same trick to solve the problem, let $L(n) = \frac{n}{2^n}\sum\limits_{p = 1}^{n - 1}\frac{2^p}{ p}$

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

Again, assume the limit exists, taking limits on both sides, we get

$\begin{eqnarray} L &=& \frac{1}{2}L + \frac{1}{2} \\ 2L &=& L + 1 \\ L &=& 1 \end{eqnarray}$

Therefore the overall solution is simply 1 - 1 = 0.