Concept

Combinatorial proof

An argument establishing an identity by exhibiting the collection both sides count, rather than by manipulating expressions. It usually generalises where an algebraic verification does not, and it says where the identity fails, because a bijection announces the case it cannot handle.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

A run down a diagonal, and the entry it adds to. 9 rows of Pascal's triangle with 5 entries shaded and the entry they add to marked. The claim is checked by adding the shaded entries: 1 + 3 + 6 + 10 + 15 = 35.

The run that lands one place along

Add up a run of entries down one of Pascal's diagonals and the total is another entry of the triangle — one row further down and one place along. The same triangle holds four more sums of that kind, and each is a different question answered by the same additive rule.

discrete · Pascals triangle

35 routes across a 4 by 3 grid. A grid with each cell holding the number of monotone routes reaching it. The far corner holds 35, which is the binomial coefficient of 7 choose 3.

Every entry counts the routes to it

Turn Pascal's triangle forty-five degrees and it becomes a grid of street corners, with each entry counting the ways of walking there. Identities between the entries then become statements about routes, and the statements are proved by cutting the routes in one place.

discrete · Pascals triangle

Named alongside it

The objects these essays reach for when they reach for this one.

Algebraic identity Binomial coefficient Counting two ways Recursion Bijection Convolution Fibonacci Lattice paths Telescoping Triangular numbers

All concepts