Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
  • Question : Prove that the number alt text is never divisible by 5.
share|cite|improve this question
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

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|cite|improve this answer

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

share|cite|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

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|cite|improve this answer

Your Answer


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.