Maths Olympiad Prep

Library / /30 of 48

Algebra Difficulty 6.2 National olympiad Prove it Greece

Let (xn)(x_n), n1n \ge 1, be a sequence of real numbers with x1=1x_1 = 1, such that 2xn+1=3xn+5xn242x_{n+1} = 3x_n + \sqrt{5x_n^2 - 4}, for n=1,2,3,...n=1,2,3,...

a. Prove that all terms of the sequence are natural numbers.

β. Examine if there exist a term of the sequence divisible by 20112011.

Solution

a.
From the given recurrence relation we get
(2xn+13xn)2=5xn244xn+1212xn+1xn+4xn2=4xn+123xn+1xn+xn2=1(1) (2x_{n+1} - 3x_n)^2 = 5x_n^2 - 4 \Rightarrow 4x_{n+1}^2 - 12x_{n+1}x_n + 4x_n^2 = -4 \Rightarrow x_{n+1}^2 - 3x_{n+1}x_n + x_n^2 = -1 \quad (1)
which can be written also in the form
xn+223xn+2xn+1+xn+12=1(2). x_{n+2}^2 - 3x_{n+2}x_{n+1} + x_{n+1}^2 = -1 \quad (2).
We consider now the second degree equation: x23xxn+1+xn+12+1=0x^2 - 3x \cdot x_{n+1} + x_{n+1}^2 + 1 = 0.
From (1), (2), we observe that two solutions of this equation are xn,xn+2x_n, x_{n+2}, and hence by using Vieta's formulas we get:
xn+xn+2=3xn+1(3)andxnxn+2=xn+12+1(4). x_n + x_{n+2} = 3x_{n+1} \quad (3) \quad \text{and} \quad x_n x_{n+2} = x_{n+1}^2 + 1 \quad (4).
Writing relation (3) in the form xn+2=3xn+1xnx_{n+2} = 3x_{n+1} - x_n and taking in mind that x1=1x_1 = 1 and x2=2x_2 = 2 we conclude by induction that all terms of the sequence are integers

β.
We suppose that there exists a term xsx_s of the sequence such that: 2011xs2011|x_s. Then from (4) for n=sn=s, we get xsxs+2=xs+12+1x_s x_{s+2} = x_{s+1}^2 + 1. Since all terms of the sequence are integers and 2011xs2011|x_s, we have:
2011xs+12+1xs+121(mod2011)(xs+12)1005(1)10051(mod2011)xs+120101(mod2011)(5) \begin{aligned} 2011 \mid x_{s+1}^2 + 1 &\Rightarrow x_{s+1}^2 \equiv -1 \pmod{2011} \\ &\Rightarrow (x_{s+1}^2)^{1005} \equiv (-1)^{1005} \equiv -1 \pmod{2011} \\ &\Rightarrow x_{s+1}^{2010} \equiv -1 \pmod{2011} \end{aligned} \quad (5)
We know that 20112011 is prime and it is easy to see that (xs+1,2011)=1(x_{s+1}, 2011) = 1.
In fact, if (xs+1,2011)=d>1(x_{s+1}, 2011) = d > 1, then dxs+1d|x_{s+1}, d2011dxs+1d|2011 \Rightarrow d|x_{s+1}, dxsd|x_s and then from relation xsxs+2=xs+12+1x_s x_{s+2} = x_{s+1}^2 + 1 we conclude that d1d|1, absurd.
Therefore from Fermat's theorem we have:
xs+120101(mod2011),(6) x_{s+1}^{2010} \equiv 1 \pmod{2011}, \quad (6)
which contradicts relation (5).

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.