How would I approach solving this problem. Could someone direct me in the right direction?
Prove: $$\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dots = \binom{n}{1} + \binom{n}{3} + \binom{n}{5}.$$
I can't seem to find the right identity to start on this.
On
Let $$E = {n\choose 0}+ {n\choose 2} + {n\choose4} + ...$$
and
$$O = {n\choose 1} + {n\choose 3}+ {n\choose 5}$$
then by binomial theorem we have $$E-O = {n\choose 0}-{n\choose 1}+{n\choose 2}-{n\choose 3}+ {n\choose 4}... =(1-1)^n =0$$
On
We will count the number of subsets of even size of $[n] = \{1, 2,\ldots,n\}$. Fix $n-1$ elements of $[n]$ and choose an arbitrary subset $S$ of these $n-1$ elements. If this subset has an even number of elements, then we have a subset of $[n]$ of even size. Otherwise, $|S|$ is odd, we add the $n$th element, which was not chosen above, to obtain a subset of $[n]$ of even size.
Therefore, we have a bijection between the set of all subsets of $[n-1]$ and the set of all subsets of even size of $[n]$. Hence the cardinalities of these two sets are equal. Thus, there are $2^{n-1}$ subsets of $[n]$ of even size.
Note that in the given equation, the L.H.S. is the number of subsets of even size of $[n]$, the R.H.S. is the number of subsets of odd size. From that, we obtain the given identity.
\begin{align} 0 = (1 - 1)^n &= \sum_{i = 0}^n \binom{n}{i} (-1)^i \tag{binomial theorem} \\ &= \sum_{\substack{i = 0 \\[0.3ex] i \text{ odd}}}^n \binom{n}{i} (-1) + \sum_{\substack{i = 0 \\[0.3ex] i \text{ even}}}^n \binom{n}{i} \\ \end{align} Group the terms according to the parity of $i$. Rearranging gives the desired equality. $$\sum_{\substack{i = 0 \\[0.3ex] i \text{ odd}}}^n \binom{n}{i} = \sum_{\substack{i = 0 \\[0.3ex] i \text{ even}}}^n \binom{n}{i}$$