TAOCP 1.2.7 Exercise 13
We prove the identity \sum_{k=1}^{n}\frac{x^k}{k} = H_n + \sum_{k=1}^{n}\binom{n}{k}\frac{(x-1)^k}{k}.
Section 1.2.7: Harmonic Numbers
Exercise 13. [M22] Prove the identity
$$ \sum_{k=1}^{n}\frac{x^k}{k} = H_n + \sum_{k=1}^{n}\binom{n}{k}\frac{(x-1)^k}{k}. $$
Verified: no
Solve time: -
Solution
We prove the identity
$$ \sum_{k=1}^{n}\frac{x^k}{k} = H_n + \sum_{k=1}^{n}\binom{n}{k}\frac{(x-1)^k}{k}. $$
Consider the binomial expansion of $x^k$ in terms of $(x-1)$:
$$ x^k = \bigl(1 + (x-1)\bigr)^k = \sum_{j=0}^{k}\binom{k}{j}(x-1)^j. $$
Dividing both sides by $k$ and summing over $k$ from $1$ to $n$ gives
$$ \sum_{k=1}^{n}\frac{x^k}{k} = \sum_{k=1}^{n}\frac{1}{k}\sum_{j=0}^{k}\binom{k}{j}(x-1)^j = \sum_{k=1}^{n}\frac{1}{k} + \sum_{k=1}^{n}\sum_{j=1}^{k}\frac{\binom{k}{j}}{k}(x-1)^j. $$
The first term is $H_n$. In the second term, interchange the order of summation over $k$ and $j$:
$$ \sum_{k=1}^{n}\sum_{j=1}^{k}\frac{\binom{k}{j}}{k}(x-1)^j = \sum_{j=1}^{n}(x-1)^j \sum_{k=j}^{n}\frac{\binom{k}{j}}{k}. $$
By the identity $\frac{\binom{k}{j}}{k} = \frac{\binom{k-1}{j-1}}{j}$, valid for $1 \le j \le k$, we obtain
$$ \sum_{k=j}^{n}\frac{\binom{k}{j}}{k} = \frac{1}{j}\sum_{k=j}^{n}\binom{k-1}{j-1}. $$
Shifting the summation index by $i = k-1$, we have
$$ \sum_{k=j}^{n}\binom{k-1}{j-1} = \sum_{i=j-1}^{n-1}\binom{i}{j-1} = \binom{n}{j}, $$
by the well-known binomial identity $\sum_{i=m}^{N}\binom{i}{m} = \binom{N+1}{m+1} - \binom{m}{m+1} = \binom{N+1}{m+1}$, and since $\binom{m}{m+1} = 0$. Therefore
$$ \sum_{k=j}^{n}\frac{\binom{k}{j}}{k} = \frac{1}{j}\binom{n}{j}. $$
Substituting back, we obtain
$$ \sum_{k=1}^{n}\sum_{j=1}^{k}\frac{\binom{k}{j}}{k}(x-1)^j = \sum_{j=1}^{n}\binom{n}{j}\frac{(x-1)^j}{j}. $$
Combining this with the first term $H_n$, the desired identity follows:
$$ \sum_{k=1}^{n}\frac{x^k}{k} = H_n + \sum_{k=1}^{n}\binom{n}{k}\frac{(x-1)^k}{k}. $$
This completes the proof.
∎