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
    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!2012-10-02
  • 0
    @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$.2012-10-04
  • 0
    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)2012-10-04
  • 0
    @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.2012-10-04
  • 0
    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?2012-10-04
  • 0
    @finial: No, $a_3\equiv-2\pmod{11}$, and I inadvertently dropped the minus sign. I’ve now recalculated; do we agree? By the way, it’s easier if you do the reductions $\bmod 11$ as you go. For instance, I calculated the $n=7$ entry as $8\cdot4-7\cdot 10=32-70=-38$, then added $44$ to get $6$.2012-10-04
  • 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