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.
  • Question : Prove that the number alt text is never divisible by 5.
share|improve this question
2  
What have you tried? –  Qiaochu Yuan Jan 4 '11 at 11:18
    
Why those tags? –  lhf Jan 4 '11 at 11:36
    
A hint (although I haven't tried this in detail): call this number $f(n)$. Then $f(n)$ might satisfy some linear recurrence. Plug integers mod 5 into this recurrence and see what happens. –  Michael Lugo Jan 4 '11 at 14:57
    
@Michael Lugo, Yup, that approach works. –  Oscar Cunningham Jan 4 '11 at 15:01
    
f(n) has to satisfy a linear recurrence, but there are easier ways to do this problem. Again, what have you tried? –  Qiaochu Yuan Jan 4 '11 at 15:53
add comment

3 Answers

Since it has already been established in the comments that a linear recurrence will do the job, here's a brief outline of that method that I hope doesn't give away too much.

Working mod $5,$ we set $a_n = \sum_{i=0}^n 3^i { 2n+1 \choose 2i+1},$ so that $a_0=1$ and $a_1=6,$ and show that $a_n$ satisfies the linear recurrence

$$a_n = 8a_{n-1} - 4a_{n-2}, \quad n \ge 2,$$

from which it follows that $a_n,$ and thus the sum in the question, is never congruent to zero mod $5$.

EDIT: To add some more detail note that

$$ a_n = \sum_{i=0}^n 3^i { 2n+1 \choose 2i+1} = \frac{(\sqrt{3}+1)^{2n+1} + (\sqrt{3} - 1)^{2n+1}}{2\sqrt{3}}.$$

share|improve this answer
add comment

This problem has appeared in IMO 1974 test. The solution may be found here:

share|improve this answer
    
That's a surprise to me! I also see that someone mentions on this link the linear recurrence solution in my answer, though their recurrence is slightly different with larger coefficients as they didn't work mod $5$ initially. –  Derek Jennings Jan 5 '11 at 13:21
add comment

Set $S(n)=\sum_{i=0}^n 2^{3i} {2n+1\choose 2i+1}$, using Zeilberger's algorithm, we can find the recurrence $$S(n+2)=18S(n+1)-49S(n),\quad n\ge0,$$ with initial value $S(0)=1$ and $S(1)=11$. Mod $5$ both sides, we have $$S(n+2) \equiv_5 3S(n+1)+S(n),\quad n\ge0,$$ with initial value $S(0)\equiv_5 S(1)\equiv_5 1$. It is easy to see that $$S(12k)\equiv_5 S(12k+1)\equiv_5 S(12k+8)\equiv_5 1,$$ $$S(12k+5)\equiv_5 S(12k+9)\equiv_5 S(12k+10)\equiv_5 2,$$ $$S(12k+3)\equiv_5 S(12k+4)\equiv_5 S(12k+11)\equiv_5 3,$$ $$S(12k+2)\equiv_5 S(12k+6)\equiv_5 S(12k+7)\equiv_5 4.$$

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