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.