Bernoulli trials (n,p) - probability for even/odd number of successes 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} $$ 
 A: 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}.$$
A: 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].
$$
A: 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}$
