1
$\begingroup$

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.

$\endgroup$
1

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ So are you saying that $\binom{n}{k}=\binom{n}{k\pm1}$??? $\endgroup$ Oct 1, 2020 at 16:20
  • $\begingroup$ No. I'm saying that ${n-1 \choose k-1} + {n-1 \choose k} = {n \choose k}$. $\endgroup$ Oct 1, 2020 at 16:35
  • $\begingroup$ Ok...I'm not sure where in your answet you're saying that :( The way I understand your answer: the total number of ways of choosing an odd lengthed string is the same as the number of ways of choosing an even lengthed string as for every combination of an odd lengthed string we can add on 1 more unit to make it even lengthed. Is that right? $\endgroup$ Oct 1, 2020 at 16:58
  • $\begingroup$ No: take a string of length $(n-1)$. If that string contains an even number of $1$s, we can add a $0$ to get a string of length $n$ that has an even number of $1$s, or we can add a $1$ to get a string containing an odd number of $1$s. Same if the string of length $(n-1)$ had an odd number of $1$s. $\endgroup$ Oct 1, 2020 at 17:09
  • $\begingroup$ Ok. Why doesn't the place where you add the extra 1 or 0 make a difference though? Because we're talking about combinations? $\endgroup$ Oct 1, 2020 at 17:15
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ My ignorance of sets is again the problem. Would you mind explaining what '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\}$.' means? $\endgroup$ Oct 1, 2020 at 18:12
  • $\begingroup$ @A-levelStudent: In general $\{x\in X:P(x)\}$ is the set of all members of $x$ for which $P(x)$ is true, so $\mathscr{E}_0$ is the set of all even-sized subsets of $[n]$ (i.e., members of $\mathscr{E}$) that do not contain $n$, and $\mathscr{E}_1$ is the set of all even-sized subsets of $[n]$ that do contain $n$. Does that help? $\endgroup$ Oct 1, 2020 at 18:15
  • $\begingroup$ Yes, that's excellent, thank you! $\endgroup$ Oct 1, 2020 at 18:19
  • $\begingroup$ @A-levelStudent: My pleasure! $\endgroup$ Oct 1, 2020 at 18:20
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.