Bernoulli trials (n,p) - probability for even/odd number of successes

Question

I came across this problem. It asks what is the probability of even number of successes in a series of $n$ Bernoulli trials with probability of success in each trial equal to $p \neq \frac{1}{2}$.

Knowing the formula for $k$ number of successes I was able to immediately write down this:

$$ p_{\ even} = \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k} p^{2k}(1-p)^{n-2k} $$

I think that is correct, right?

But after that when I saw the solution which they give in the book, I found (as I suspected by the way) that there's a closed form formula and it goes.

$$ p_{\ even} = \frac{1}{2} + \frac{1}{2} (1-2p)^{n}$$

The proof is simple, one basically argues inductively over $n$.

This made me think (and this is my question here)... Is there an algebraic way to prove the following equality? I mean some way which simply manipulates these binomial coefficients and uses some of their known properties.

$$ \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k} p^{2k}(1-p)^{n-2k} = \frac{1}{2} + \frac{1}{2} (1-2p)^{n} $$

Answer 1

Case 1: $n=2m$, then: $$\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k} p^{2k}(1-p)^{n-2k} = \sum_{k=0}^{m}{2m \choose 2k}p^{2k}(1-p)^{2m-2k} = \\ \frac12\left(((1-p)+p)^{2m}+((1-p)-p)^{2m}\right)=\frac12\left(1+(1-2p)^{2m}\right)=\frac{1}{2} + \frac{1}{2} (1-2p)^{n};$$ Case 2: $n=2m+1$, then: $$\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k} p^{2k}(1-p)^{n-2k} = \sum_{k=0}^{m}{2m+1 \choose 2k}p^{2k}(1-p)^{2m+1-2k} = \\ \frac12\left(((1-p)+p)^{2m+1}+((1-p)-p)^{2m+1}\right)=\frac12\left(1+(1-2p)^{2m+1}\right)=\frac{1}{2} + \frac{1}{2} (1-2p)^{n}.$$

Answer 2

A beautiful trick: look instead at Bernoulli random variables $X_1,\dots,X_n$ valued in $\{-1,1\}$. Then, by independence: $$ 2\cdot\mathbb{P}(\text{even #failures}) - 1 = \mathbb{E}[X_1 \times \dots \times X_n] = \mathbb{E}[X_1] \times \dots \times \mathbb{E}[X_n]. $$

Answer 3

Let $P_n$ denote the probability that $n$ Bernoulli trials results in an even number of successes. The following recurrence relation follows:

$P_n = p(1-P_{n-1})+(1-p)P_{n-1}$, $n\ge1$

$P_{1}=1-p$

Let us seek for the characteristic equation of the form $P_{n} = A+Bx^{n}$. If we substitute our ansatz into the recurrence relation we get

$Bx^{n} -p +2pA + 2pBx^{n-1} - Bx^{n-1} = 0$

Thus taking $A = 1/2$ together with the boundary condition $P_1$ we get the desired result

$P_n = \frac{1}{2} + \frac{1}{2}(1-2p)^{n}$