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'Aurizio Nov 19 '17 at 0:14

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$ – Jack D'Aurizio Nov 19 '17 at 0:42

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


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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.