Prove this

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

#Combinatorics

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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

bob smith - 7 years, 5 months ago

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 - 7 years, 5 months ago

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 - 7 years, 5 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$