Define the sequence $\{a_i\}$ by $a_0=1$, $a_1=4$, and $a_{n+1}=5a_n-a_{n-1}$ for all $n\geq 1$. Show that all terms of the sequence are of the form $c^2+3d^2$ for some integers $c$ and $d$.
Problem
Source: Philippine Mathematical Olympiad 2020/3
Tags: PMO, number theory
kaede
19.01.2020 19:49
Proposition
$a^{2}_{n+1} +3=a_{n} a_{n+2} \cdots ( \heartsuit )$ holds for all non-negative integers $n$.
Proof of this proposition$a_{2} =5a_{1} -a_{0} =20-1=19$
$a_{3} =5a_{2} -a_{1} =95-4=91$
We can show the above equality by induction on $n\in \mathbb{Z}_{\geq 0}$.
For $n=0$, $a^{2}_{1} +3=19=1\cdotp 19=a_{0} \cdotp a_{2}$.
For $n=1$, $a^{2}_{2} +3=364=4\cdotp 91=a_{1} \cdotp a_{3}$.
Suppose that $( \heartsuit )$ holds for $n=k$ and $n=k+1$ for some $k\in \mathbb{Z}_{\geq 0}$.
${a^{2}_{k+3} +3} =( 5a_{k+2} -a_{k+1})^{2} +3=25a^{2}_{k+2} -10a_{k+2} a_{k+1} +a^{2}_{k+1} +3$
$=$$25a^{2}_{k+2} -10a_{k+2} a_{k+1} +a_{k} \cdotp a_{k+2}$
$=a_{k+2}( 25a_{k+2} -10a_{k+1} +a_{k})$
It is sufficient to show that $a_{k+4} =25a_{k+2} -10a_{k+1} +a_{k}$ :
$a_{k+4} =5a_{k+3} -a_{k+2} =5( 5a_{k+2} -a_{k+1}) -( 5a_{k+1} -a_{k})$
$=25a_{k+2} -10a_{k+1} +a_{k}$
Therefore, we have $a^{2}_{k+3} +3 =a_{k+2} \cdotp a_{k+4}$ , which implise $( \heartsuit )$ holds for $n=k+2$.
Hence $( \heartsuit )$ holds for all non-negative integers $n$.
$\blacksquare $
Proof of $a_{n}=x^2+3y^2$ for some $(x,y)$
$1=1^{2} +3\cdotp 0^{2}$
$4=2^{2} +3\cdotp 0^{2}$
By the proposition, we have $a^{2}_{n+1} +3=a_{n} a_{n+2}$.
For simplicity, let $N=a^{2}_{n+1} +3$.
Note that $a_{n} \mid N$ and $N\equiv 4\pmod 8$ or $N\equiv 1\pmod 2$
Hence we have $a_{n} =x^{2} +3y^{2}$ for some $( x,y) \in \mathbb{Z}^{2}$ due to the following two lemmas.
$\blacksquare $
Lemma1
Let $n$ be an integer.
If $p$ is an odd prime divisor of $n^{2} +3$, then $p=x^{2} +3y^{2}$ for some $( x,y) \in \mathbb{Z}^{2}$.
proof of this lemmaFor $p=3$, $p=0^{2} +3\cdotp 1^{2}$.
Suppose that $p >3$.
There exist $( s,t) ,( s',t') \in \mathbb{Z}^{2}$ such that $s-nt\equiv s'-nt\pmod p$ and $s,s',t,t'\in \left[ 0,\sqrt{p}\right)$.
Let $x=s-s'$ and $y=t-t'$.
Then $x^{2} =( s-s')^{2} \equiv ( n( t-t')^{2} =n^{2} y^{2} \equiv -3y^{2}\pmod p$.
Furthermore, we have $x^{2} +3y^{2} < p+3p=4p$.
So we have $x^{2} +3y^{2} =kp$ for some $k\in \mathbb{N}$ with $k\leq 3$.
Since $x^{2} +3y^{2} \not \equiv 2\pmod 4$, we have $x^{2} +3y^{2} \neq 2p$.
If $k=3$, then we have $3( x/3)^{2} +y^{2} =p$.
If $k=1$, then we have $x^{2} +3y^{2} =p$, of course.
$\blacksquare $
Lemma2
$\left( x^{2} +3y^{2}\right)\left( z^{2} +3w^{2}\right) =( xz+3yw)^{2} +3( xw-yz)^{2}$
proof of this lemmaJust expand the LHS and RHS.
InternetPerson10
19.01.2020 20:05
nice sol @above!
\begin{align*}
a_0=1&=1^2+3\cdot 0^2 \\
a_1=4&=1^2+3\cdot 1^2 \\
a_2=19&=4^2+3\cdot 1^2 \\
a_3=91&=4^2+3\cdot 5^2 \\
a_4=436&=19^2+3\cdot 5^2 \\
a_5=2089&=19^2+3\cdot 24^2 \\
a_6=10009&=91^2+3\cdot 24^2 \\
a_7=47956&=91^2+3\cdot 115^2 \\
\end{align*}In general, $a_{2n}=a^2_n + 3\cdot \left(\sum^{n-1}_{i=0} a_i\right)^2$ and $a_{2n+1}=a^2_n + 3\cdot \left(\sum^{n}_{i=0} a_i\right)^2$ for all $n\geq 1$. This can be proved using induction based on the difference $a_n-a_{n-1}$ for odd and even $n$.
sticknycu
19.01.2020 22:07
This is linear omogen recurence. Just put characteristic equation $r^2-5r+1=0$ and that is.
ismayilzadei1387
03.09.2023 19:28
Look Serbia 2008