1
$\begingroup$

Give a combinatorial proof of

$${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$$


In first of all, I know how to proof directly. We move all terms to left hand side of equation. And we get $(1-1)^n = 0^n = 0$, and we are done. Also I saw here several topics about this, but it never were about the combinatorial proof.

I want this prove combinatorial. I have no idea of question, which will be correctly answered from both side of equation. Thank you for all hints.

$\endgroup$
  • 2
    $\begingroup$ Let $[n]=\{1,2,\ldots,n\}$. The left hand side counts subsets of $[n]$ with an odd number of elements, while the right hand side counts subsets of $[n]$ with an even number of elements. How could you go from one to the other and back? $\endgroup$ – Kevin Long Jan 28 at 19:13
3
$\begingroup$

Let's call a set even if it has an even number of elements and odd if it has an odd number of elements. As @KevinLong stated in the comments, the LHS counts the number of odd subsets of $n$ elements and the RHS counts the number of even subsets of $n$ elements.

Let's call the $n$ element set we're dividing up $N$. Fix some arbitrary element $x \in N$. We can partition the set of subsets of $N$ by whether they include $x$. For any subset of $N$ which includes $x$, there is exactly one subset of $N$ with all the same elements but without $x$. Likewise, for any subset of $N$ which does not include $x$, there is exactly one subset of $N$ with all the same elements but also including $x$.

Let's call any two subsets of $N$ that are related in this way (i.e. one can be obtained from the other by adding/removing $x$) a corresponding pair. Note that every subset of $N$ is a member of exactly one corresponding pair. Also, in any corresponding pair one of the sets is even and the other is odd. Therefore, the number of even subsets and the number of odd subsets is the same, so LHS = RHS.

$\endgroup$
  • $\begingroup$ Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set $\{1,2,3,\cdots\}$. We are dividing up $N$, for example $N = \{1, 3, 4\}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: $\{1\}, \{1, 3\}, \{1, 4\}, \{1,3,4\}$; second that do not contain $1$: $\emptyset, \{3\}, \{4\}, \{3,4\}$. These subsets are differ only by element $1$. Correct me, if I am wrong. $\endgroup$ – Kapur Jan 28 at 20:06
  • $\begingroup$ @Kapur $N$ is just any $n$ element set. For simplicity we can say it is $\{1, 2, \ldots, n\}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem. $\endgroup$ – Alex Jan 28 at 20:12
  • $\begingroup$ Now, it seems better. $\endgroup$ – Kapur Jan 28 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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