Combinatorial proof

A proof of an identity that interprets both sides as counts of the same finite set of objects, establishing their equality by counting those objects in two ways.

Double counting: A counting method that computes the size of one set by grouping its elements in two different ways. A combinatorial proof often equates two expressions by counting the same set using different classifications.
Vandermonde's identity: The identity expressing a binomial coefficient of a sum as a sum of products of binomial coefficients. Choosing a fixed number of people from two groups gives a direct count of both sides.
Finite set: A set containing a limited number of elements. The two expressions in a basic combinatorial proof count a finite collection in different ways.
Algebraic proof: A proof that establishes a mathematical claim through algebraic transformations and properties. It can prove the same identity without interpreting its expressions as counts.
Bijection: A function that pairs elements of two sets one-to-one and onto. A bijection directly shows that the two sets counted by an identity have equal size.
Hockey-stick identity: A binomial-coefficient identity equating a diagonal sum in Pascal's triangle with a single coefficient. The same subset can be counted by its largest selected element or in one unrestricted choice.
Cardinality: The number of elements in a set. Equating the cardinalities of one set under two descriptions yields the desired identity.
Induction proof: A proof method establishing a base case and showing each case implies the next. Induction can establish identities by progression through integer cases rather than a shared counted set.
Binomial coefficient: The number of ways to choose a fixed-size subset from a finite set. Many identities become transparent when each side counts selections with different distinguished features.
Sum of the first n integers: The formula that the sum of the first n positive integers is n(n+1)/2. Pairing terms from opposite ends gives a visual double count of the total.

Linked from 8 pages