Maths Olympiad Prep

Library / /13 of 120

, 2012

Algebra Difficulty 4.6 AIME Prove it Saudi Arabia

For any positive integer kk define
Hk=1+12+⋯+1k. H_k = 1 + \frac{1}{2} + \dots + \frac{1}{k}.
Prove the relation
1+1n+1∑k=1nHk=Hn+1. 1 + \frac{1}{n+1} \sum_{k=1}^{n} H_k = H_{n+1}.

Solutions — 2

Solution 1

We have
∑k=1nHk=1+(1+12)+(1+12+13)+⋯+(1+12+⋯+1n)=n+n−12+n−23+⋯+1n=(n+1)−1+n+1−22+n+1−33+⋯+n+1−nn=(n+1)(1+12+⋯+1n)−n=(n+1)Hn−n. \begin{align*} \sum_{k=1}^{n} H_k &= 1 + \left(1 + \frac{1}{2}\right) + \left(1 + \frac{1}{2} + \frac{1}{3}\right) + \dots + \left(1 + \frac{1}{2} + \dots + \frac{1}{n}\right) \\ &= n + \frac{n-1}{2} + \frac{n-2}{3} + \dots + \frac{1}{n} \\ &= (n+1) - 1 + \frac{n+1-2}{2} + \frac{n+1-3}{3} + \dots + \frac{n+1-n}{n} \\ &= (n+1) \left(1 + \frac{1}{2} + \dots + \frac{1}{n}\right) - n = (n+1)H_n - n. \end{align*}
Using the above relation we get
1+1n+1∑k=1nHk=1+1n+1[(n+1)Hn−n]=Hn+1−nn+1=Hn+1n+1=Hn+1. \begin{align*} 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{align*}

Solution 2

For n=1n=1 we have 1+12H1=1+12=H21+\frac{1}{2}H_1 = 1+\frac{1}{2}=H_2. Assume that
1+1n+1∑k=1nHk=Hn+1. 1 + \frac{1}{n+1} \sum_{k=1}^{n} H_k = H_{n+1}.
We get
1+1n+2∑k=1n+1Hk=1+1n+2Hn+1+n+1n+2⋅1n+1∑k=1nHk=1+1n+2Hn+1−n+1n+2+n+1n+2⋅Hn+1=Hn+1+1n+2=Hn+2, \begin{align*} 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{align*}
and the relation is proved by induction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.