# Prove divisibility for general equation of sucession

I have the following problem:

Prove that given the following succession:

$a_1 = 2, a_2 = 4, a_{n+2} = (n+1)a_{n+1} + (n-1)a_n, \forall n \in \mathbb{N}$

then, it follows that $\forall n \in \mathbb{N}, 3 | a_n + (-1)^{n-1}$

So, what I begin doing is trying to figure out the general term, $a_n$, for the sucession, so then I would be able to proove what I'm asked for.

But, the thing is.. I can't figure out the general term of $a_n$...I did the following:

$a_1= 2, a_2 = 4$

$a_3 = 2 \cdot 4 + 0 \cdot 2 = 8$

$a_4 = 3 \cdot 8 + 1 \cdot 4 = 28$

$a_5 = 4 \cdot 28 + 2 \cdot 8 = 128$

$a_6 = 5 \cdot 128 + 3 \cdot 28 = 724$

... and so on. So, I got the following sequence:

$4,8,28,128, 724$

But I cannot figure out which the general term is, in order to proove the second statement. Any ideas from where should I follow? Or if the exercicse did not intend me to go and search the general term $a_n$, but to go in a very differente way?

• Try showing that $a_n \equiv (-1)^n \pmod{3}$. – Calvin Lin Oct 11 '13 at 4:03
• But shouldn't I find first the general term for $a_n$? And that's what I cannot find... :S – pmartelletti Oct 11 '13 at 4:05
• @pmartelletti You don't need to characterize the general term if all you need to show is that the terms follow a certain property. Check Calvin's assertion for $n=1,2$ and then use the recurrence relation to show that if it holds for $n-1$ and $n$, it must hold for $n+1$. Finally, show that the relation you have to prove follows from Calvin's assertion. – user96614 Oct 11 '13 at 14:15
• Oh, I get the idea now! The question is.. how did you get the $a_n \equiv (-1)^n \pmod{3}$ from $3|a_n + (-1)^{n-1}$ formula? Now I'm missing that part...:S – pmartelletti Oct 11 '13 at 15:39
One of the nice things about reduction modulo$~n$ is that it preserves arithmetic relations (the technical term is that it is a homomorphism of rings). Here this means that if you reduce every term modulo$~3$, then you get a sequence of elements $\overline a_i$ of $\Bbb Z/3\Bbb Z$ that satifies the corresponding recurrence $\overline a_{n+2} = \overline{(n+1)}\overline a_{n+1} + \overline{(n-1)}\overline a_n$ in $\Bbb Z/3\Bbb Z$, and has initial conditions $\overline a_1 = \overline 2$ and $\overline a_2 = \overline 4=\overline 1$. Since only finitely many values for the entries are now possible, and the coefficients $\overline{(n+1)}$, $\overline{(n-1)}$ of the equation have periodic behaviour, the sequence $(\overline a_i)_{i\in\Bbb N}$ is bound to become periodic. It should be easy to find out the period, and from that to find an expression for $\overline a_i$ valid fro all $i$. This in turn should make proving your claim very straightforward.