Best proof of k oddn(nk)=k evenn(nk)\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 EE be the set of all ways we can choose an even number of objects, and OO 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 nn (different) objects, designate one object, say xx, 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:

 e E, e={e/{x}xeexxe\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 ee' 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 nn times (order matters). Then the number of ways I can get an even and odd total respectively is E|E| and O|O|. But no matter what the total is after n1n-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 (00)0 \choose{0}, the second is (10)1 \choose 0 (11)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 nthn^{th} row (where the row with just a single '11' is counted as the 0th0^{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

No vote yet
1 vote

  Easy Math Editor

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

[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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...