Maths Olympiad Prep

Library / Argentine National Olympiad /6 of 23

Argentine National Olympiad, 2016

Algebra Difficulty 6.1 National Olympiad Prove it Argentina

For an integer m≥3m \ge 3 set S(m)=1+13+⋯+1mS(m) = 1 + \frac{1}{3} + \dots + \frac{1}{m} (the fraction 1/m1/m does not participate in the sum). Let n≥3n \ge 3 and k≥3k \ge 3. Compare the numbers S(nk)S(nk) and S(n)+S(k)S(n) + S(k).

Solution

We show that S(nk)<S(n)+S(k)S(nk) < S(n) + S(k). Cancel the summand of S(k)S(k) on both sides of this inequality, then add 12\frac{1}{2} to both sides and rearrange. This yields the equivalent inequality
1k+1+1k+2+⋯+1nk+12<1+12+13+⋯+1n.(∗) \frac{1}{k+1} + \frac{1}{k+2} + \dots + \frac{1}{nk} + \frac{1}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}. \quad (*)
Divide the first (n−1)k(n-1)k numbers on the left hand side into n−1n-1 sums of kk fractions with consecutive denominators: A1=1k+1+⋯+12kA_1 = \frac{1}{k+1} + \dots + \frac{1}{2k}, A2=12k+1+⋯+13kA_2 = \frac{1}{2k+1} + \dots + \frac{1}{3k}, ..., An−1=1(n−1)k+1+⋯+1nkA_{n-1} = \frac{1}{(n-1)k+1} + \dots + \frac{1}{nk}.
Then compare AjA_j with 1j\frac{1}{j} for j=1,…,n−1j=1, \dots, n-1. Denoting dj=1j−Aj=1j−1jk+1−1jk+2−⋯−1jk+kd_j = \frac{1}{j} - A_j = \frac{1}{j} - \frac{1}{jk+1} - \frac{1}{jk+2} - \dots - \frac{1}{jk+k}
we have
dj=(1jk−1jk+1)+(1jk−1jk+2)+⋯+(1jk−1jk+k)= d_j = \left( \frac{1}{jk} - \frac{1}{jk+1} \right) + \left( \frac{1}{jk} - \frac{1}{jk+2} \right) + \dots + \left( \frac{1}{jk} - \frac{1}{jk+k} \right) =
=1jk(jk+1)+2jk(jk+2)+⋯+kjk(jk+k)> = \frac{1}{jk(jk+1)} + \frac{2}{jk(jk+2)} + \dots + \frac{k}{jk(jk+k)} >

>1+2+...+kjk(jk+k)=k+12k⋅1j(j+1)>12j−12(j+1) > \frac{1+2+...+k}{jk(jk+k)} = \frac{k+1}{2k} \cdot \frac{1}{j(j+1)} > \frac{1}{2j} - \frac{1}{2(j+1)}
It follows that
(1+12+13+⋯+1n)−(1k+1+1k+2+⋯+1nk)=d1+⋯+dn−1+1n>(12−14)+(14−16)+⋯+(12n−2−12n)+1n=12+12n>12 \left(1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}\right)-\left(\frac{1}{k+1}+\frac{1}{k+2}+\dots+\frac{1}{nk}\right)=d_1+\dots+d_{n-1}+\frac{1}{n} > \left(\frac{1}{2}-\frac{1}{4}\right)+\left(\frac{1}{4}-\frac{1}{6}\right)+\dots+\left(\frac{1}{2n-2}-\frac{1}{2n}\right)+\frac{1}{n} = \frac{1}{2}+\frac{1}{2n} > \frac{1}{2}
This proves (*), hence S(nk)<S(n)+S(k)S(nk) < S(n) + S(k) holds true.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.