From sequences back to polynomials

Babbage's Difference Engine is best known as a mechanical calculator built to evaluate polynomials by repeated addition. But the mathematical trick behind it works in reverse as well: given enough leading terms of a sequence, you can recover the polynomial that generates it.

Consider the pentagonal numbers: 0, 1, 5, 12, 22, 35, 51, ... The method of forward differences lets us identify the generating polynomial from just a handful of these values.

The difference table

For a sequence f(0), f(1), f(2), ..., define the first difference as Δf(n) = f(n+1) − f(n), the second difference as Δ²f(n) = Δf(n+1) − Δf(n), and in general the k-th difference as Δkf(n). We treat f itself as the 0-th difference.

Arrange these in a table: the first column is the index n, the second is the sequence value f(n), then the first difference, second difference, and so on. For the pentagonal numbers, the second difference column is constant — and all subsequent differences are zero.

The key observation: if we know that each difference column eventually becomes zero, we no longer need the full sequence column. The first row alone (the value at n=0 plus the leading entries of each difference column) is enough to reconstruct the entire table by working left-to-right and top-to-bottom.

Degree detection

Claim: if f(n) is a polynomial of degree k, then the k-th difference column is constant.

Proof sketch: write a general k-th degree polynomial as f(n) = aknk + ak−1nk−1 + ... + a0. Substituting into the definition of the first difference and expanding each power j via the binomial theorem gives:

This cancels the highest power of n in every term of Δf(n), leaving a polynomial of degree k−1. Repeating the argument, Δkf(n) is a constant.

Two caveats:

  1. The implication is one-way. Observing a constant k-th difference does not prove the sequence comes from a degree-k polynomial — a higher-degree polynomial or even a non-polynomial function could produce the same finite table. The inference is valid only under the working assumption that the underlying function is polynomial and we seek the simplest one.
  2. The analogy to derivatives is intentional. For continuous functions, the k-th derivative of a degree-k polynomial is constant. Differences play the role of derivatives on a discrete grid; setting the step size to 1 in the derivative definition makes the connection direct.

Finding the coefficients: Newton's forward formula

Once the degree k is known from the difference table, polynomial interpolation needs only k+1 points. Newton's polynomial form is especially convenient for forward differences. For a sequence starting at n=0, it takes the shape:

The construction is deliberate. In the product terms, any factor with index greater than p vanishes when evaluating at p, so the coefficients can be solved one at a time:

  • At n=0, every term except the first disappears, giving f(0) = a0.
  • At n=1, only the first two terms survive; using the known a0, we get f(1) = f(0) + a1, or a1 = Δf(0).
  • At n=2, solving for a2 yields Δ²f(0)/2.

The pattern generalizes:

With the binomial coefficient C(n,i) for the falling product, the Newton forward polynomial can be written compactly as a sum over i from 0 to k of:

All coefficients come from the first row of the difference table — no need for the full sequence column once the degree is established.

For the pentagonal numbers, the degree is 2 because the second difference is constant. Evaluating the sum at n=0 gives:

which simplifies directly to the expected quadratic.

A worked second example

Take the sequence −8, −12, −6, 16, 60, ... Constructing the difference table shows the third difference is constant, indicating a cubic generator. The first row of the table supplies the coefficients for Newton's polynomial, and substituting them reproduces the sequence's first five terms exactly.

Notice that with five data points, ordinary polynomial interpolation would normally force a quartic. The difference table allowed us to stop at degree three — and for longer sequences the savings can be much more significant.

The complete procedure

For an integer sequence suspected of being polynomial-generated:

  1. Build the difference table by successive subtraction.
  2. Find the column that becomes constant; its position reveals the polynomial's degree k.
  3. Use Newton's forward formula with the first k+1 entries to write the generating polynomial explicitly.

Appendix: coefficient of the leading power

A separate argument shows that the coefficient ak of nk equals Δkf(0)/k!. Tracking only the highest-degree term through each difference operation, the leading coefficient of Δf(n) is k·ak, of Δ²f(n) is k(k−1)·ak, and so on until Δkf(n) = k!·ak. Since the k-th difference is constant, its value at n=0 pins down the polynomial's leading coefficient.

Newton's polynomial formulation is a more direct route to all coefficients, which makes this alternate derivation mostly a useful exercise in manipulating floor- and falling-power notation.