# Harmonic number identity $\sum_{k=1}^{n}H_k=(n+1)(H_{n+1}-1)$

Prove using generating functions that for Harmonic numbers $H_n= \sum_{j=1}^{n}\frac{1}{j}$ $$\sum_{k=1}^{n}H_k=(n+1)(H_{n+1}-1) (*)$$
The generating function for harmonic numbers is $$\sum_{n \in \mathbb N}H_n x^n =\frac{-ln(1-x)}{1-x}$$
I'm guessing we convert LHS of $(*)$ to power series, change limits of the sums, apply the generating funtion and then extract coefficients.
$$\sum_{n \in \mathbb N} \sum_{k=1}^{n}H_k x^n$$ I'm confused about how to change the limits of this sum. Please help!

• Have a look at the first lines of this answer for a simple approach by summation by parts. – Jack D'Aurizio Nov 19 '17 at 0:14

Since you know that (by defining $H_0$ as $0$) $$\sum_{n\geq 0}H_n x^n = \frac{-\log(1-x)}{1-x}=f(x)$$ by multiplying both sides by $\frac{1}{1-x}$ you have: $$\sum_{n\geq 0}\left(\sum_{k=0}^{n}H_k\right)x^n = \frac{-\log(1-x)}{(1-x)^2}=g(x).$$ We may notice that $f'(x)=\frac{1}{(1-x)^2}+g(x)$.
Since $\frac{1}{(1-x)^2}=\sum_{n\geq 0}(n+1)x^n$, the previous DE implies $$\sum_{k=0}^{n}H_k = (n+1)(H_{n+1}-1)$$ as wanted.
\begin{align} \sum_{k=1}^NH_k&=\sum_{k=1}^N\sum_{\ell=1}^k\frac1\ell\\\\ &=\sum_{\ell=1}^n\frac1\ell\sum_{k=\ell}^n(1)\\\\ &=\sum_{\ell=1}^n\frac1\ell(n+1-\ell)\\\\ &=(n+1)\sum_{\ell=1}^n \frac1\ell -n\\\\ &=(n+1)\sum_{\ell=1}^{n+1}\frac1\ell -(n+1)\\\\ &=(n+1)\left(H_{n+1}-1\right) \end{align}
Let $$S_n$$ denotes $$\displaystyle\sum_{k=1}^n H_k$$ and by applying Abel's summation:
$$\displaystyle\sum_{k=1}^n a_k b_k=A_nb_{n}+\sum_{k=1}^{n-1}A_k\left(b_k-b_{k+1}\right)\$$ where $$\ \displaystyle A_n=\sum_{i=1}^n a_i\$$ and letting $$\ \displaystyle a_k=1$$ , $$\ \displaystyle b_k=H_k\$$, we get, \begin{align} S_n&=\left(\sum_{i=1}^n1\right)H_{n}+\sum_{k=1}^{n-1}\left(\sum_{i=1}^k1\right)\left(H_k-H_{k+1}\right)\\ &=nH_{n}+\sum_{k=1}^{n-1}(k)\left(-\frac1{k+1}\right), \quad\color{blue}{\sum_{k=1}^{n-1}\frac{k}{k+1}=\sum_{k=0}^{n-1}\frac{k}{k+1}}\\ &=nH_{n}-\sum_{k=1}^n\frac{k-1}{k}\\ &=nH_{n}-\sum_{k=1}^n1+\sum_{k=1}^n\frac{1}{k}\\ &=nH_n-n+H_n\\ &=H_n(n+1)-n\\ &=\left(H_{n+1}-\frac1{n+1}\right)(n+1)-n\\ &=(n+1)(H_{n+1}-1) \end{align}