12.2. Example Proof of Equality

Now we are going to prove that the value of C(n, k) is the same as the value of C(n, n - k). Of course, one way of doing that is to expand C(n, k) and rewrite it as n! / (k!(n - k)!). So I could have simply said that they are the same. But that is not the goal of combinatorial proof. In general when we are giving a combinatorial proof for proving LHS and RHS are the same, we do not expand or simplify the expressions on the left-hand side and right-hand side.

A combinatorial proof is a method where we show that two expressions are equal by counting the same set of objects in two different ways. Instead of directly calculating the left-hand side (LHS) and right-hand side (RHS), we focus on how many ways we can arrange or select objects. The goal is not to manipulate the formulas but to interpret them in a way that both sides represent the same count.

Imagine you have 10 different fruits and want to pick 3. You could think of it as picking which 3 fruits to take (LHS) or instead deciding which 7 fruits you will leave behind (RHS). Both methods lead to the same conclusion, illustrating that both sides of the equation represent the same choice situation, just viewed from different angles.

Suppose you are given n objects then your left-hand side is nothing but the number of ways in which you can pick k objects out of those n objects. That's the interpretation of C(n, k) function. Now it turns out for each of the ways in which you can select k objects, there is a way of excluding n - k objects.

Here, the LHS shows the count of selecting k objects from n. Alternatively, instead of focusing on what's being picked, you can count how many n - k objects you will leave out. This gives a different perspective on the same problem. By establishing this correspondence, we show that the total number of selections from either viewpoint is indeed the same.

Think of a birthday party planning scenario. If you have 10 guests and need to choose 3 to invite, you can either list the guests you are inviting or the 7 you are not inviting. The total counts in both cases will be the same, which demonstrates the equality of the two expressions through perspective.

Now let's prove an interesting combinatorial identity using combinatorial proof. This is often called as Pascal's identity. So to prove this consider a collection of n + 1 objects. The left-hand side expression is C(n + 1, k), and I have to pick k objects. I can do that in C(n + 1, k) ways. Now I have to show that the same thing can be counted by adding two quantities on the right-hand side.

Pascal's Identity states that C(n + 1, k) can be expressed as the sum of C(n, k) and C(n, k - 1). The left side counts all possible combinations from n + 1 objects picked k at a time. The right side divides these combinations into two categories: those that include a particular object and those that do not. This separation allows us to count the total number effectively by adding the counts of the two categories.

Imagine having 11 different types of cookies, and you want to choose 4. You can count all combinations that include a specific cookie (Category 1) and those that do not include it (Category 2). By counting the combinations in each way and adding them together, you show that counting can be done differently while still reaching the same result.

Now if I focus on the total of the different k-combinations that I can have out of this n + 1, I can have either a k-combination of Category 1 or a k-combination of Category 2. Namely in the k combination either, the specific object is there or it is not.

The categories of combinations are disjoint, meaning every k-combination can only fall into one of the two groups. By summing up the individual values of each category, we arrive at the total number of k-combinations for the set of n + 1 objects, thus validating Pascal's Identity and reinforcing the concept that the same number can be counted in multiple valid ways.

Continuing with the cookie example, every selection of 4 cookies is categorized as either including or excluding a specific type. Each selection either falls into one of these two distinct groups, ensuring there is no overlap, and counting both sets provides the complete picture of all combinations possible.

--