$\sum_{k=1}^nH_k = (n+1)H_n-n$. Why?

Question

This is motivated by my answer to this question.

The Wikipedia entry on harmonic numbers gives the following identity:

$$ \sum_{k=1}^nH_k=(n+1)H_n-n $$

Why is this?

Note that I don't just want a proof of this fact (It's very easily done by induction, for example). Instead, I want to know if anyone's got a really nice interpretation of this result: a very simple way to show not just that this relation is true, but why it is true.

Has anyone got a way of showing that this identity is not just true, but obvious?

Answer 1

I suck at making pictures, but I try nevertheless. Write $n+1$ rows of the sum $H_n$:

$$\begin{matrix} 1 & \frac12 & \frac13 & \dotsb & \frac1n\\ \overline{1\Big\vert} & \frac12 & \frac13 & \dotsb & \frac1n\\ 1 & \overline{\frac12\Big\vert} & \frac13 & \dotsb & \frac1n\\ 1 & \frac12 & \overline{\frac13\Big\vert}\\ \vdots & & &\ddots & \vdots\\ 1 & \frac12 &\frac13 & \dotsb & \overline{\frac1n\Big\vert} \end{matrix}$$

The total sum is obviously $(n+1)H_n$. The part below the diagonal is obviously $\sum\limits_{k=1}^n H_k$. The part above (and including) the diagonal is obviously $\sum_{k=1}^n k\cdot\frac1k = n$.

It boils down of course to the same argument as Raymond Manzoni gave, but maybe the picture makes it even more obvious.

Answer 2

Consider the different terms $\frac 1k$. Once you added the $n$ terms $\,H_k\,$ you'll have : \begin{array} {lcc} &n &\text{terms} &1\\ &n-1&\text{terms}&\frac 12\\ &\cdots\\ &n+1-k&\text{terms}&\frac 1k\\ &\cdots\\ &2&\text{terms} &\frac 1{n-1}\\ &1&\text{term}&\frac 1n\\ \end{array}

The sum will be $$\sum_{k=1}^nH_k=\sum_{k=1}^n \frac{n+1-k}k=(n+1)H_n-n$$

Answer 3

$$ \begin{align} \sum_{k=1}^nH_k &=\sum_{k=1}^n\sum_{j=1}^k\frac1j&&\text{expand }H_k\\ &=\sum_{j=1}^n\sum_{k=j}^n\frac1j&&\begin{array}{}\text{change order of summation}\\\text{where }1\le j\le k\le n\end{array}\\ &=\sum_{j=1}^n\frac{n-j+1}{j}&&\begin{array}{}\text{each term is constant over}\\\text{the inner summation}\end{array}\\ &=(n+1)\sum_{j=1}^n\frac1j-\sum_{j=1}^n1&&\text{separate terms}\\[6pt] &=(n+1)H_n-n&&\text{sum} \end{align} $$

Answer 4

I would see that as the discrete version of $\int_1^x\ln t \,dt= x\ln x-x+1$. This leads you to a proof by Abel transformation (discrete integration by parts): $$ \sum_{k=1}^nH_k=\sum_{k=1}^nH_k(k+1-k)=(n+1)H_{n+1}-1H_1-\sum_{k=1}^n\underbrace{(k+1)(H_{k+1}-H_k)}_{=1} $$ $$ =(n+1)H_{n+1}-1-n=(n+1)H_n-n. $$

Answer 5

Let $a_1, a_2,,\ldots$ be any sequence, let $H_n$ denote the partial sum

$$H_n=a_1+a_2+\cdots+a_n$$

and let $K_n$ denote the partial sum

$$K_n=1a_1+2a_2+\cdots+na_n$$

Then

$$\begin{align} \sum_{k=1}^n H_k &= a_1+(a_1+a_2)+\cdots(a_1+a_2+\cdots+a_n)\\ &=na_1+(n-1)a_2+\cdots+2a_{n-1}+1a_n\\ &=(n+1)(a_1+a_2+\cdots a_n)-(1a_1+2a_2+\cdots+na_n)\\ &=(n+1)H_n - (1a_1+2a_2+\cdots+na_n)\\ &=(n+1)H_n-K_n\\ \end{align}$$

Given this completely general identity, the specific identity for the harmonic numbers is obvious from the simple observation that

$$K_n={1\over1}+{2\over2}+\cdots+{n\over n}=n$$

Answer 6

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\\ \end{align}