Best proof of $\displaystyle \sum^{n}_{k \text{ odd}} {n \choose{k}}=\sum^{n}_{k \text{ even}} {n \choose{k}}$

This is just a really quick note on the equality described above.

Let $E$ be the set of all ways we can choose an even number of objects, and $O$ the number of ways we can choose an odd number of objects.

First proof: 'Classic' proof

This is the classic one, in which we set up a bijection between the two sets. Given $n$ (different) objects, designate one object, say $x$, as the special one. The number of ways we can choose an even number of objects can be bijected to the number of ways we can choose an odd number by applying this transformation:

$\forall \space e \in \space E, \space e'= \begin{cases} e / \{x\} & x \in e \\ e \cup x & x \notin e \end{cases}$

Now the set of all $e'$ is the set of all the ways we can choose an odd number of elements. $\square$

Second proof: My own proof

(I think this may be an adaptation of the first proof.)

Imagine flipping a coin $n$ times (order matters). Then the number of ways I can get an even and odd total respectively is $|E|$ and $|O|$. But no matter what the total is after $n-1$ flips, the chance that I will get an even number of heads or an odd number of heads is the same! (why?) $\square$

Third proof: Again my proof but I bet it's already been thought of by somebody else

I hope everybody is familiar with the combinatorial method of representing Pascal's triangle, i.e the first row is $0 \choose{0}$, the second is $1 \choose 0$ $1 \choose 1$, etc. If you aren't then I'm sure somebody will explain it to you if you asked in the comments. So anyway we look at the $n^{th}$ row (where the row with just a single '$1$' is counted as the $0^{th}$ row). Of course each number is the sum of both numbers above it so we have that the sum of all the ways we can choose an even number of elements is the sum of all the numbers in the row above it (again, why?) and similarly the ways we can choose an odd number of elements is the row above it also. $\square$

Just putting it out there, if anybody can teach me how to make a LaTeX pascals triangle then if I have time I'll chuck it into this proof.

So which proof do you think is best? Do you have your own proof? Note by Wen Z
3 years, 1 month ago

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. 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

> 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"
MathAppears 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}$