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.

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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