The sequence $\left(a_n \right)$ is defined by $a_1=1, \ a_2=2$ and $$a_{n+2} = 2a_{n+1}-pa_n, \ \forall n \ge 1,$$for some prime $p.$ Find all $p$ for which there exists $m$ such that $a_m=-3.$
Problem
Source: Mathematics and Youth Magazine (vietnam)
Tags: number theory, arithmetic sequence
17.09.2020 11:27
Same trick as for this classical problem from Mathematical Excalibur (from where it is surely copied).
18.07.2023 18:20
The following sollution works for any integer p (not compulsory prime or even positive), and it consists in doing casework based on p mod 3: $1.\; p \equiv 0 \mod{3} $ This is the easiest one as $a_{n} $ is never divisible by 3. $2. \; p \equiv -1 \mod{3} $ Note that $ a_{n+2} \equiv 2a_{n+1}-pa_n \equiv 2a_{n+1}+a_n \mod{3} $. Thus the period of $a_n \; \mod{3}$ is $\fbox{ (1,2,2,0,2,1,1,0)}$ which is easy to prove by strong induction using the above relation. This means that $3 \mid {a_k} \Rightarrow 4 \mid k$. Also $ a_{n+2} \equiv a_{n}\mod{2} \Rightarrow 2 \mid a_{2x} $. So ${3 \mid {a_k}} \Rightarrow 4 \mid k \Rightarrow {2 \mid {a_k}}$, meaning $-3$ is not part of the sequence. $3. \; p \equiv 1 \mod{3} $ This time $ a_{n+2} \equiv 2a_{n+1}-pa_n \equiv 2a_{n+1}-a_n \mod{3} $ . Meaning the period of the sequence is just $\fbox {(1,2,0)}$. Parity does not help this time, instead $\mod{p-4} $ does. Note again that $ a_{n+2} \equiv 2a_{n+1}-pa_n \equiv 2a_{n+1}-4a_n \mod{p-4} $, and it is not hard to prove using strong induction that: ${a_{n} \equiv 2^{n-1} \mod{p-4}}$ if ${n \equiv 1 \mod{6}}$ or ${n \equiv 2 \mod{6}}$ ${a_{n} \equiv -2^{n-1} \mod{p-4}}$ if ${n \equiv 4 \mod{6}}$ or ${n \equiv 5 \mod{6}}$ ${a_{n} \equiv 0 \mod{p-4}}$ if ${n \equiv 0 \mod{3}}$ This means that $3\mid a_{n} \Rightarrow 3\mid n \Rightarrow p-4 \mid a_{n} $ Finally, if there exists k such that $a_{k}=-3$, we get $p-4 \mid -3 \Rightarrow $ $p$ can only be $1, 3, 5 $ or $ 7.$ $3$ and $5$ are not $ 1 \mod{3} $. For n=1 it is easy to see that $ a_n = n \; \forall \; n $ so $-3$ does not belong to the sequence. So we are only left with $p=7$, when $a_3=-3$ Thus $\fbox {p=7}$ is the only solution q.e.d. This is also my first post