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}^{n+1}\frac1\ell -(n+1)\\\\ &=(n+1)\left(H_{n+1}-1\right) \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.