Bijective Proofs for Combinatorial Identities

Welcome back! In our last lesson, we established the powerful concept of a bijection: a perfect pairing between two sets that proves they have the same size. We used this to show, for example, that the number of lattice paths from $(0, 0)$ to $(m, n)$ is equal to the number of certain binary strings.

Today, we'll take this idea a step further. We will focus on proving entire combinatorial identities—equations involving binomial coefficients and other counting formulas. Instead of constructing an explicit mapping between two different sets, we will often define a single set of objects and count it in two different ways. This elegant technique, known as a combinatorial proof or double counting argument, is a cornerstone of advanced combinatorics. It not only proves an identity is true but also reveals why it's true, providing the deep structural understanding you'll need for Olympiad-level problems.

The Heart of a Combinatorial Proof

The core logic of a combinatorial proof is beautifully simple. To prove an identity like LHS = RHS:

Pose a counting question.
Answer the question one way to get LHS.
Answer the question a different way to get RHS.
Since both expressions count the same thing, they must be equal.

Let's watch a short video that introduces this concept with some excellent examples.

Combinatorial Proofs

This video from CSU Mathematics clearly explains the principle of "counting in two ways" and contrasts it with algebraic proofs.

Please watch the entire video. Pay attention to how each proof starts by defining a set of objects to count. Notice the distinction between a "counting in two ways" proof and a "bijective proof" as described at the end—both are powerful combinatorial arguments.

Proving Identities by Telling Stories

As you saw in the video, the key is to find a "combinatorial story"—a counting problem that both sides of the identity can answer. Let's work through some fundamental identities using this method.

1. The Committee-Chair Identity: $k (k n) = n (k - 1 n - 1)$

This identity was a practice problem in our last lesson. Let's build a formal proof for it.

The Story: From a group of $n$ people, how many ways can we form a committee of size $k$ and appoint one of its members as the chairperson?

Answer 1 (LHS): First, we choose the $k$ members of the committee from the $n$ people. There are $(k n)$ ways to do this. Then, from the $k$ chosen members, we select one to be the chairperson. There are $k$ ways to do this. By the product rule, the total number of ways is $k (k n)$ .
Answer 2 (RHS): Let's change the order. First, we choose the chairperson from the $n$ people. There are $n$ ways to do this. Then, we must choose the remaining $k - 1$ committee members from the remaining $n - 1$ people. There are $(k - 1 n - 1)$ ways to do this. By the product rule, the total number of ways is $n (k - 1 n - 1)$ .

Since both approaches count the exact same set of outcomes (the set of all possible chaired committees of size $k$ ), the results must be equal. Thus, we have proven the identity combinatorially.

2. Pascal's Identity: $(k n) = (k n - 1) + (k - 1 n - 1)$

This identity defines the recursive structure of Pascal's Triangle. An algebraic proof is straightforward, but the combinatorial proof is more illuminating.

The Story: How many ways can we choose a $k$ -person team from a group of $n$ people?

Answer 1 (LHS): By definition, this is $(k n)$ .
Answer 2 (RHS): Let's single out one person from the group, say, "Zoe". Every possible team either includes Zoe or does not. This partitions our set of possible teams into two disjoint groups.
- Case 1: The team includes Zoe. If Zoe is on the team, we have already chosen one member. We need to choose the remaining $k - 1$ members from the other $n - 1$ people. There are $(k - 1 n - 1)$ ways to do this.
- Case 2: The team does not include Zoe. If Zoe is not on the team, we must choose all $k$ members from the other $n - 1$ people. There are $(k n - 1)$ ways to do this.
By the sum rule, the total number of ways is the sum of these two cases: $(k n - 1) + (k - 1 n - 1)$ .

Both expressions count the number of possible teams, so they must be equal. This argument is a classic example of using a "distinguished element" to structure a proof.

3. Vandermonde's Identity: $\sum_{j = 0}^{k} (j m) (k - j n) = (k m + n)$

This identity looks intimidating, but its combinatorial proof is surprisingly natural.

The Story: Suppose we have a group of $m$ mathematicians and $n$ physicists. How many ways can we form a committee of $k$ people from this combined group?

