Waste less time on Facebook — follow Brilliant.
×

Prove this

Prove that \(\sum_{r=1}^n\) \((-1)^{r-1} \times nCr\) = 1

Note by Selena Miller
3 years, 10 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

How 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, 10 months ago

Log in to reply

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

Bob Smith - 3 years, 10 months ago

Log in to reply

Solution 1

Expand \((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 2

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, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...