What is the combinatorial interpretation for this expression$ \sum_{i=0}^{n} (-1)^{i} \binom{n}{i} = 0$

71 Views Asked by At

What is the combinatorial interpretation for this expression $$\sum_{i=0}^{n} (-1)^{i} \binom{n}{i} = 0\:?$$

1

There are 1 best solutions below

0
On BEST ANSWER

This says that there are the same number of ways to choose 1) an even number of things, or 2) an odd number of things, from a set of $n$ distinct objects.

Case I) This is easy to see, by symmetry, if $n$ is odd.

Case II) If $n$ is even, can you see an argument for it? Spoiler below.

Fix one arbitrary object ("the first object"), and take two cases. Case 1: Choose the first object. Now, an odd number of $n-1$ objects remain, so follow Case I). Case 2: Do not choose the first object. Then follow Case I) again.