# Congruences and second-order recurrence relations

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.

• Please fix the typos in the definition of your sequence. – darij grinberg May 13 at 6:26

## 1 Answer

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.

• I guess you're applying induction on $n$. Your induction hypothesis would be $a_n \equiv 3^n \pmod 5, a_{n+1} \equiv 3^{n+1} \pmod 5$. And you'd be then proving that $a_{n+2} \equiv 3^{n+2} \pmod 5$. But can you always treat the indices of the terms as bases for induction? – ydnfmew May 13 at 6:40
• @ydnfmew Yes, that is correct. – Peter Foreman May 13 at 6:43