Combinatorics floor summation $\sum_{i=0}^{\lfloor n/2\rfloor}\binom n{2i}p^{2i}(1-p)^{n-2i}=\frac12((2p-1)^n+1)$

Question

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?

Answer 1

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$.

Answer 2

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.