Prove that $2^{n-1}$ divides $\binom{n}{1} + \binom{n}{3}5 + \binom{n}{5}25 + \binom{n}{7}125 + \cdots$ for $n \geqslant 1$. Prove that $2^{n-1}$ divides $\binom{n}{1} + \binom{n}{3}5 + \binom{n}{5}25 + \binom{n}{7}125 + \cdots$ for $n \geqslant 1$.
Assume $\binom{n}{k} = 0$ if $k>n$.
Does anyone know an elementary proof without using the Binet formula?

Note that $\binom{n-2}{j-1}+2\binom{n-2}{j}+\binom{n-2}{j+1}=\binom{n}{j+1}$.  Define
$$
g(n)=\sum_j \binom{n}{2j+1}\cdot5^j.
$$
Then
$$
\begin{aligned}
4g(n-2)+2g(n-1)&=4\sum_j\binom{n-2}{2j+1}\cdot5^j+2\sum_j\binom{n-1}{2j+1}\cdot5^j\\
&=(5-1)\sum_j\binom{n-2}{2j+1}\cdot5^j+2\sum_j\left[\binom{n-2}{2j}+\binom{n-2}{2j+1}\right]\cdot5^j\\
&=\sum_j\binom{n-2}{2j+1}\cdot5^{j+1}+2\sum_j\binom{n-2}{2j}\cdot5^j+\sum_j\binom{n-2}{2j+1}\cdot5^j\\
&=\sum_j\left[\binom{n-2}{2j-1}+2\binom{n-2}{2j}+\binom{n-2}{2j+1}\right]\cdot5^j\\
&=\sum_j\binom{n}{2j+1}\cdot5^j\\
&=g(n).
\end{aligned}
$$
So $g(n)=2g(n-1)+4g(n-2)=2\left[g(n-2)+2g(n-2)\right]$ with the initial conditions $g(1)=1$, $g(2)=2$.  The result follows by induction.
It would be satisfying to interpret this calculation combinatorially.  I'll think about this.
