# Proving a combinatorial identity $\sum_{i = 0}^{[n/2]} \binom{n}{2i} p^{2i}q^{n-2i} = \frac{1}{2}\left[(p+q)^n + (q-p)^n \right]$

I would really appreciate some help with proving following identity. I've been trying for the whole day to no avail.

$$\sum_{i = 0}^{[n/2]} \binom{n}{2i} p^{2i}q^{n-2i} = \frac{1}{2}\left[(p+q)^n + (q-p)^n \right]$$

Where by$\ [n/2]$ we mean the largest integer less than or equal to $\ n/2$. Also $\ q = 1 - p$

This question is a step in a probability problem that i'm solving hence the $\ q = 1 - p$.

• Have you tried expanding both $(q+p)^n$ and $(q+(-p))^n$ using the binomial theorem? – dtldarek Sep 14 '13 at 18:58
• Please, use $\large\left\lfloor n/2\right\rfloor$ instead of $\large\left\lbrack n/2\right\rbrack$. – Felix Marin Sep 14 '13 at 19:13

Expand the righthand side:

\begin{align*} \frac12\left((p+q)^n+(-p+q)^n\right)&=\frac12\left(\sum_{k=0}^n\binom{n}kp^kq^{n-k}+\sum_{k=0}^n\binom{n}k(-1)^kp^kq^{n-k}\right)\\\\ &=\frac12\sum_{k=0}^n\binom{n}k\left(1+(-1)^k\right)p^kq^{n-k}\\\\ &=\frac12\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}k2p^{2k}q^{n-2k}\\\\ &=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}kp^{2k}q^{n-2k}\;, \end{align*}

since $$1+(-1)^k=\begin{cases}2,&\text{if }k\text{ is even}\\0,&\text{if }k\text{ is odd}\;.\end{cases}$$

From $$(q\pm p)^n=\sum_{j=0}^n{n\choose j}(\pm 1)^{j}p^jq^{n-j}$$ we see that adding both sums cancels all terms with odd $j$. After halving the sum and replacing even $j$ with $2i$, we obtain the desired result.

Suppose we don't have the RHS. Write:

$$f(z) = \sum_k \binom{n}{k} p^{n - k} z^k = (p + z)^n$$

We essentially want the even terms of this for $z = q$. For any series $f(z)$ you get the even terms by $(f(z) + f(-z)) / 2$ (and odd ones through $(f(z) - f(-z)) / 2$):

\begin{align} \sum_i \binom{n}{2 i} p^{n - 2 i} z^{2 i} &= \frac{f(z) + f(-z)}{2} \\ &= \frac{1}{2} \left( (p + z)^n + (p - z)^n \right) \end{align}

With $z = q$ you get the claim.