Maths Olympiad Prep

Library / /455 of 520

Algebra Difficulty 7.5 National olympiad, round 2 Prove it

Let (xn)n=1(x_n)_{n=1}^\infty be a sequence defined recursively with: x1=2x_1=2 and xn+1=xn(xn+n)n+1x_{n+1}=\frac{x_n(x_n+n)}{n+1} for all n1n \ge 1. Prove that n(n+1)>(x1+x2++xn)2xn+1.n(n+1) >\frac{(x_1+x_2+ \ldots +x_n)^2}{x_{n+1}}.

Proposed by Nikola Velov

Solution

1. Define the sequence and the sum:
Let (xn)n=1 (x_n)_{n=1}^\infty be a sequence defined recursively by:
x1=2andxn+1=xn(xn+n)n+1for all n1. x_1 = 2 \quad \text{and} \quad x_{n+1} = \frac{x_n(x_n + n)}{n+1} \quad \text{for all} \ n \geq 1.
Define Sn=x1+x2++xn S_n = x_1 + x_2 + \ldots + x_n .

2. State the inequality to prove:
We need to prove that:
n(n+1)>(x1+x2++xn)2xn+1. n(n+1) > \frac{(x_1 + x_2 + \ldots + x_n)^2}{x_{n+1}}.
This can be rewritten using Sn S_n as:
Sn<n(n+1)xn+1. S_n < \sqrt{n(n+1)x_{n+1}}.

3. Base case:
For n=1 n = 1 :
S1=x1=2andx2=x1(x1+1)2=232=3. S_1 = x_1 = 2 \quad \text{and} \quad x_2 = \frac{x_1(x_1 + 1)}{2} = \frac{2 \cdot 3}{2} = 3.
We need to check:
2<123=6. 2 < \sqrt{1 \cdot 2 \cdot 3} = \sqrt{6}.
Since 2<6 2 < \sqrt{6} , the base case holds.

4. Inductive step:
Assume the inequality holds for some n1 n \geq 1 , i.e.,
Sn<n(n+1)xn+1. S_n < \sqrt{n(n+1)x_{n+1}}.
We need to show that:
Sn+1<(n+1)(n+2)xn+2. S_{n+1} < \sqrt{(n+1)(n+2)x_{n+2}}.
Note that:
Sn+1=Sn+xn+1. S_{n+1} = S_n + x_{n+1}.
By the inductive hypothesis:
Sn+1=Sn+xn+1<n(n+1)xn+1+xn+1. S_{n+1} = S_n + x_{n+1} < \sqrt{n(n+1)x_{n+1}} + x_{n+1}.

5. Simplify the inequality:
We need to prove:
n(n+1)xn+1+xn+1<(n+1)(n+2)xn+2. \sqrt{n(n+1)x_{n+1}} + x_{n+1} < \sqrt{(n+1)(n+2)x_{n+2}}.
Using the recursive definition:
(n+2)xn+2=xn+1(xn+1+n+1). (n+2)x_{n+2} = x_{n+1}(x_{n+1} + n + 1).
Thus, we need to show:
n(n+1)xn+1+xn+1<(n+1)xn+1(xn+1+n+1). \sqrt{n(n+1)x_{n+1}} + x_{n+1} < \sqrt{(n+1)x_{n+1}(x_{n+1} + n + 1)}.

6. Algebraic manipulation:
Square both sides to eliminate the square roots:
(n(n+1)xn+1+xn+1)2<(n+1)xn+1(xn+1+n+1). (\sqrt{n(n+1)x_{n+1}} + x_{n+1})^2 < (n+1)x_{n+1}(x_{n+1} + n + 1).
Expanding both sides:
n(n+1)xn+1+2xn+1n(n+1)xn+1+xn+12<(n+1)xn+12+(n+1)xn+1(n+1). n(n+1)x_{n+1} + 2x_{n+1}\sqrt{n(n+1)x_{n+1}} + x_{n+1}^2 < (n+1)x_{n+1}^2 + (n+1)x_{n+1}(n+1).
Simplify:
n(n+1)xn+1+2xn+1n(n+1)xn+1+xn+12<(n+1)xn+12+(n+1)2xn+1. n(n+1)x_{n+1} + 2x_{n+1}\sqrt{n(n+1)x_{n+1}} + x_{n+1}^2 < (n+1)x_{n+1}^2 + (n+1)^2x_{n+1}.
Combine like terms:
2xn+1n(n+1)xn+1<(n+1)2xn+1n(n+1)xn+1. 2x_{n+1}\sqrt{n(n+1)x_{n+1}} < (n+1)^2x_{n+1} - n(n+1)x_{n+1}.
Factor out xn+1 x_{n+1} :
2n(n+1)xn+1<(n+1)xn+1+(n+1)xn+1. 2\sqrt{n(n+1)x_{n+1}} < (n+1)x_{n+1} + (n+1)x_{n+1}.
Simplify:
2n(n+1)xn+1<(2n+1)xn+1. 2\sqrt{n(n+1)x_{n+1}} < (2n+1)x_{n+1}.
Divide both sides by xn+1 x_{n+1} :
2n(n+1)<2n+1. 2\sqrt{n(n+1)} < 2n+1.
This is immediate from the AM-GM inequality and the fact that 2n+1>n+1 2n+1 > n+1 .

Thus, the inequality holds for all n1 n \geq 1 by induction.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.