# Prove that $\sum_{i=0}^n2^{3i} \binom {2n+1}{2i+1}$ is never divisible by 5

• Question : Prove that the number is never divisible by 5.
-
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

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}}.$$

-

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

-
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.$$

-