Let $(x_{n}) \ n\geq 1$ be a sequence of real numbers with $x_{1}=1$ satisfying $2x_{n+1}=3x_{n}+\sqrt{5x_{n}^{2}-4}$ a) Prove that the sequence consists only of natural numbers. b) Check if there are terms of the sequence divisible by $2011$.
Problem
Source: Greek TST 2014-Pr.1.
Tags: induction, modular arithmetic, quadratics, number theory proposed, number theory
thugzmath10
24.06.2014 07:00
We have $2x_2=3x_1+\sqrt{5x_1^2-4}=4$, so $x_2=2$. Now, for all $n\geq 1$, we have $2x_{n+1}=3x_{n}+\sqrt{5x_n^2-4}> 2x_n\implies x_{n+1}>x_n$. Also, $2x_{n+1}=3x_{n}+\sqrt{5x_n^2-4}$ is equivalent to
\[\begin{aligned}
(2x_{n+1}-3x_n)^2-5x_n^2=-4\implies x_{n+1}^2-3x_{n+1}x_n+x_n^2=-1.
\end{aligned}\]
Thus, we have $ x_{n+2}^2-3x_{n+2}x_{n+1}+x_{n+1}^2=-1$. It follows that $x_{n+2}^2-3x_{n+2}x_{n+1}+x_{n+1}^2= x_{n+1}^2-3x_{n+1}x_n+x_n^2$, so we get $(x_{n+2}-x_n)(x_{n+2}+x_n-3x_{n+1})=0$. As $x_{n+2}>x_{n+1}>x_n$, we get $x_{n+2}=3x_{n+1}-x_n$ for all $n\geq 1$. As $x_1, x_2$ are natural numbers, by induction we deduce that $x_n$ is a natural number for all $n\geq 1$.
shmm
24.06.2014 07:40
thugzmath10 your solution is false
thugzmath10
24.06.2014 08:03
Is there a flaw in my solution?
shmm
24.06.2014 08:25
Oh.sorry.my mistake
bcp123
15.08.2014 21:16
Consider the sequence satisfying $x_1=1$, $x_2=2$ and $x_{n+2}=3x_{n+1}-x_n$. It can be shown that this sequence satisfies $ 2x_{n+1}=3x_{n}+\sqrt{5x_{n}^{2}-4} $ and has general term $x_n=\frac{\left(\frac{3+\sqrt{5}}{2}\right)^n+\left(\frac{3-\sqrt{5}}{2}\right)^n}{3}$. Since $2011\equiv 1\pmod{5}$, $5$ is a quadratic residue $\pmod{5}$ so by FLT for $n=2010$, $x_n$ is divisible by $2011$. EDIT:Ignore this and look posts below.
mavropnevma
15.08.2014 21:39
bcp123 wrote: ... and has general term $x_n=\frac{\left(\frac{3+\sqrt{5}}{2}\right)^n+\left(\frac{3-\sqrt{5}}{2}\right)^n}{3}$. Since $2011\equiv 1\pmod{5}$, $5$ is a quadratic residue $\pmod{5}$ so by FLT for $n=2010$, $x_n$ is divisible by $2011$. No, the general term is ${x_n=\dfrac {\sqrt{5}-1}{2\sqrt{5}} \left(\frac{3+\sqrt{5}}{2}\right)^n+\dfrac {\sqrt{5}+1}{2\sqrt{5}}\left(\frac{3-\sqrt{5}}{2}\right)^n}$ (notice $x_n = F_{2n-1}$ using the Fibonacci numbers). Also, what follows is flawed.
bcp123
15.08.2014 22:12
Thank you for correction. $(\frac{1+\sqrt{5}}{2})^n\equiv (\frac{1-\sqrt{5}}{2})^n\pmod{2011}$ gave me $1274^n\equiv 1\pmod{2011}$ and multiplactive order of $1274$ $\pmod{2011}$ is $2010$ so $2011\mid F_{2n-1}\Rightarrow 2010\mid 2n-1$,absurd.
Dimasep
20.08.2014 19:33
May i know why???? We have this x_n = F_{2n-1}
Dimasep
21.08.2014 07:57
How do you get 1274^n congruent to 1 mod 2011 ??????
Seventh
02.01.2015 03:24
Taking the general form $x_n = ((\frac{1+\sqrt{5}}{2})^{2n-1} - (\frac{1-\sqrt{5}}{2})^{2n-1})/\sqrt{5}$, we have that $2^{2n-2} x_n = a_n = \dfrac{(1+\sqrt{5})^{2n-1} - (1-\sqrt{5})^{2n-1}}{2\sqrt{5}}$. So, $a_n$ is solution of the Pell-like equation $x^2 - 5y^2 = -4^{2m+1}$ (it is not hard to see it), with $a_n$ taken to $y$. And if $a_n$ is multiple of $2011$, we have that $x^2 \equiv_{2011} -4^{2m+1} = -(2^k)^2 \iff 2011| x^2 + (2^k)^2$, but it is absurd, since $2011 \equiv_4 3$. Therefore, there aren't any $x_n$ multiple of $2011$.
SidVicious
10.08.2016 01:35
a) As in 2# we have $x_{n+2}=3x_{n+1}-x_n$ b) Define sequence $(b)_{n \ge 3}^{\infty}$ with $b_3=1, b_4=2$ and $b_{n+2}=b_{n+1}+b_n$. Then $x_n=b_n^2+b_{n+1}^2$ for $n \ge 3$. Proof by induction: Base is trivial; $x_3=5=2^2+1^2=b_3^2+b_4^2, x_4=13=3^2+2^2=b_4^2+b_5^2$. Suppose it holds for all number $x_i$ with index $\le n+1$. Then $x_{n+2}=3x_{n+1}-x_{n}=3(b_{n+1}^2+b_{n+2}^2)-b_n^2-b_{n+1}^2=b_{n+2}^2+2b_{n+2}^2+2b_{n+1}^2-b_n^2=b_{n+2}^2+(b_{n+2}^2+b_{n+1}^2)+b_{n+2}^2+b_{n+1}^2-b_n^2=b_{n+2}^2+(b_{n+2}^2+b_{n+1}^2)+(b_{n+2}-b_{n+1})^2+2b_{n+1}b_{n+2}-b_n^2=b_{n+2}^2+(b_{n+2}^2+b_{n+1}^2+2b_{n+1}b_{n+2})=b_{n+2}^2+b_{n+3}^2$, as desired. Hence $x_n=b_n^2+b_{n+1}^2$ but this implies $x_n$ can't be divisible by $2011 \equiv -1 (mod 4)$
Devastator
17.06.2019 14:09
I think I have a different solution for part (b)
Suppose that $x_k$ is divisible by 2011 for some natural number $k$
From part (a), we already know that $a_{k+1}$ is an integer
Then by the given, $5x_k^2-4$ must be a perfect square
Note that the above expression is $-4 mod 2011$
However, $4$ is clearly a quadratic residue modulo $2011$, and $2011$ is a prime that is congruent to $3mod4$. Hence, $-4$ is not a quadratic residue modulo $2011$, a contradiction. (I asked my friend, he said that this is well known. I think that this can be proven by contradiction as shown below)
Click to reveal hidden textConsider some $3mod4$ prime $p$. Suppose that $x$ and $-x$ are both quadratic residues modulo $p$. Then there exists integers $a$ and $b$ such that $a^2$ and $b^2$ are congruent to $x$ and $-x$ modulo $p$, respectively. Therefore, $p$ divides $a^2+b^2$. Wait I made a mistake nvm. I think orders could finish off the last part tho, not sure...
Hence, no term of the sequence is divisible by $2011$
Kimchiks926
01.03.2020 14:25
Similary as above it is easy to obtain that $x_{n+2} = 3x_{n+1} - x_{n}$ with $x_1=1$ and $x_2=2$. This seqeunce has a property that $x_{n+1}^2+1=x_nx_{n+2}$. ( it can be showed with induction )So if we assume wlog that $x_n$ is divisible by $2011$ then $x_{n+1}^2+1$ is also divisible by $2011$, but $2011$ is a prime , which is $3$ mod $4$, therefore $x_{n+1}^2+1$ is divisible by prime, which is $3$ mod $4$ - contradiction, since $a^2+1$ is divisble only by primes , which are $1$ mod $4$.