Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
show 2 more comments

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.