Answer 1 (RHS): We have a total of $m + n$ people, and we need to choose a committee of $k$ . The total number of ways is simply $(k m + n)$ .
Answer 2 (LHS): Let's count by considering the composition of the committee. A committee of $k$ people must have some number of mathematicians, say $j$ . The number of mathematicians, $j$ , can range from 0 to $k$ .
- For a fixed $j$ , we choose $j$ mathematicians from the available $m$ . This can be done in $(j m)$ ways.
- To complete the committee of $k$ , we must then choose the remaining $k - j$ members from the $n$ physicists. This can be done in $(k - j n)$ ways.
- The total number of ways to form a committee with exactly $j$ mathematicians is $(j m) (k - j n)$ .
Since the number of mathematicians $j$ can be any integer from 0 to $k$ , and these cases are disjoint, we sum over all possibilities for $j$ : $\sum_{j = 0}^{k} (j m) (k - j n)$ .

We have counted the same set of committees in two ways, so the identity is proven.

4. The Hockey-Stick Identity: $\sum_{i = r}^{n} (r i) = (r + 1 n + 1)$

This identity gets its name from the shape it forms in Pascal's Triangle.

The Story: How many subsets of size $r + 1$ can be chosen from the set ${1, 2, \dots, n + 1}$ ?

Answer 1 (RHS): By definition, this is $(r + 1 n + 1)$ .
Answer 2 (LHS): Let's count these subsets by considering their largest element. Let's call the largest element $i + 1$ .
- What are the possible values for this largest element? The smallest it could be is $r + 1$ (if the subset is ${1, 2, \dots, r, r + 1}$ ). The largest it can be is $n + 1$ . So, $r + 1 \leq i + 1 \leq n + 1$ , which means $r \leq i \leq n$ .
- Let's fix the largest element in our subset to be $i + 1$ . We have chosen one element. We now need to choose the remaining $r$ elements for our subset. Since the largest element is $i + 1$ , these $r$ elements must come from the set ${1, 2, \dots, i}$ . The number of ways to do this is $(r i)$ .
Since the cases for different largest elements are disjoint, we sum over all possible values of $i$ : $\sum_{i = r}^{n} (r i)$ .

The two expressions count the same collection of subsets, and are therefore equal.

Practice Problems

Now it's your turn to create some combinatorial stories. For each identity, clearly state the counting question you are answering, then provide the two different ways of counting.

The Sum of a Row: Prove the identity $\sum_{k = 0}^{n} (k n) = 2^{n}$ .
- Hint: How many ways are there to form a team of any size from $n$ people? Or, how many binary strings of length $n$ are there?
Committee and Subcommittee: Prove the identity $(m n) (k m) = (k n) (m - k n - k)$ , where $n \geq m \geq k$ .
- Hint: Consider a group of $n$ people. How many ways can you choose a committee of size $m$ and, from within that committee, a leadership subcommittee of size $k$ ? Count this in two different orders.
Strings with Three Symbols: Prove the identity $\sum_{k = 0}^{n} (k n) 2^{k} = 3^{n}$ .
- Hint: How many strings of length $n$ can be made using the symbols ${A, B, C}$ ? For the left-hand side, consider breaking it down based on how many positions are not A.

Conclusion

You have now seen how to prove complex-looking algebraic identities using simple, intuitive counting arguments. This method of "telling a story" is not just a proof technique; it's a way of thinking that builds a deep connection between abstract formulas and concrete combinatorial objects. Mastering this will be invaluable as we tackle more difficult problems.

Key Takeaways:

A combinatorial proof of an identity LHS = RHS is constructed by finding a set that can be counted in two ways, one yielding LHS and the other RHS.
The key is to formulate a "combinatorial story" or a counting question that both sides of the identity answer.
Common strategies include using a "distinguished element" (Pascal's Identity), partitioning a set into types (Vandermonde's Identity), or conditioning on a specific property like the largest element (Hockey-Stick Identity).

In our next lesson, we will shift gears slightly. Instead of counting how many objects exist, we will explore a powerful principle for proving that objects with certain properties must exist at all. This is the famous Pigeonhole Principle.

Recommended resources

The Heart of a Combinatorial Proof

Proving Identities by Telling Stories

1. The Committee-Chair Identity: k(kn​)=n(k−1n−1​)

2. Pascal's Identity: (kn​)=(kn−1​)+(k−1n−1​)

3. Vandermonde's Identity: ∑j=0k​(jm​)(k−jn​)=(km+n​)