Combinatorics floor summation $\sum_{i=0}^{\lfloor n/2\rfloor}\binom n{2i}p^{2i}(1-p)^{n-2i}=\frac12((2p-1)^n+1)$ While solving a problem I came across a rather interesting identity, and I do not see how I could prove it.
$$\sum_{i=0}^{\lfloor n/2\rfloor}\binom n{2i}p^{2i}(1-p)^{n-2i}=\frac12((2p-1)^n+1)$$
Any ideas?
 A: Let $q=1-p$. Apply the binomial theorem twice, then add:
\begin{array}{rrl}
&(p+q)^n&=\;\;\sum_{i=0}^n \binom{n}ip^iq^{n-i}\\
+&(-p+q)^n&=\;\;\sum_{i=0}^n \binom{n}i(-p)^iq^{n-i}\\\hline
&(p+q)^n+(-p+q)^n &=2\sum_{i=0}^{\lfloor n/2\rfloor}\binom{n}{2i}p^{2i}q^{n-2i}
\end{array}
To understand the RHS of the sum, note when $i$ is odd we have $p^i+(-p)^i=0$, while when $i$ is even, $p^i+(-p)^i=2p^i$. Replacing $q$ with $1-p$ makes the LHS $1+(1-2p)^n$.
A: With the corrected RHS of $\frac12((1-2p)^n+1)$ and Austin Mohr's interpretation of the LHS as the probability of an even number of heads occurring in $n$ tosses of coin which comes up heads with probability $p$, the result is easily established by induction.
Case $n = 0$:  $\frac12((1-2p)^0+1) = 1$, which is correct since zero tosses always produce zero heads.
Case $n > 0$:  An even number of heads after $n$ tosses occurs either by having an even number of heads in $n-1$ tosses followed by tails, or an odd number in $n-1$ tosses followed by heads.  The probability of this is
$$
\begin{align}
&\frac12((1-2p)^{n-1}+1)(1-p) + (1 - \frac12((1-2p)^{n-1}+1))\cdot p\\
&= \frac12(1-2p)^{n-1}(1-p-p) +\frac12(1-p-p) + p\\
&= \frac12((1-2p)^n + 1),
\end{align}
$$
as required.
