Sum of Scaled Harmonic Numbers

Question

I came across the following identity: $$ \frac{1}{n}\sum_{j=1}^{n}\sum_{k=j}^{n}\frac{1}{k}=1. $$ However, I do not know how to prove it except verify it by numerical calculations. Does any one know how to prove it or give me some hints? Thanks very much.

Answer 1

In the double sum $$\sum_{j=1}^{n}\sum_{k=j}^{n}\frac{1}{k}$$ each fraction $1/k$ occurs $k$ times, so overall these contribute $1$ to the sum. As $k$ ranges from $1$ to $n$, the total sum is $n$.

Answer 2

Using Iverson Brackets can simplify the changing of the order of summation: $$ \begin{align} \frac1n\sum_{j=1}^n\sum_{k=j}^n\frac1k &=\frac1n\sum_{j=1}^n\sum_{k=1}^n[k\ge j]\frac1k\\ &=\frac1n\sum_{k=1}^n\sum_{j=1}^n[k\ge j]\frac1k\\ &=\frac1n\sum_{k=1}^n\sum_{j=1}^k\frac1k\\ &=\frac1n\sum_{k=1}^n1\\[9pt] &=1 \end{align} $$

Answer 3

By double counting we have

$$\frac{1}{n}\sum_{j=1}^{n}\sum_{k=j}^{n}\frac{1}{k}=\frac1n \sum_{k=1}^{n}\sum_{j=1}^{k}\frac{1}{k}=\frac1n \sum_{k=1}^{n}1=\frac1n \cdot n=1$$

Answer 4

We can also write the index region conveniently to better see what's going on.

We obtain \begin{align*} \frac{1}{n}\sum_{j=1}^n\sum_{k=j}^n\frac{1}{k}&=\frac{1}{n}\sum_{\color{blue}{1\leq j\leq k\leq n}}\frac{1}{k}\\ &=\frac{1}{n}\sum_{k=1}^n\sum_{j=1}^k\frac{1}{k}\\ &=\frac{1}{n}\sum_{k=1}^n1\\ &=1 \end{align*}

Answer 5

Another proof uses the well-known formula for the sum of harmonic numbers

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

The double sum of the OP can be written as

$$\frac{1}{n} \sum_{j=1}^{n}\left (H_n - H_{j-1}\right)\\ =H_n - \frac{1}{n} \sum_{m=1}^{n-1} H_m\\ = H_n - \frac{1}{n} \left (n H_{n-1} -n +1\right)\\ = H_n - H_{n-1} + 1 -\frac{1}{n} = 1$$

In the second line we have used that $H_0=0$, and in last line we have employed the defining recursion relation of the harmonic numbers.