On this page
Double counting (also known as counting in two ways) is a mathematical proof technique used to show that two expressions are equal. Instead of relying on algebra to move variables around, you define a single, finite set of items and describe its total size from two different perspectives. Since both methods count the exact same set, the two resulting expressions must equal each other.
In their 2001 book *A Course in Combinatorics*, mathematicians J.H. van Lint and R.M. Wilson describe double counting as "one of the most important tools in combinatorics" (Wikipedia)). The method gives you a physical story for why an identity is true, which is often easier to follow and verify than a long page of equation manipulation.
How does the handshaking lemma use double counting?
One of the most famous examples of double counting comes from graph theory. In 1736, Leonhard Euler proved a result that later became known as the handshaking lemma (Wikipedia). The lemma states that in any graph, the sum of the degrees of all vertices is exactly twice the number of edges.
Here is how Euler's idea works as a double counting proof:
The Set: Imagine the set of all "endpoints" of every edge in the graph.
Way 1 (Vertices): Count the endpoints by looking at the vertices (nodes). Each vertex connects to a certain number of edges, which is its degree. If you add up the degrees of all vertices, you have counted every endpoint in the graph.
Way 2 (Edges): Count the endpoints by looking at the edges (lines). Every single edge has exactly two endpoints. If the graph has E edges, there must be exactly 2 × E endpoints.
The Conclusion: Because both methods count the exact same set of endpoints, the sum of the degrees equals twice the number of edges.
How do you prove the sum of binomial coefficients?
Another powerful example of double counting is proving that the sum of all binomial coefficients for a given n equals 2ⁿ (written as nC0 + nC1 + … + nCn = 2ⁿ). This identity is foundational when studying sums of binomial coefficients.
The Set: The total number of subsets that can be formed from a set of n distinct elements.
Way 1 (By size): Group the subsets by their size, k. To form a subset of size k, you choose k items from n, which is calculated as nCk. If you sum these choices for every possible size from k = 0 (the empty set) all the way up to k = n (the full set), you get the total number of subsets.
Way 2 (By individual choice): Look at each of the n elements one by one. For every element, you have exactly two choices: either include it in your subset or leave it out. Since there are two choices for the first element, two for the second, and so on for all n elements, the total number of possible combinations is 2 × 2 × … × 2, which is 2ⁿ.
Because both methods count the total number of subsets, the sum of the combinations must equal 2ⁿ. If you are studying for exams and need to visualise how sets are formed, the Fermi Concept Library has a lesson for every concept in mathematics.
What is the committee and chairperson trick?
Another classic double counting proof shows that k × nCk = n × (n−1)C(k−1). This looks intimidating algebraically, but it is simple if you count the ways to form a committee that has a chairperson.
The Set: The number of ways to choose a committee of k people from a group of n people, and then appoint one of those k people as the chairperson.
Way 1: First, choose the committee of k people from the total n (which gives nCk ways). Then, pick 1 chairperson from those k members (which gives k choices). Multiplying these gives k × nCk.
Way 2: First, pick the chairperson directly from the total n people (which gives n choices). Then, fill the remaining k−1 seats on the committee from the remaining n−1 people (which gives (n−1)C(k−1) ways). Multiplying these gives n × (n−1)C(k−1).
Since both stories describe the exact same process of forming a led committee, the two sides are equal. Whether you are counting combinations or evaluating arrangements of letters with repeats, having a concrete story makes the mathematics intuitive. You can explore more combinatorial proofs with a step-by-step solver that explains the reasoning in the Fermi Problem Library.
How do you build a double counting proof?
If you struggle to spot the right set to count when proving an identity, Fermi's AI tutor can help. Instead of just printing the final algebraic proof, the tutor holds a line of reasoning across the session, notices where you are stuck, and decides whether to explain, ask, or show.
To build your own double counting proof on an exam, try following this three-step framework:
Define the set: Look at the two expressions you want to equate and ask, "What real-world items could these numbers represent?" (e.g., committees, subsets, endpoints, paths).
Count by groups: Find one way to sort the set into groups and sum them up. This usually yields the side of the equation with an addition series.
Count directly: Find a second, independent way to count the entire set at once. This usually yields the simpler, multiplicative side of the equation.
