The problem :
The sequence $a_0, a_1, a_2, ...$ is defined by $a_0 = 1, a_1 = 3, a_{n+2} = a_{n+1} + 9a_n$ for $n$ even, $9a_{n+1} + 5a_n$ for $n$ odd. Show that $a_{1995}^2 + a_{1996}^2 + a_{1997}^2 + a_{1998}^2 + a_{1999}^2 + a_{2000}^2$ is divisible by 20, and that no $a_{2n+1}$ is a perfect square.
It is an old Vietnamese problem $(1995)$ for which I can't find any solutions ; the problem comes from the site prase.cz : 33rd vietnam 1995. Any ideas ?
My "ideas / approaches" :
I'm pretty much stuck on it, which is why I'm asking for help here :) , but I think for the first question, a good way to start would be to rewrite the expression with only $a_{1995}$. But then I don't really see what to do.
For the second one, I'm also stuck on it. Maybe find the characteristic polynomial of the sequence, then try to prove the question by transforming the polynomial into its canonical form and then writing the equation: "canonical form of the polynomial" $= z^2$ where $z^2$ is a perfect square.
- zouirou.
For $n \ge 1$
$\quad a_n \equiv 0 \pmod{3} \; \land \; a_n \not\equiv 0 \pmod{9}$
So $3$ is a factor of $a_n$ but $3^2$ isn't and therefore none of these $a_n$ can be perfect squares.
We begin by calculating $\pmod{5}$ on the sequence and find the repeating block of length $8$ (starting on even index),
$\; 2 \mapsto 2 $
$\; 3 \mapsto 3 $
$\; 4 \mapsto 1 $
$\; 5 \mapsto 4 $
$\; 6 \mapsto 3 $
$\; 7 \mapsto 2 $
$\; 8 \mapsto 4 $
$\; 9 \mapsto 1 $
So we're looking for max $k$ with $2 + 8k \le 1995$ and the block starts at index $1994$.
Continuing, we calculate
$\quad 3^2+1^2+4^2+3^2+2^2+4^2 \equiv 0 \pmod{5}$
We do the same procedure with $\pmod{4}$ and arrive at
$\quad 3^2+3^2+2^2+1^2+3^2+0^2 \equiv 0 \pmod{4}$
We conclude that $a_{1995}^2 + a_{1996}^2 + a_{1997}^2 + a_{1998}^2 + a_{1999}^2 + a_{2000}^2$ is divisible by $20$.