I ran into an exercise in a book that asked the following: Prove that
$$S(n) = \sum_{\ell=0}^{[n/2]}\binom{n}{2\ell}p^{2\ell}(1-p)^{n-2\ell} = \frac{1+(1-2p)^n}{2},$$
where $[x] =$ the floor function. I got stuck because expressing $a_{n+1}$ depends on whether or not $n$ is evevn or odd. How can induction even work in this case?
$$\begin{eqnarray*}2\cdot S(n)&=&\sum_{k=0}^{n}\binom{n}{k}p^k(1-p)^{n-k}+\sum_{k=0}^{n}\binom{n}{k}(-1)^k p^k(1-p)^{n-k}\\&=&(p+1-p)^n+(-p+1-p)^n = 1+(1-2p)^n.\end{eqnarray*}$$