I'm having trouble tackling this ghastly exercise.
Let $(a_n)_{n\in\mathbb{N}}:a_1=3,a_2=-1,a_{n+1}=a_{n+1}+4^{2n}a_n+15^n n^{15}$. Prove that $a_n \equiv 3^n \pmod 5$.
I know that every term in this sequence is congruent modulo 5 to the sum of the previous two terms in the sequence:
$$a_{n+2}=a_{n+1}+4^{2n}a_n+15^n n^{15} \equiv a_{n+1} + a_n \pmod 5$$
But I don't know how to find a explicit formula for $a_n$. Is it crucial to do so? [Edit: can I treat $(a_n)$ as equivalent to $(b_n): b_1=3,b_2=-1,b_{n+2}=b_{n+1}+b_n$ for the purposes of this exercise?]
Does this even require induction on $n$?
I'm grasping at straws here.
You already got $a_{n+2}\equiv a_{n+1}+a_{n}$(mod 5), but $3^{n+2}\equiv 3^{n+1}+3^n$ (mod 5) because $9-3-1=5$. Also $a_1=3^1$ and $a_2=-1\equiv 3^2$ (mod 5) thus we are done.