×

# 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
8 months ago