# Find all $n \in N$ such that $11 | a_n$, with the following sequence defined

$\{a_n\}_{n \in \Bbb N}$ with $a_1=1, a_2=3$

and for $n \ge 1$:

$a_{n+2} = (n+3)a_{n+1}-(n+2)a_n$

as the title states, find all $n \in \Bbb N$ such that $11 | a_n$

-

Edit: I originally computed the table from the incorrect value $a_2=2$. Fortunately, finial caught this, and I’ve recomputed it with the correct initial value, modifying the rest of the hint accordingly.

HINT: If you calculate the first few values of $a_n\bmod 11$, you get this:

$$\begin{array}{r|c} n:&1&2&3&4&5&6&7&8&9&10&11&12&13\\ \hline a_n:&1&3&9&0&10&4&6&0&1&0&0&0&0 \end{array}$$

That string of $0$’s should suggest a conjecture: $a_n\equiv 0\pmod{11}$ for $n\ge 10$. Since the $a_n$’s are defined by a recurrence, induction is the natural choice for a method of proof.

-
thank you very much for the hint, i will work it out and see what i get later on, will come back to you very soon! – fmat Oct 2 '12 at 8:04
@finial: Thanks for catching the typo for $a_2$. It threw off the rest of the table as well, though not the fact that the terms are constant $\bmod 11$ for $n\ge 10$. – Brian M. Scott Oct 4 '12 at 0:25
I am intrested on your approach, did you just wrote up the first ~10 terms to see whats happennig here ? did anything tiped you off ? (+1) – Belgi Oct 4 '12 at 1:07
@Belgi: When I encounter a recurrence that I’ve not seen before, I almost always begin by calculating a few values, just to get a feel for what’s happening. In this case it was natural to compute them $\bmod 11$, and of course as soon as I got the same value twice in a row, the answer was clear. – Brian M. Scott Oct 4 '12 at 1:11
So I am a bit not sure how our values don't match But here I start with $a_1 = 1$ and $a_2 = 3$ and I have: $a_3 = 9$ $\Rightarrow$ $a_3 \equiv 9\pmod {11}$ $a_4 = 33$ $\Rightarrow$ $a_4 \equiv 0\pmod {11}$ $a_5 = 153$ $\Rightarrow$ $a_5 \equiv 10\pmod {11}$ $a_6 = 873$ $\Rightarrow$ $a_6 \equiv 4\pmod {11}$ $a_7 = 5913$ $\Rightarrow$ $a_7 \equiv 6\pmod {11}$ and so on Is there anything that I did wrong? – fmat Oct 4 '12 at 4:59

HINT: If you let $b_n=a_n-a_{n-1}$ you find that $$b_{n+2}=(n+2)b_{n+1}$$

We have $b_2=2$ (the first defined value) and it is then easy to see (and prove) a simple formula for $b_n$.

You still have a little work to do, and the idea of working modulo 11 may be quicker, but this is another way of seeing what is happening.

-
How did you know to define $b_n$ in this manner ? did you do some calculation or something ? – Belgi Oct 4 '12 at 0:28

By calculation, we can get that $a_{n}=1!+2!+\cdots+n!$, as $11|k!$ for $k\geq11$,and $11|(9!+10!)$ ($9!+10!=11\cdot9!$), you can only check them for $n=1,2,\cdots,10$, and that $a_{n}$ is divisible by 11 or not for $n\geq11$ follows from that $a_{8}$ (or $a_{10}$) is divisible by 11 or not.

-
You provided a really good point there that we only need to check for $n = 1, 2, ..., 10$. Thank you very much! – fmat Oct 4 '12 at 5:10