1
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – ydnfmew May 13 at 6:40
  • 1
    $\begingroup$ @ydnfmew Yes, that is correct. $\endgroup$ – Peter Foreman May 13 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.