The run that lands one place along

The rung below asked Pascal’s triangle a question it was not built for — whether each entry is odd — and got a fractal. This rung asks the questions it was built for.

They all have the same shape: shade a run of entries, add them up, and the total is somewhere else in the triangle.

The stick, and why it works #

The identity is called the hockey stick, from the shape of the shading: a run down a diagonal and one entry off at the end.

$$\binom{r}{k} + \binom{r+1}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1}.$$

The proof is the additive rule, used backwards. Every entry is the sum of the two above it, so

$$\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1},$$

and the second term on the right can be expanded the same way, and again, and again. Each expansion peels off one entry of the diagonal and leaves a smaller version of the same problem, until the last one bottoms out at $\binom{k}{k+1} = 0$.

That is a telescoping argument and it is worth naming as one. A sum is rewritten so that each term cancels part of the next, and what survives is the two ends. The same manoeuvre proves that the odd numbers add to squares, and it is the discrete version of the theorem that makes area the undoing of slope — a total of differences is a difference of totals.

There is a second proof and it is the one worth carrying, because it explains rather than verifies. Both sides count the same thing: the ways of choosing $k+1$ items from $n+1$. Classify those choices by which item is the largest chosen. If the largest is item $j$, the remaining $k$ come from the $j-1$ below it, and there are $\binom{j-1}{k}$ ways. Summing over $j$ gives exactly the run down the diagonal.

Counting one collection two ways is the whole method of this subject, and every identity below is an instance of it.

What the diagonals are #

The stick identity says something structural once it is read the right way round: each diagonal is the running total of the one before it.

The first diagonal is all ones. Its running totals are $1, 2, 3, 4, \ldots$, which is the second diagonal. Their running totals are $1, 3, 6, 10, \ldots$ — the triangular numbers, which is the third. Their running totals are the tetrahedral numbers, and so on.

So the figurate numbers are not visitors in Pascal’s triangle. They are what the triangle’s columns are, and the reason is one line: the additive rule says an entry is the sum of the one above and the one above-left, which is exactly the recurrence a running total satisfies.

That reading also explains why $\binom{n}{2}$ counts pairs and equals $n(n-1)/2$. The third diagonal is the running totals of $1, 2, 3, \ldots$, and a running total of the whole numbers is a triangular number, and a triangular number is half a rectangle. Three descriptions of one column.

It is worth following the reading one step further, because it says what the triangle is as an object. A running total is a discrete integral, so the diagonals are the repeated integrals of the constant sequence $1, 1, 1, \ldots$ — the first is the constant itself, the second is $n$, the third is $n^2/2$ to leading order, the fourth $n^3/6$, and the $k$-th is a polynomial in $n$ of degree $k-1$ with leading coefficient $1/(k-1)!$.

Those are exactly the terms of an exponential series, and that is not a coincidence either: summing a diagonal is integrating, and a family closed under integration with the constants right is the family the exponential is built from. The columns of Pascal’s triangle are the powers of $n$, divided by factorials, made whole, and the factorials in the coefficient formula are the accumulated cost of $k$ integrations rather than a normalisation somebody chose.

The practical form of that observation is the standard method for summing polynomials. To add up $1^3 + 2^3 + \cdots + n^3$, write $n^3$ as a combination of $\binom{n}{1}$, $\binom{n}{2}$ and $\binom{n}{3}$ — which is possible because those are polynomials of degrees one, two and three — and then apply the stick identity to each, which sums a diagonal in one step. The awkward closed form for the cubes comes out of three applications of a single identity, with no induction and no guessing of the answer in advance.

The rows #

Two more identities live along the rows rather than down the diagonals, and they are the two easiest to prove and the two most used.

$$\sum_k \binom{n}{k} = 2^n.$$

The counting proof is one sentence: a subset of $n$ items is chosen by deciding independently, for each item, whether to include it. That is $n$ binary decisions and $2^n$ outcomes. Grouping the outcomes by how many items were included gives the row of the triangle, so the row adds to $2^n$.

$$\sum_k (-1)^k \binom{n}{k} = 0 \quad (n \ge 1).$$

This one has a bijection rather than a count. Fix an item — the first, say. Every subset either contains it or does not, and toggling it pairs each subset with exactly one other of the opposite size. So the subsets of even size and those of odd size are in one-to-one correspondence, the two totals are equal, and the alternating sum is nought.

