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

Question

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!

Answer 1

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.

Answer 2

Note that

$$\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}$$