# 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. Nov 19, 2017 at 0:14

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}

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.

• @MarkViola: yes, of course, I am going to add it to the answer, thanks Mark. Nov 19, 2017 at 0:42

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}

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