Let $X \text{~} \text{Binomial}(n, p)$.
What is $\text{P}[X \mod 2 = 0]$? Is it of the form $1/2 + O(1/2^n)$?
Let $X \text{~} \text{Binomial}(n, p)$. What is $\text{P}[X \mod 2 = 0]$? Is it of the form $1/2 + O(1/2^n)$? 


This probability is in fact $1/2 + (12p)^n/2$. Here's a proof. The probability generating function of $X$ is $f(z) = (q+pz)^n$, where $q = 1p$. That is, the coefficient of $z^k$ in $(q+pz)^n$ is the probability $P(X=k)$. Now, consider $(f(z)+f(z))/2$. This polynomial contains just the terms of $f(z)$ which contain $z$ to some even power. If we set $z = 1$, then we get just the sum of those terms. So the probability you want is $(f(1)+f(1))/2$. For example, if $n = 3$ we have $$f(z) = q^3 + 3 p q^2 z + 3 p^2 q z^2 + p^3 z^3$$ $${f(z) + f(z) \over 2} = q^3 + 3 p^2 q z^2$$ $${f(1) + f(1) \over 2} = q^3 + 3 p^2 q$$. Now, we have $$ {f(1) + f(1) \over 2} = {(q+p)^n + (qp)^n \over 2} = {1 + (12p)^n \over 2} $$ which is the result. 


The effect of adding a Bernoulli$(p)$ on the parity applies this matrix $$M=\left(\begin{array}{cc} 1p & p \\\ p & 1p \end{array}\right)$$ to $(prob(even), prob(odd))$. We can decompose the initial vector of $(1,0)$ for Binomial$(0,p)$ as the sum of the eigenvectors $(1/2,1/2)$ and $(1/2,1/2)$ with eigenvalues $1$ and $12p$, respectively. So, the parity vector of Binomial$(n,p)$ is $(1,0)M^n = 1^n (1/2,1/2) + (12p)^n (1/2,1/2)$. $1/2 + (12p)^n /2$ even, $1/2  (12p)^n / 2$ odd. 


Some general remarks. There is a family of linear operators $\phi_{a,d}$ which, given a generating function $f(x) = \sum f_n x^n$, returns the generating function $\sum f_{an+d} x^n$. Observe that, for $\zeta$ a primitive $a^{th}$ root of unity, $$f(\zeta^k x) = \sum_{i=0}^{a1} \zeta^{ki} \phi_{a,i}(f(x)).$$ This is precisely the discrete Fourier transform matrix of order $a$, and inverting it tells us how to write down these operators $\phi_{a,d}$ explicitly and in particular to compute all sums of the form $\displaystyle \sum {n \choose ak+d}$; this case is $a = 2, d = 0$. In this particular case there is a dirty trick I like to employ. Given a generating function $f(x) = \sum f_n x^n$, the generating function $g(x) = \sum g_n x^n$ where $$g_n = \sum_{k=0}^{n} {n \choose k} f_k$$ satisfies $$g(x) = \frac{1}{1  x} f \left( \frac{x}{1  x} \right).$$ One may deduce this using the Laplace transform, finite differences, or a combinatorial argument. It allows us to evaluate the sums $\displaystyle \sum {n \choose ak+d}$ by setting $f(x) = \frac{x^d}{1  x^a}$. Finally, there is a nice interpretation of the above sums in graphtheoretic terms. Consider the family of undirected cyclic graphs $C_a$, consisting of $a$ vertices arranged in a regular $a$gon with an edge between adjacent vertices. Labeling the vertices $0, 1, 2, ... a1$, the probability of starting at vertex $0$ and ending at vertex $2da$ in $n$ steps is precisely $$\frac{1}{2^n} \sum {n \choose ak+d}.$$ This is because a choice of whether to move left or right for each of the $n$ steps determines a subset of $\{ 1, 2, ... n \}$ whose cardinality $\bmod a$ determines your final location. Now one can compute these probabilities by computing the eigenvalues of the adjacency matrix of $C_a$ and even compute mixing times using standard graphtheoretic techniques. (Of course one may reintroduce the parameter $p$ into the adjacency matrix to model a random walk in which preference is given to moving to the left or right.) 

