How many ways are there to pick \(k\) people for a committee out of a total of \(n\) people? The answer is not all that interesting. You can prove (though I won't right now) that the answer is

\[\binom{n}{k}=\frac{n!}{k!(n-k)!}\]

We use the notation \(\binom{n}{k}\) to mean "the number of ways to pick \(k\) objects from a set of \(n\) objects."

These numbers are called "binomial coefficients," and they have some awesome properties. For starters, \[\binom{n}{k}=\binom{n}{n-k}.\] We can see this by looking at the algebra, and doing the manipulations. This is totally legitimate, and not even that hard, but it is boring. What's more, for more complicated formulas, this could be a lot more difficult.

Instead of figuring out counting the possible committees of \(k\) people we can make from \(n\) people, we can think about the "non-committees." Each committee we form, we are really also forming a "non-committee" of all the \(n-k\) people not on that committee. We can think of this as a committee in its own right. So instead of asking "how many \(k\)-person committees can we form from \(n\) people," we can ask "how many \(n-k\)-person

This answer is \(\binom{n}{n-k}\). But we asked the same question. How could we get two different answers? Well, of course we can't. So our two answers must be the same. That is, we proved that

\[\binom{n}{k}=\binom{n}{n-k}.\]

Want to see it again? How many committees can we form (of any size, even \(0\)) from \(n\) people. We can count it by first asking about \(0\)-person committees, and then \(1\)-person committees, etc. up to \(n\)-person committees.

Alternatively, we can count it in the following way. For each person \(P\), we have two options:

\[2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+\binom{n}{n}.\]

I know, it's so simple. All we did was notice that if we count something, and then count it again, we get the same answer. But this obvious fact lets us prove some really cool stuff. Many identities using binomial coefficients or Fibonacci numbers can be proved by using this sort of "count it twice" argument.

Looking for a hard one? Come up with a "count it twice" argument to prove that:

\[\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}\]

\[\binom{n}{k}=\frac{n!}{k!(n-k)!}\]

We use the notation \(\binom{n}{k}\) to mean "the number of ways to pick \(k\) objects from a set of \(n\) objects."

These numbers are called "binomial coefficients," and they have some awesome properties. For starters, \[\binom{n}{k}=\binom{n}{n-k}.\] We can see this by looking at the algebra, and doing the manipulations. This is totally legitimate, and not even that hard, but it is boring. What's more, for more complicated formulas, this could be a lot more difficult.

**A new idea:**Instead of figuring out counting the possible committees of \(k\) people we can make from \(n\) people, we can think about the "non-committees." Each committee we form, we are really also forming a "non-committee" of all the \(n-k\) people not on that committee. We can think of this as a committee in its own right. So instead of asking "how many \(k\)-person committees can we form from \(n\) people," we can ask "how many \(n-k\)-person

*non*-committees can we form from \(n\) people?"This answer is \(\binom{n}{n-k}\). But we asked the same question. How could we get two different answers? Well, of course we can't. So our two answers must be the same. That is, we proved that

\[\binom{n}{k}=\binom{n}{n-k}.\]

**Another application:**Want to see it again? How many committees can we form (of any size, even \(0\)) from \(n\) people. We can count it by first asking about \(0\)-person committees, and then \(1\)-person committees, etc. up to \(n\)-person committees.

Alternatively, we can count it in the following way. For each person \(P\), we have two options:

- Put \(P\) in our committee
- Don't put \(P\) in our committee

\[2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+\binom{n}{n}.\]

**Wow!**I know, it's so simple. All we did was notice that if we count something, and then count it again, we get the same answer. But this obvious fact lets us prove some really cool stuff. Many identities using binomial coefficients or Fibonacci numbers can be proved by using this sort of "count it twice" argument.

**Challenge:**Looking for a hard one? Come up with a "count it twice" argument to prove that:

\[\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}\]