Maths Olympiad Prep

Library / Irish Mathematical Olympiad /52 of 236

Irish Mathematical Olympiad

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=xn−1+nx_n = x_{n-1} + \sqrt{n} for n≥2n \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 n≥2n \ge 2 and suppose that, inductively:
xn−1≥n(n+1)6 x_{n-1} \ge \frac{n(n+1)}{6}
Now as n≥2n \ge 2, we have:
n+1n=1+1n≤32 \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)29≤n(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+13≤n(n+1)6 \frac{n+1}{3} \le \sqrt{\frac{n(n+1)}{6}}
This allows us to complete the inductive step:
xn=xn−1+xn−1≥n(n+1)6+n(n+1)6≥n(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=120181xn≤∑n=120186(n+1)(n+2)=∑n=12018(6n+1−6n+2)=3−62020<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,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.