1
$\begingroup$

$\{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$

3 Answers 3

5

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.

  • 0
    Oh yes definitely, now I have completely clear idea about this problem, as @AlfredChern suggested below, we can actually show that for $n \ge 11$ we always have 11 dividing $a_n$ since $11 \mid k!$ for $k \ge 11$, thank you very much2012-10-04
1

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.

  • 0
    How did you know to define $b_n$ in this manner ? did you do some calculation or something ?2012-10-04
1

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.

  • 0
    You provided a really good point there that we only need to check for $n = 1, 2, ..., 10$. Thank you very much!2012-10-04