An identity satisfied by 'harmonic numbers' [duplicate]

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?

Solution 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.

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

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

Solution 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. $$