5
$\begingroup$
  • Question : Prove that the number alt text is never divisible by 5.
  • 0
    f(n) _has to_ satisfy a linear recurrence, but there are easier ways to do this problem. Again, what have you tried?2011-01-04

3 Answers 3

4

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

2

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

  • 0
    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.2011-01-05
1

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