12.1. Definition of Combinatorial Proofs

Now let us go to the last topic for today's lecture, namely combinatorial proofs. This is a common proof strategy we often use in combinatorics. Namely, it's a counting argument to prove identities where you have something on the left-hand side and something on your right-hand side, and you want to mathematically prove that your expression on the left-hand side and the right-hand side are the same.

Combinatorial proofs are used to establish identities in combinatorics by using counting methods. Instead of relying on algebraic manipulations to show that two expressions are equal, a combinatorial proof provides a way to count the same objects in different ways, revealing their equivalence without directly simplifying the expressions themselves.

Think of combinatorial proofs like two different routes you can take from home to school. Route A takes you through the park, while Route B takes you through the library. Both routes get you to your destination even though they look different on the map. The two routes represent counting in different ways, leading to the same conclusion: you arrive at school.

But to do that, we use a counting argument and prove that the expression in the left-hand side and the expression on the right-hand side count the same number of objects but in different ways.

In combinatorial proofs, the core idea is to demonstrate that the two sides of an equation count the same set of objects. This involves identifying a way to interpret what each side represents. By establishing that both sides count the same object in different manners, we can confirm their equality without mathematical manipulation.

Imagine you have two ways to organize a team for a project: Team A consists of picking 4 members from a group of 10, while Team B consists of choosing 6 members to leave out. Both methods yield the same number of teams, illustrating how counting can be interpreted differently yet yield the same result.

Nowhere in the proof do we actually expand our expressions on the left-hand side or right-hand side and show by simplification that the left-hand side is the same as the right-hand side. We do not do that; that is not the goal of combinatorial proof.

One of the defining characteristics of combinatorial proofs is that they do not involve simplifying or expanding either side of the identity. This approach emphasizes understanding the combinatorial relationships between things rather than performing algebraic manipulations. It’s important because it highlights different counting perspectives rather than reducing the problem to simpler forms.

Consider a market where you can purchase fruits either by the basket or by individual pieces. A combinatorial proof is like presenting both options without ever tallying up the price to compare them directly, instead showing that each way can lead to the same total amount of fruit.

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.

When proving identities using combinatorial proofs, we can take an expression like C(n, k) which represents the number of ways to choose k objects from n total objects. Alternatively, we can think of this as leaving out n - k objects. This alternative perspective shows that the same selection process can be counted in two distinct ways, reinforcing the notion that both sides of the equation are indeed equal.

Imagine you have a box of colored pencils and you need to choose a certain number to take to art class. You could either choose a specific number to take, or decide which pencils to leave behind. Both decisions ultimately yield the same set of available pencils for your class, reflecting the same combinatorial reasoning from two perspectives.

Now let's prove an interesting combinatorial identity using combinatorial proof. This is often called Pascal's identity. To prove this, consider a collection of n + 1 objects. Now what is my left-hand side expression? C(n + 1, k). That denotes the total number of k-combinations I can have out of those n + 1 objects.

Pascal's identity establishes a relationship between combinations. The left-hand side, C(n + 1, k) counts how many ways you can choose k items from a total of n + 1 items. The proof involves splitting this count into two categories based on whether a specific object is included or not, thereby demonstrating that the same quantity can be reached via different counting strategies, showcasing combinatorial proof.

Imagine a classroom with 11 students (n + 1). When selecting a committee of 5 students (k), you can think of it in two ways: either one particular student is included, or they are not. By categorizing the selections this way, you can count all groups of students without directly calculating combinations, illustrating the proof.

--