12.3. Pascal's Identity

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. So I am calling those n+1 objects as say A to B they are distinct. Now what is my left-hand side expression? C(n, k) That denotes the total number of k-combinations I can have out of those n+1 objects. I have to pick k objects. I can do that in C(n+1, k) ways. That is the left-hand side.

This chunk introduces Pascal's identity using combinatorial proofs. We start by defining our objects. We have n+1 distinct objects, labeled A through B. The left-hand side of our identity is represented by C(n, k), which refers to the number of ways we can select k items from these n+1 objects. When we write C(n+1, k), we’re essentially stating the number of k-combinations possible from all n+1 objects.

Imagine you have a box with 6 different colored marbles (red, blue, green, yellow, purple, orange), and you want to choose 3 marbles. The left-hand side (C(6, 3)) represents all possible combinations of marbles you can select from the 6 colors.

Now I have to show that the same thing can be counted by adding these 2 quantities that are there on the right-hand side. How do I do that? So my claim is that different k-combinations that I can have out of A to B can be divided into 2 groups. That will take care of the addition that we have on your right-hand-side expression. I have to somehow show that the total number of different k-combinations that I can have can be divided into 2 categories, 2 disjoint categories to be more specific and those 2 disjoint categories are the following.

This chunk explains how to approach the right-hand side of Pascal's identity. We want to group the total k-combinations into two distinct categories. This division is essential for proving that the two sides of the equation are equal. The different groupings provide a way to count the same combinations in two different ways.

If you think of the colored marbles again, we can categorize the combinations based on whether a specific color, say red, is included or not. We have one category for combinations including red (let's say you always take it), and another for those where red is not involved.

You consider all k-combinations that you can form out of those n+1 objects where a specific object is always present. Say the object A is always present. And the number of such k-combinations is nothing but C(n, k−1). Because if the object A is always going to be included in the k objects which you are finally choosing, then you have to worry about how many ways you can pick the remaining k−1 objects out of n.

This part of the proof focuses on category 1 of our combinations. When we choose k-combinations that must include a specific object (A), we are left to select the remaining k-1 objects from the other n distinct ones. This is calculated as C(n, k-1) because we are only looking at combinations that exclude A from consideration.

Continuing with the marble example, if you always include the red marble in your selection of 3, you only need to pick 2 more from the remaining 5 colors. The number of combinations for this selection is calculated as C(5, 2).

Whereas category 2 k-combinations are the ones where the object A is never included. And it is easy to see that the number of different k-combinations of this category is C(n, k). Because if you are not going to include A then your problem is still to choose k objects and now you are left with only n objects to choose from those k objects.

In category 2, we calculate the number of k-combinations excluding the specific object A. Since A is not included, we are only considering the remaining n objects. The k-combinations of this category can be directly counted as C(n, k), since now we have n objects and we need to choose k without any restrictions.

For our marbles, if we decide to leave out the red marble, then we only have to choose 3 colors from the remaining 5 colors. The total combinations of this scenario is C(5, 3).

So if I sum the total number of k-combinations that I have in category 1 and the number of k-combinations that I have in category 2, that will give me the total number of k-combinations that I can have for a set consisting of n+1 objects. And that's precisely your right-hand side. And this is a combinatorial proof because now I have not expanded my left-hand side expression, I have not expanded my right-hand side expression and simplified them. I am just giving a counting argument and proving that LHS and RHS are counting the same things.

The final part of the proof shows that by adding the results from both categories, we arrive at the right-hand side of the identity. The left-hand side counts all possible k-combinations of n+1 objects, while the right-hand side sums the combinations from both categories, confirming that the counts equate.

Going back to our example with marbles, any combination of 3 marbles will either include the red one or not. When you add the combinations of both scenarios (including red versus excluding red), you have all possible ways to choose 3, precisely matching the total possible combinations for 6 distinct colors, proving the identity.

--