Maths Olympiad Prep

Library / /86 of 462

Algebra Difficulty 5.0 AIME, harder Prove it Ireland

Define a sequence xn:n=1,2,3,x_n : n = 1, 2, 3, \dots by x1=1x_1 = 1 and xn=xn1+nx_n = x_{n-1} + \sqrt{n} for n2n \ge 2. Show that:
n=120181xn<3. \sum_{n=1}^{2018} \frac{1}{x_n} < 3.

Solution

xn(n+1)(n+2)6x_n \ge \frac{(n+1)(n+2)}{6}

This is true for n=1n=1. Now suppose n2n \ge 2 and suppose that, inductively:
xn1n(n+1)6 x_{n-1} \ge \frac{n(n+1)}{6}
Now as n2n \ge 2, we have:
n+1n=1+1n32 \frac{n+1}{n} = 1 + \frac{1}{n} \le \frac{3}{2}
Multiplying each side by n(n+1)9\frac{n(n+1)}{9}:
(n+1)29n(n+1)6 \frac{(n+1)^2}{9} \le \frac{n(n+1)}{6}
As both sides are positive, we can take the square root of each side, which gives:
n+13n(n+1)6 \frac{n+1}{3} \le \sqrt{\frac{n(n+1)}{6}}
This allows us to complete the inductive step:
xn=xn1+xn1n(n+1)6+n(n+1)6n(n+1)6+n+13=(n+1)(n+2)6. x_n = x_{n-1} + \sqrt{x_{n-1}} \\ \ge \frac{n(n+1)}{6} + \sqrt{\frac{n(n+1)}{6}} \\ \ge \frac{n(n+1)}{6} + \frac{n+1}{3} = \frac{(n+1)(n+2)}{6}.

This is the inductive step we had to prove. Now we can apply this to the sum, which is:
n=120181xnn=120186(n+1)(n+2)=n=12018(6n+16n+2)=362020<3. \sum_{n=1}^{2018} \frac{1}{x_n} \le \sum_{n=1}^{2018} \frac{6}{(n+1)(n+2)} = \sum_{n=1}^{2018} \left( \frac{6}{n+1} - \frac{6}{n+2} \right ) = 3 - \frac{6}{2020} < 3.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.