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?

Thanks a lot for your help, in advance!

  • $\begingroup$ Try mathematical induction. $\endgroup$ – user96614 Oct 11 '13 at 3:56
  • $\begingroup$ Try showing that $a_n \equiv (-1)^n \pmod{3}$. $\endgroup$ – Calvin Lin Oct 11 '13 at 4:03
  • $\begingroup$ But shouldn't I find first the general term for $a_n$? And that's what I cannot find... :S $\endgroup$ – pmartelletti Oct 11 '13 at 4:05
  • $\begingroup$ @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. $\endgroup$ – user96614 Oct 11 '13 at 14:15
  • $\begingroup$ 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 $\endgroup$ – 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.


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.