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!
-
$\begingroup$ Have a look at the first lines of this answer for a simple approach by summation by parts. $\endgroup$– Jack D'AurizioNov 19, 2017 at 0:14
4 Answers
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.
-
$\begingroup$ @MarkViola: yes, of course, I am going to add it to the answer, thanks Mark. $\endgroup$ 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)}$