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

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

Answer 2

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 3

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}

Answer 4

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