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.

 A: 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}}.$$
A: This problem has appeared in IMO 1974 test. The solution may be found here:


*

*http://www.artofproblemsolving.com/Forum/viewtopic.php?p=358034&sid=4ec9cfb8d7c76cdfe71c058fc2f5c974#p358034
A: 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.$$
