Saudi Arabia Mathematical Competitions 2012

We have $$\begin{array}{rl}\sum _{k=1}^n{H}_k& =1+\left(1+\frac{1}{2}\right)+\left(1+\frac{1}{2}+\frac{1}{3}\right)+\cdots +\left(1+\frac{1}{2}+\cdots +\frac{1}{n}\right)\\ & =n+\frac{n-1}{2}+\frac{n-2}{3}+\cdots +\frac{1}{n}\\ & =(n+1)-1+\frac{n+1-2}{2}+\frac{n+1-3}{3}+\cdots +\frac{n+1-n}{n}\\ & =(n+1)\left(1+\frac{1}{2}+\cdots +\frac{1}{n}\right)-n=(n+1)H_n-n.\end{array}$$ Using the above relation we get $$\begin{array}{rl}1+\frac{1}{n+1}\sum _{k=1}^n{H}_k& =1+\frac{1}{n+1}[(n+1)H_n-n]\\ & =H_n+1-\frac{n}{n+1}=H_n+\frac{1}{n+1}=H_{n+1}.\end{array}$$

---

Alternative solution.

For $n=1$ we have $1+\frac{1}{2}{H}_1=1+\frac{1}{2}=H_2$. Assume that $$1+\frac{1}{n+1}\sum _{k=1}^n{H}_k=H_{n+1}.$$ We get $$\begin{array}{rl}1+\frac{1}{n+2}\sum _{k=1}^{n+1}{H}_k& =1+\frac{1}{n+2}{H}_{n+1}+\frac{n+1}{n+2}\cdot \frac{1}{n+1}\sum _{k=1}^n{H}_k\\ & =1+\frac{1}{n+2}{H}_{n+1}-\frac{n+1}{n+2}+\frac{n+1}{n+2}\cdot H_{n+1}\\ & =H_{n+1}+\frac{1}{n+2}=H_{n+2},\end{array}$$ and the relation is proved by induction.