I've been trying this question for a while now: Let $a_0$ and $a_1$ be integers. For an integer $n \geq2$ define $a_n=a_{n-1}+a_{n-2}$. Prove that if $a_2\equiv6a_0\pmod {19}$ and $a_3\equiv6a_1 \pmod{19}$, then $a_{n+2}\equiv6a_n \pmod {19}$ for any non-negative integer $n$. I did the following:
We use strong induction to prove this.
Base cases: $n=0$ and $n=1$, which are trivial to prove
Inductive step: For any non-negative integer $k$, $P(k) \implies P(k+1)$.
What should I do now? I've wrote the simple parts of the proof but can't seem to get the inductive step right. Any help is appreciated.
Best Answer
Take $n\ge 2$.
For strong induction, assume $ a_k\equiv 6 a_{k-2}$ for all $k$ between $2 $ and $n+1$.
Now $a_{n+2}=a_{n+1}+a_{n}$, and by strong induction $a_{n+1}\equiv6a_{n-1}$ and $a_{n}\equiv6a_{n-2}$.
Therefore, $a_{n+2}\equiv6a_{n-1}+6a_{n-2}=6a_n.\square $