Suppose that there are \(n\) distinguishable objects numbered \(1,2,\ldots,n\). We want to pick a non-empty subset of them. Call a subset odd or even according to their cardinality.

Positive terms count the number of ways to choose an odd number of objects (the terms are \(\binom{n}{1}, \binom{n}{3}, \binom{n}{5}, \ldots\)). Negative terms count the number of ways to choose an even number of objects (the terms are \(\binom{n}{2}, \binom{n}{4}, \binom{n}{6}, \ldots\)).

Now distinguish object \(n\). For any subset \(S\) picked among the remaining \(n-1\) objects, we obtain two subsets for the \(n\) objects: \(S\) and \(S \cup \{n\}\). One of these is odd and the other is even, so there are the same number of odd subsets as there are even subsets...except that when \(S\) is empty, \(S\) is not a valid subset but \(S \cup \{n\}\) is, so this exception increments the number of odd subsets without incrementing the even one. So there is 1 more odd subset, which is exactly what the identity is.

I'll leave the solution with Pascal's Triangle to others.

## Comments

Sort by:

TopNewestHow many ways can you prove the identity?

Can you use an algebraic method? Can you use a combinatorial method? Can you find a pattern? Can you relate it to Pascal's Triangle?

Log in to reply

Sum from 0, use the Binomial expansion for (1-1)^n

Log in to reply

Solution 1Expand \((1-1)^n\) according to the binomial theorem. We obtain

\(\displaystyle\sum_{r=0}^n (-1)^r \binom{n}{r} = 0\)

\(\displaystyle\sum_{r=0}^n (-1)^{r-1} \binom{n}{r} = 0\)

\(\displaystyle\sum_{r=1}^n (-1)^{r-1} \binom{n}{r} + (-1)^{0-1} \binom{n}{0} = 0\)

\(\displaystyle\sum_{r=1}^n (-1)^{r-1} \binom{n}{r} + (-1) \cdot 1 = 0\)

\(\displaystyle\sum_{r=1}^n (-1)^{r-1} \binom{n}{r} = 1\)

Solution 2Suppose that there are \(n\) distinguishable objects numbered \(1,2,\ldots,n\). We want to pick a non-empty subset of them. Call a subset odd or even according to their cardinality.

Positive terms count the number of ways to choose an odd number of objects (the terms are \(\binom{n}{1}, \binom{n}{3}, \binom{n}{5}, \ldots\)). Negative terms count the number of ways to choose an even number of objects (the terms are \(\binom{n}{2}, \binom{n}{4}, \binom{n}{6}, \ldots\)).

Now distinguish object \(n\). For any subset \(S\) picked among the remaining \(n-1\) objects, we obtain two subsets for the \(n\) objects: \(S\) and \(S \cup \{n\}\). One of these is odd and the other is even, so there are the same number of odd subsets as there are even subsets...except that when \(S\) is empty, \(S\) is not a valid subset but \(S \cup \{n\}\) is, so this exception increments the number of odd subsets without incrementing the even one. So there is 1 more odd subset, which is exactly what the identity is.

I'll leave the solution with Pascal's Triangle to others.

Log in to reply