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?
–
Best of Combinatorics
Staff
·
3 years, 3 months ago

Log in to reply

Sum from 0, use the Binomial expansion for (1-1)^n
–
Bob Smith
·
3 years, 3 months ago

Log in to reply

Solution 1

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

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.
–
Ivan Koswara
·
3 years, 3 months ago

## 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? – Best of Combinatorics Staff · 3 years, 3 months ago

Log in to reply

Sum from 0, use the Binomial expansion for (1-1)^n – Bob Smith · 3 years, 3 months ago

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. – Ivan Koswara · 3 years, 3 months ago

Log in to reply