Let $s$ be a positive integer. Let $\{a_n\}_{n=1}^{\infty}$ be a
sequence given by $$a_1=0, \ a_2=2s, \ a_3=3, \ a_{n+3}=s a_{n+1}+a_n \ \
\ \text{for} \ n\ge 1.$$
Prove that for any prime number $p$, the number $a_p$ is divisible by $p$.
Solution.
Let the roots of the equation $x^3-sx-1=0$ be $x_1, x_2$ and
$x_3=-x_1-x_2$ (Vieta's formulas), they are algebraic integers (by
definition). One directly observes (using the initial conditions) that
$a_n=x_1^n+x_2^n+(-x_1-x_2)^n$. Assume $p>2$ (the other is obvious).
We have
$$a_p=x_1^p+x_2^p+(-x_1-x_2)^p=-\sum_{k=1}^{p-1}{p\choose k}x_1^kx_2^{p-k}$$
${p\choose k}$
is divisible by $p$ for $1\le k \le p-1$, so we obtain that $a_p=p A$
where $A$ is an algebraic integer, since algebraic integers form a ring.
However, from here we see that $A$ is also rational, hence $A$ is
integer. Thus $p$ divides $a_p$.
I would like to thank
Mr. Bozhilov for finding a mistake in the original proof, and his
fruitful discussion, which led to a resolution.
The problem appeared at AKHIMO 2018.
No comments:
Post a Comment