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?

This proof may not qualify as elementary, as it uses some algebraic number theory.
Let $R=\mathbb{Z}[(1+\sqrt{5})/2]$, the ring of integers of $\mathbb{Q}(\sqrt{5})$, and define $\alpha:=(1+\sqrt{5})/2$ and $\beta:=(1-\sqrt{5})/2\in R$. The binomial theorem implies
$$
\begin{align*}
S_n:=
{n\choose 1}+5{n\choose 3}+25{n\choose 5}\ldots&=\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2\sqrt{5}}\\
&=2^{n-1}\frac{\alpha^n-\beta^{n}}{\sqrt{5}}.
\end{align*}
$$
Now $2$ and $\sqrt{5}$ are coprime, so $2^{n-1}$ must divide $S_n$ in $R$. But the only rational numbers in $R$ are integers, so $2^{n-1}$ divides $S_n$ as integers.
