IMC 2008 · Day 2 · P9

As is known, the Fibonacci numbers $F_n$ can be expressed as $F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right)$. Expanding this expression, we obtain that $F_n = \frac{1}{2^{n-1}} \left( \binom{n}{1} + \binom{n}{3} 5 + \dots + \binom{n}{l} 5^{\frac{l-1}{2}} \right)$, where $l$ is the greatest odd number such that $l \le n$ and $s = \frac{l-1}{2} \le n/2$.

So, $F_n = \frac{1}{2^{n-1}} \sum\limits_{k=0}^{s} \binom{n}{2k+1} 5^k$, which implies that $2^{n-1}$ divides $\sum\limits_{0 \le k < n/2} \binom{n}{2k+1} 5^k$.