Maths Olympiad Prep

Library / /68 of 82

Algebra Difficulty 6.3 National olympiad Prove it Croatia

Given the sequence of real numbers x0=1x_0 = 1, x1=1x_1 = 1,
xn=n2+xn1xn2,for n2, x_n = \sqrt{\frac{n}{2} + x_{n-1}x_{n-2}}, \quad \text{for } n \ge 2,
determine whether there exists a real number AA such that An<xn<An+1An < x_n < An+1 for all nNn \in \mathbb{N}?

Solution

Note that all members of the sequence are positive real numbers. The recursive relation gives
2xn2=n+2xn1xn2xn12+xn22+n. 2x_n^2 = n + 2x_{n-1}x_{n-2} \le x_{n-1}^2 + x_{n-2}^2 + n.

2xn2xn12+xn22+n,2xn12xn22+xn32+n1,2x32x22+x12+3,2x22x12+x02+2. \begin{aligned} 2x_n^2 &\le x_{n-1}^2 + x_{n-2}^2 + n, \\ 2x_{n-1}^2 &\le x_{n-2}^2 + x_{n-3}^2 + n-1, \\ &\vdots \\ 2x_3^2 &\le x_2^2 + x_1^2 + 3, \\ 2x_2^2 &\le x_1^2 + x_0^2 + 2. \end{aligned}
Adding all these inequalities gives
2xn2+xn122x12+x02+[n+(n1)++3+2], 2x_n^2 + x_{n-1}^2 \le 2x_1^2 + x_0^2 + [n + (n-1) + \dots + 3 + 2],
i.e.
2xn2+xn12n2+n+42.() 2x_n^2 + x_{n-1}^2 \le \frac{n^2 + n + 4}{2}. \quad (*)
If there exists a sought number AA, the left hand side of this inequality is at least 2A2n2+A2(n1)22A^2n^2 + A^2(n-1)^2, thus
2A2n2+A2(n1)2n2+n+42, 2A^2n^2 + A^2(n-1)^2 \le \frac{n^2 + n + 4}{2},
i.e. 6A2n24A2n+2A2n2+n+46A^2n^2 - 4A^2n + 2A^2 \le n^2 + n + 4. This inequality holds for every nNn \in \mathbb{N} only if 6A216A^2 \le 1, i.e. A66A \le \frac{\sqrt{6}}{6}.
We prove that A=66A = \frac{\sqrt{6}}{6} satisfies the conditions of the problem.
First, we show inductively that xn>n66x_n > \frac{n\sqrt{6}}{6}, for all nN0n \in \mathbb{N}_0. Statement is true for n=0n=0 and n=1n=1. Let us assume xn1>(n1)66x_{n-1} > \frac{(n-1)\sqrt{6}}{6} and xn2>(n2)66x_{n-2} > \frac{(n-2)\sqrt{6}}{6}. Then
xn2=n2+xn1xn2>n2+(n1)66(n2)66=n2+26>n26, x_n^2 = \frac{n}{2} + x_{n-1}x_{n-2} > \frac{n}{2} + \frac{(n-1)\sqrt{6}}{6} \cdot \frac{(n-2)\sqrt{6}}{6} = \frac{n^2 + 2}{6} > \frac{n^2}{6},
i.e. xn>n66x_n > \frac{n\sqrt{6}}{6}, and this finishes the inductive step.
Next, we prove that xn<n66+1x_n < \frac{n\sqrt{6}}{6} + 1, for all nNn \in \mathbb{N}. The statement is true for n=1n=1 and n=2n=2 by inspection. Inequality ()(*) and the fact xn12>(n1)26x_{n-1}^2 > \frac{(n-1)^2}{6} imply
2xn2n2+n+42xn12<n2+n+42(n1)26=2n2+5n+116. 2x_n^2 \le \frac{n^2 + n + 4}{2} - x_{n-1}^2 < \frac{n^2 + n + 4}{2} - \frac{(n-1)^2}{6} = \frac{2n^2 + 5n + 11}{6}.
It remains to show
2n2+5n+116<2(n66+1)2, \frac{2n^2 + 5n + 11}{6} < 2 \left( \frac{n\sqrt{6}}{6} + 1 \right)^2,
but this inequality is equivalent to 5n1<4n65n - 1 < 4n\sqrt{6} which holds for n3n \ge 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 and solution reproduced as published; topic and difficulty added by this site.