The bijection is a better proof than the arithmetic because it says why the identity fails at $n = 0$: there is no item to toggle, the pairing has nothing to work with, and the single empty subset is left over. An arithmetic proof would have needed a special case; the bijection announces where it is.

The two row identities are also the two ends of a single family, and seeing that is worth more than either. Both are $\sum_k \binom{n}{k} x^k$ evaluated at a particular $x$ — at $x = 1$ for the plain sum and at $x = -1$ for the alternating one — and that expression is $(1+x)^n$, which is the binomial theorem. So the two identities are one polynomial read at two points, and the row of the triangle is that polynomial’s list of coefficients.

Reading them that way immediately produces more. At $x = 2$ the sum $\sum_k 2^k\binom{n}{k}$ is $3^n$, which counts the ways of putting $n$ items into three boxes by first choosing which go into the first box; at $x = i$ it splits a row into four interleaved parts and produces the sums of every fourth entry. Each value of $x$ is an identity, and there are as many identities as there are values, which is why the polynomial is a better object to hold than any list of the identities it produces.

The shallow diagonals #

Read the triangle along a shallower slope, taking $\binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \cdots$, and the totals are $1, 1, 2, 3, 5, 8, 13, \ldots$

The reason is the additive rule again, applied to the whole diagonal at once. Split each entry of the $n$-th shallow diagonal by the additive rule and the two halves land in the $(n-1)$-th and $(n-2)$-th shallow diagonals — so the totals satisfy $F_n = F_{n-1} + F_{n-2}$, which with the right two starting values is the Fibonacci rule.

The counting proof is nicer. A shallow diagonal’s entry $\binom{n-k}{k}$ counts the ways of choosing $k$ non-adjacent items from a row of $n-k+1$, and summing over $k$ counts every subset with no two adjacent. Those are counted by the Fibonacci numbers, by the standard argument: either the last item is left out, leaving the count for $n-1$, or it is taken, forcing its neighbour out and leaving the count for $n-2$ — the same two-case split that makes the golden ratio the rate at which the counts grow.

So a fact about subsets with no two adjacent and a fact about a diagonal of Pascal’s triangle are one fact. Neither construction mentions the other, which is the same kind of coincidence the rung below’s Sierpiński triangle turned out to be, and it has the same kind of explanation: two recursions of the same shape.

The squares #

$$\sum_k \binom{n}{k}^2 = \binom{2n}{n}.$$

A square of a coefficient is a product of two, so the left-hand side is counting pairs of choices. Take $n$ items on the left and $n$ on the right; a choice of $n$ items from all $2n$ takes some $k$ from the left and $n-k$ from the right. There are $\binom{n}{k}$ ways for the first and $\binom{n}{n-k}$ for the second, and $\binom{n}{n-k} = \binom{n}{k}$ by symmetry, so the product is the square. Summing over $k$ counts every choice of $n$ from $2n$.

The symmetry step is worth pausing on because it is what turns a product into a square. Choosing $k$ items to keep is the same act as choosing $n-k$ to discard, so the row reads the same backwards — and that is why an identity about products of two different coefficients comes out looking like an identity about squares.

What a row costs #

The triangle is usually built by addition, and that is not how a single entry deep in it should be computed.

Building row $n$ by the additive rule costs about $n^2/2$ additions, since every row must be built to get to it, and it needs every earlier row in memory. Computing one entry directly by the multiplicative rule

$$\binom{n}{k} = \frac{n}{1}\cdot\frac{n-1}{2}\cdots\frac{n-k+1}{k}$$

costs $k$ multiplications and $k$ divisions and needs nothing kept. For $\binom{100}{37}$ that is seventy-four operations against about five thousand.

The multiplicative rule has a property that looks like luck and is not: every partial product is a whole number. Multiplying by $n-k+i$ and dividing by $i$ at each step never leaves a fraction, because the running value after $i$ steps is $\binom{n-k+i}{i}$, which is a count and therefore whole. Reordering the operations would break it — dividing by all the $i$ first gives a fraction — so the rule is a specific interleaving rather than an expression.

And then there is the size. $\binom{100}{37}$ is about $10^{28}$, which a double-precision number cannot hold exactly; it is stored to sixteen significant figures and the rest is noise. That is fatal for any question about divisibility, since divisibility is decided by the digits that were discarded — and it is exactly the question the rung above asks. The figures there compute the coefficient in exact whole-number arithmetic for that reason, after a first version used a double and confidently refused a correct answer.

