Example 1 Prove that .
There is an obvious way to prove this by algebraic manipulations using the fact that . But we are more intersted in a general idea which not only proves this particular identity but also shows us how to come up with such identities. So, here’s one such proof:
Consider a community of people from which you have to select a committee of members with a designated leader. In how many ways can this be done? One way to do this is to choose the members first in ways and then choose a leader from them in ways. This gives a total of ways. Other way of doing this would be to first choose the leader, in ways and then from the remaining people choose to complete the committe. This gives a total of ways. Thus, we can see that .
This illustrates the typical “procedure” of double counting in proving identities. You look for an object which when counted in one way gives the left hand side and when counted in another way gives the right hand side. I would like to write it as this:
Let , be finite sets and a subset of . Whenever we say is incident to . If denotes the number of elements that are incident to and denotes the number of elements that are incident to , then .
Here’s a famous example from graph theory.
Example 2 Let be a finite simple graph with vertex set and edge set . The degree of a vertex , denoted as , is the number of edges incident to . Then we have
For the proof consider , where is the set of pairs such that is an end-vertex of . Counting in two ways gives us on one hand , since every vertex contributes to the count, and on the other hand , since every edge has two ends.
Next let’s consider an interesting identity in number theory:
To prove this, let and .
This identity can be used to prove a surprising result that even though is a wildly jumping function its average is quite well behaved. In fact,
Proof of this follows easily from the identity and the properties of harmonic numbers.
In example 1, we had a nice combinatorial view of the number , namely, it is the number of ways to choose elements from a set of elements. But it might not be that easy in identities involving some other numbers. For example, consider this:
Example 4 Let denote the Fibonacci number. Then
To give a double counting proof of this identity we need a combinatorial view of the Fibonacci numbers. That can be done as follows:
Let denote the number of ways in which you can tile a rectangular board with squares and domnioes. Clearly as you can put only a square and as you can put two squares or a single domino. Thinking recursively we see that a tiling of rectangular board will either begin with a square or a domino giving us for all .
So, it is not difficult to see that for all (letting ). Now, we would prove an equivalent identity involving ,
The right hand side is the number of ways to tile rectangular board by squares and dominoes minus one particular tiling.
Let’s try this: is the number of tilings with at least one domino.
Can we count it in some other way?
Think about what is the position of the last domino in a tiling. Since after we have put the last domino, it’s all squares! With the last domino at we have tilings where ranges from to . Hence, we get a total of tilings with at least one domino.
I’ll list some more examples that one can try using these ideas:
Prove that .
Example 6 Let be a set of persons such that:
- Any person is acquainted with exactly other persons in .
- Any two persons that are acquainted have exactly common acquaintances in .
- Any two persons that are not acquainted have exactly common acquaintances in .
Then show that, .
In graph theoretic terms this will be stated as, “Given a -regular graph with the property that any two adjacent vertices have exactly common neighbors and any two non adjacent vertices have exactly common neighbors, show that .”
Such graphs are known as strongly regular graphs.
Example 7 Show that for all ,
Hint: How many tilings have exactly dominoes?
Example 8 Theorem 3 on this post.
Further reading and references