Common combinatorial proof set-ups

By Natasha -
One good way to think about combinatorial proofs in general is something like this:
Goal: Prove that quantity A and quantity B are equal.
Step 1: Think of some question to which either A is obviously the answer. 
Step 2: Show that B also gives the answer to the question.

Or perhaps like this:
Goal: Prove that quantity A and quantity B are equal.
Step 1: Think of some set of size A. Think of some different set of size B.
Step 2: Find a bijective (one-to-one) correspondence between the two sets.
In both set-ups, most of the creativity is in that second step. That's the hard part, but it's also the part that gives us all the insight. Coming up with an explanation of why B counts the same thing A does is exactly what helps us understand why the two quantities are the same.

Let's spend a little more time with binomial coefficients to gain some more practice with combinatorial proofs. Here are a few identities. Take some time to think about them and try to write up proofs for each before reading the proofs at the end of this post.

Claim 1: $$\sum_{k=0}^n  {n \choose k} = 2^n$$
Claim 2: $${n \choose k} = {n \choose n{-}k} $$
Claim 3: If n>0 then  
$$\sum_{k=0}^n {n \choose 2k} = \sum_{k=0}^n {n \choose 2k+1}$$

Proofs of Claims 1-3

Proof of Claim 1: Our question will be, how many ways can we make a committee (of any size) out of a class of n people?

The left hand side of the equation counts this because each term in the sum tells us how many different committees can be constructed with exactly k members. Since k can be as little as 0 (the empty committee) and as big as n (the whole class is the committee), this gives us the total number of committees possible.

The right hand side counts this because for each of the n people, there are two choices---either that person is in the committee, or that person is not in the committee. By the product rule, we multiply by 2 a total of n times, and get 2n. ▢ 

Proof of Claim 2: How many different k-person committees can be made out of a set of n people? By our definition of binomial coefficients, this is answered by the left hand side. On the other hand, instead of choosing k people for the committee, we can choose n-k people to exclude from the committee; the right hand side counts that. Therefore, the two sides are equal. ▢ 

Proof of Claim 3: HW!

Comments

Post a Comment

Popular posts from this blog

Common counting techniques

By Natasha -
Image
Before we go too far with proving various clever binomial coefficient identities, let's try counting some things with them. Stars and bars We know that there are " n  choose  k " ways to pick  k  children out of a group of  n  children (assuming we can tell the children apart). But what if we add an indistinguishable element to the story? Unlike our distinguishable children, let's say we have some identical candies to hand out. One natural question is: How many ways are there to hand out  k  indistinguishable candies to  n  distinguishable children? Here's where the stars and bars come in. Let's say we have 3 children and 8 candies. We can think of the candies as the "stars." The 3 children can be thought of as candy receptacles (sorry, kids), distinguished only by their order from left to right. So here's one way we could distribute the candy: ***|****|* In this case, the first child/candy receptacle gets 3 candies, the second gets 4
Read more

"Pyramid Numbers" Fun Fact!

By -
Similar to the set up for the triangular numbers, "pyramid number," or \(P_n\), refers to the required number of dots for a \(n\) triangular base pyramid that has \(n\) dots per side on its base. And here is a fun fact for \(P_n\): $$\sum_{n=1}^{\infty}{\frac{1}{P_n}} = \frac{3}{2}$$ To prove this equality, we first may need some kind of formula for \(P_n\) so that we can do something with the LHS. As you may have found in homework, "Pyramid numbers" are a series of numbers right next to "triangular numbers" in Pascal's triangle. Therefore we know a general formula for \(P_n\): $$P_n = {n+2\choose 3} = \frac{(n+2)\cdot (n+1)\cdot n}{3!}$$ Now, we can rewrite the LHS and try to split the sum expression: $$\begin{eqnarray} \sum_{n=1}^{\infty}{\frac{1}{P_n}} &=& \sum_{n=1}^{\infty}{\frac{1}{(\frac{(n+2)\cdot (n+1)\cdot n}{3!})}}\\ &=&3!\sum_{n=1}^{\infty}{\frac{1}{(n+2)\cdot (n+1)\cdot n}}\\ &=&3!(\frac{1}{1\cdot 2 \cd
Read more

Parallelogram Identity Proof (Using Stars and Bars Technique)

By -
The parallelogram identity in Pascal's triangle states that, given an entry \({n \choose k}\) in Pascal's triangle, \({n \choose k}-1 = \) the sum of the entries included in the rectangle that is straight above entry \({n \choose k}\) and also includes the apex of Pascal's triangle. This equality can be expressed as a double sum as follows, $${n+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{n-k}{n-i-j \choose k-i}$$.  We can prove this by using the stars and bars technique that we are familiar with. For easier explanation, let's first rewrite the double sum expression above in another form (but mathematically equivalent). Set \(r = n-k\), we have  $${r+k+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{r}{(k-i)+(r-j) \choose k-i}$$.  Let's assume we have \((k+1)\) stars and \(r\) bars. As we have already known, \({r+k+1 \choose k+1}\) counts the number of different star-bar sequences. This implies that maybe we can try to interpret the RHS as another way to count almo
Read more