A count is a whole number and should be computed as one, which is a rule this collection has arrived at from several directions. The moment a count is stored as a floating-point value it stops being a count and becomes an estimate of one, and every question that depends on its last digit becomes unanswerable without anything failing.

Where these came from #

None of the five identities is anybody’s in particular, and the history is worth a paragraph because the pattern is instructive.

The triangle itself is old and widely independent: Halayudha describes it in tenth-century India, al-Karaji in eleventh-century Persia, Yang Hui in thirteenth-century China, and Pascal in 1654 — as the rung below records, the name is European bookkeeping rather than a claim of discovery.

The identities travelled with it. The row sum is in every tradition that met the object, because it is what the object is for. The alternating sum and the stick are in Pascal’s Traité du triangle arithmétique, which is largely a catalogue of exactly this kind of statement — Pascal’s real contribution being that he proved them, by an early and explicit use of induction, where his predecessors had observed them.

The names are all much later and mostly unhelpful. “Hockey stick” is twentieth-century and American, describes the shading rather than the mathematics, and is unknown in several languages that have their own name for the same picture. A result named after its diagram is a result nobody found a better handle for, which here is fair: it is a special case of the general fact that a diagonal is a running total, and that fact has no name at all.

What the shading cannot do #

Every figure on this page shades a run and prints its total, and the total is a fact about the drawn entries. The identity is about every $n$ and every $k$, and eleven rows of a triangle contain finitely many instances of it.

The generator adds the shaded entries and compares against the closed form, so what is established is that the identity holds here. What establishes it in general is one of the two arguments in each section — the telescope or the count — and neither is drawn, because a telescope is a cancellation and a count is a bijection, and neither has a picture.

More specifically, the shallow-diagonal figure cannot show the Fibonacci recursion. It shows one diagonal and one total; the claim is about a sequence of totals satisfying a rule, which needs three consecutive diagonals to state and a general argument to prove.

Where the identities need their conditions #

The stick needs its run to start at the top of the diagonal. Starting halfway down gives a difference of two entries rather than one, which is still an identity and is not the one drawn. The figure’s assertion checks the run it shades, so a mis-specified run fails rather than reporting a wrong total.

The alternating row identity fails at $n = 0$, as the bijection predicts, and every statement of it carries the condition.

The shallow diagonals need the right convention. Which entries count as one shallow diagonal depends on how the triangle is indexed, and two reasonable conventions give the Fibonacci numbers offset by one from each other. The figure fixes one and states it.

And the square identity needs the row to be doubled inside the triangle. The total is the middle entry of row $2n$, so drawing it needs $2n+1$ rows, which is why the figure uses a small row.

Everything at once, and why that is the point #

The five identities look like five results and are one observation applied five times: classify a collection by something, and count each class.

The stick classifies choices by their largest element. The row identity classifies subsets by their size. The alternating identity pairs subsets by toggling one element. The shallow diagonal classifies non-adjacent subsets by their size. The square identity classifies choices from a doubled set by how many come from each half.

Every one of them is a partition of a set that is counted two ways, and the identity is the statement that the two counts agree. There is no algebra in any of the five proofs, and the algebraic verifications — expanding factorials and cancelling — are longer, less memorable and explain nothing.

That is the standing recommendation of this field and it is worth stating as one. When an identity between counts is to be proved, look for the set both sides count. It is usually there, the proof is usually a sentence, and the sentence usually generalises where the algebra does not.

The ladder from here #

Rungs above: the routes a coefficient counts, where the triangle is read as a grid and the identities become statements about paths. Kummer’s theorem, which says exactly how often a prime divides an entry. The binomial theorem, which is the row identity with the two decisions weighted rather than counted. Generating functions, where a whole row becomes a polynomial and these identities become products of polynomials. And the central binomial coefficient’s growth, which is where the triangle’s middle column meets the bell curve the falling balls draw.

Asking an old object an old question #

The rung below ended by recommending that a well-understood object be asked a question it was not built to answer. This rung is the other half of that advice and it is worth stating too.

The questions on this page are the ones the triangle was built for. Every one of them was known to somebody in the eleventh century, none of them required a new idea, and the reason to write them down is that they are the structure the fractal was hiding in. The parity picture is striking and the identities are what the object is made of, and a reader who met only the striking one would have the wrong idea about what the triangle is.

A famous property is rarely the most informative one. Pascal’s triangle is famous for a fractal that appears when its entries are reduced modulo two, and it is made of running totals — and the second fact is what explains the first, since the fractal comes from the additive rule and the additive rule is what makes each diagonal a running total of the last.