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!
 A: 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}$$
A: 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.
A: 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}
A: Let's denote $\Delta f(x) = f(x+1) - f(x), \ $ then $\sum\limits_{a \le x < b} \Delta f(x) = f(b) - f(a)$ and $\sum\limits_{a \le x < b} u(x) \Delta v(x) = \left . u(x) v(x) \ \right|_{a}^{b} - \sum\limits_{a \le x < b} v(x+1) \Delta u(x)$
Let's consider $\sum\limits_{1 \le x < n+1} H_{x}$, and let's denote $u(x) = H_{x}, \ \Delta v(x) = 1, \text{then} \ \Delta u(x) = \frac{1}{x+1}, v(x) = x$.
So, we have: $\sum\limits_{1 \le x < n+1} H_{x} = \left . x \cdot H_{x} \right|_{1}^{n+1} - \sum\limits_{1 \le x < n+1} \frac{x+1}{x+1} = (n+1) \cdot H_{n+1} - 1 \cdot H_{1} - n = \boxed{(n+1)H_{n+1} - (n+1)}$
