# Proving a combinatorial identity

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

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

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

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