Prove that $\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+...=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+...$

Question

Prove that $\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+...=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+...$ using a combinatorial approach, NOT an algebraic approach.

Fot values of $n$ which are odd this is simple, using Pascal's identity and/or Pascal's triangle, but I am not sure how to approach this for even values of $n$. Thank you for your help.

Answer 1

Consider bit strings of length $n$.

The left-hand side is counting the number of such strings that have even parity (the sum of the bits is even), the right-hand side is counting those that have odd parity.

We can look at this another way. Say we have a given string of length $(n-1)$. Whatever parity it has, we can add another bit to make it even, or to make it odd.

That shows that the number of strings of length $n$ with even parity must be the same as the number of strings of length $n$ with odd parity.

Answer 2

Counting bit strings works fine, but you might prefer to think in terms of counting subsets of $[n]=\{1,2,\ldots,n\}$. Let $\mathscr{E}$ be the set of subsets of $[n]$ of even size and $\mathscr{O}$ the set of subsets of $[n]$ odd size; the lefthand side is $|\mathscr{E}|$, and the righthand side is $|\mathscr{O}|$. If $n$ is odd, consider the map $\varphi:\wp([n])\to\wp([n]):A\mapsto[n]\setminus A$ that takes each subset of $[n]$ to its complement: it takes each set in $\mathscr{E}$ to one in $\mathscr{O}$ and vice versa, so its restriction to $\mathscr{E}$ is a bijection to $\mathscr{O}$, and you’re done.

If $n$ is even, it’s a little trickier, but we can use a slightly more complicated version of the same idea. Let $\mathscr{E}_0=\{A\in\mathscr{E}:n\notin A\}$, $\mathscr{E}_1=\{A\in\mathscr{E}:n\in A\}$, $\mathscr{O}_0=\{A\in\mathscr{O}:n\notin A\}$, and $\mathscr{O}_1=\{A\in\mathscr{O}:n\in A\}$. Since $n-1$ is odd, the restriction of $\varphi$ to $\mathscr{E}_0$ is a bijection between $\mathscr{E}_0$ and $\mathscr{O}_0$, so all that we need now is a bijection between $\mathscr{E}_1$ and $\mathscr{E}_1$. And that’s actually ready to hand: the map that takes $A\in\mathscr{E}_1$ to $\{n\}\cup\varphi(A\setminus\{n\})$ works. Given an even sized subset of $[n]$ that contains $n$, it first removes $n$ to get an odd-sized subset of $[n-1]$, takes the complement of that set in $[n-1]$ to get an even-sized set, and then restores $n$ to the set to get an odd-sized subset of $[n]$. I’ll leave it to you to check that this really is the desired bijection.

Answer 3

Let $f$ from the set of subsets of $[n]$ with an odd number of elements to the set of subsets of $[n]$ with an even number of elements, defined by the following rule:

Given $S\subseteq [n],$ \begin{equation} f(S)=\begin{cases} S\cup \{1\} & if 1\notin S \\ S\setminus \{1\} & if 1 \in S\\ \end{cases} \end{equation} $f$ is clearly a bijection as $f^{-1}:$even ordered subsets $\mapsto$odd ordered subsets, defined by the same rule as $f$. Clearly, $f\circ f^{-1}=$identity function on the set of subsets with an even number of elements, and $f^{-1}\circ f=$identity function on the set of subsets with an odd number of elements.

Thus the identity holds.