An exercise for my stochastic processes class is asking me to prove that
\begin{equation} \sum_{k=0}^{\left \lfloor \frac{n-1}{2} \right \rfloor } \begin{pmatrix} n \\ 2k+1 \end{pmatrix} 5^k \end{equation}
is always an integer multiple of $(2^{n-1})$, that is
\begin{equation} \sum_{k=0}^{\left \lfloor \frac{n-1}{2} \right \rfloor } \begin{pmatrix} n \\ 2k+1 \end{pmatrix} 5^k = p(2^{n-1}), \quad p \in \mathbb{N}\end{equation}
Some identities which seem helpful for this situation but which I have not quite figured out how to apply are the following:
\begin{equation}\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} \lfloor n/2 \rfloor \\ \lfloor k/2 \rfloor \end{pmatrix}\begin{pmatrix} n \mod 2 \\ k \mod 2 \end{pmatrix} \mod 2 \end{equation}
and
\begin{equation} \sum_{k=0}^n k\begin{pmatrix} n \\ k \end{pmatrix} = n2^{n-1}\end{equation}
Could someone please suggest some identities that may be helpful or point me to a resource where I might find some useful identities?
The only identity you really need here is the binomial theorem: $$ \binom n0 + \binom n1 x + \binom n2 x^2 + \dots + \binom{n}{n-1}x^{n-1} + \binom nn x^n = (1 + x)^n. $$ By replacing $x$ with $-x$, we get: $$ \binom n0 + \binom n1 (-x) + \binom n2 (-x)^2 + \dots + \binom{n}{n-1}(-x)^{n-1} + \binom nn (-x)^n = (1 - x)^n. $$ You should ponder the relationship between these two sums and how you may use them to obtain the sum in your question, which only includes the odd terms.