A Difference Table Is a Discrete Derivative

Published December 10, 2024 · Revised July 24, 2026

Start with the triangular numbers:

$$1,\ 3,\ 6,\ 10,\ 15,\ 21,\ldots$$

Subtract each term from the next. Then do the same to the new row.

Reproduce this figure

triangular_diff.typ_diagram-style.typtypst compile triangular_diff.typ triangular_diff.png --ppi 500 --root ..

The first row says how much the triangles grow: add 2 dots, then 3, then 4. The next row says that those additions themselves grow by 1 each time. After one more subtraction, nothing changes.

That calculation introduces the main ideas used below.

# A map of the argument

There are three directions to follow:

1. Down the table: differences remove polynomial degree, while nonpolynomial signatures leave periodic, exponential, or recursive structure behind.
2. From objects to numbers: geometric stages become totals and changes. Equal totals can forget the shape, while different weights retain or isolate different information.
3. Back up the table: summation stacks the layers, while the left edge reconstructs the sequence. The Stirling-number coefficients explain the special case of ordinary powers.

The final section explains why exact and measured sequences behave so differently under repeated differencing.

One pattern connects the geometric examples: start with a filtered family of objects, measure each stage, and then take a discrete derivative. A valuation is such a measurement when it respects inclusion–exclusion: $v(A\cup B)+v(A\cap B)=v(A)+v(B)$. Cardinality, ordinary volume, and sums of fixed point weights are examples in the settings below. The difference table belongs to the resulting numbers; whether those differences still describe literal layers depends on what the valuation forgot.

# Differences peel off degree

For a sequence given by a function $f$, define its forward difference by

$$\Delta f(n)=f(n+1)-f(n).$$

If $f(n)$ is a degree-$d$ polynomial, then $\Delta f(n)$ has degree $d-1$. For example, if the leading term is $cn^d$, the binomial theorem gives

$$\Delta(cn^d) =c\bigl((n+1)^d-n^d\bigr) =cd\,n^{d-1}+\text{lower-degree terms}.$$

Repeat this $d$ times and only the constant $c\,d!$ remains. One more difference gives zero. Thus:

• a linear sequence has constant first differences;
• a quadratic sequence has constant second differences;
• a cubic sequence has constant third differences.

The cubes make the last case visible.

Reproduce this figure

cubes_table.pylockfilefigure_quality.pyuv run --locked cubes_table.py

This works in reverse. If an infinite sequence has zero $(d+1)$st differences everywhere, it comes from a polynomial of degree at most $d$. A short finite table can always be fitted by a polynomial, so the test becomes conclusive only when the pattern is known to continue.

The arithmetic needs only a few lines:

def difference_table(values):
    rows = [list(values)]
    while len(rows[-1]) > 1:
        previous = rows[-1]
        rows.append([b - a for a, b in zip(previous, previous[1:])])
    return rows

Finite differences also obey a product rule, but the shift cannot be omitted:

$$\Delta(fg)(n) =f(n+1)\Delta g(n)+g(n)\Delta f(n).$$

Equivalently, the shift may fall on $g$ instead. This small asymmetry is one way that finite differencing departs from ordinary differentiation. The coordinates adapted to this operator will appear when the article rebuilds a sequence from its left edge.

# When a difference is a new layer

Suppose $X_n$ is the set of points present at stage $n$, and let $N(n)=|X_n|$. Passing from the objects to their counts, then to their differences, gives a one-way flow:

$$X_n \longrightarrow N(n)=|X_n| \longrightarrow \Delta N(n)=N(n+1)-N(n).$$

Each arrow forgets something. The total $N(n)$ forgets where the points are. The difference $\Delta N(n)$ forgets which points arrived and which departed.

If the stages are nested,

$$X_0\subseteq X_1\subseteq X_2\subseteq\cdots,$$

then nothing departs. The new shell at stage $n$ is

$$S_n=X_n\setminus X_{n-1},$$

and its size is exactly

$$|S_n|=N(n)-N(n-1)=\Delta N(n-1).$$

That set identity – not the sequence alone – is what makes a difference into a new layer.

Now put points on a triangular grid. From any point, allow one step in any of the six grid directions. The points reachable in at most $n$ steps form a hexagon.

Reproduce this figure

hexagonal_growth.pylockfilefigure_quality.pyuv run --locked hexagonal_growth.py

At radius $n$, the total number of points is

$$H_n=1+3n(n+1).$$

So the ring added at radius $n\geq1$ has

$$H_n-H_{n-1}=6n$$

points. The six sides each gain one point per unit of radius. The geometric layers and the rows of the difference table are the same count:

The totals are quadratic, the rings are linear, and the change in ring size is the constant 6.

The same hexagon is the ball of radius $n$ for the six allowed moves on the $A_2$ root lattice.1 Changing the allowed moves changes the ball and can change the sequence.

# Net growth is not always a shell

The nesting condition is a separate requirement. Consider the interval $P=[1,2]$ on the integer line. Its $n$th dilation contains

$$nP\cap\mathbb Z=\{n,n+1,\ldots,2n\},$$

so its count is always $n+1$. From $n=2$ to $n=3$, however, the set changes from

$$\{2,3,4\}\quad\text{to}\quad\{3,4,5,6\}.$$

Two points, 5 and 6, arrive; one point, 2, disappears. The count rises by one, but there is no one-point shell. The first difference records arrivals minus departures.

For a convex shape $P$, putting the origin inside $P$ is a sufficient condition for nested dilations:

$$(n-1)P\subseteq nP.$$

That is why the centered hexagons above form nested set-theoretic layers while an arbitrary translation of the same counting problem may not.

# The polygon formula

There is a wider two-dimensional rule. Let $P$ be a polygon whose vertices lie on the integer lattice. If $A$ is its area and $B$ is the number of lattice points on its boundary, then the number of lattice points in its $n$-fold dilation is

$$L_P(n)=An^2+\frac{B}{2}n+1.$$

This is the polygon case of Ehrhart counting, and it follows directly from Pick’s theorem.2 One difference turns that quadratic total into a linear net increment. When the dilations are nested, that increment is the size of the new set. For the hexagon above, $A=3$ and $B=6$, so $L_P(n)=3n^2+3n+1$ and the $n$th layer has exactly $6n$ points.

A new layer need not equal the geometric boundary for every polygon. It does for this centered hexagon: the strictly interior lattice points of the $n$th hexagon are exactly the points already present at radius $n-1$. The distinction matters when the shape is changed.

# The table forgets the shape

The same count can come from a different picture. Compare the unit square

$$Q=[0,1]^2$$

with the stretched triangle

$$T=\text{conv}\{(0,0),(2,0),(1,1)\}.$$

The $n$th dilation of the square has $(n+1)^2$ lattice points. The triangle has rows of lengths

$$2n+1,\ 2n-1,\ \ldots,\ 3,\ 1,$$

whose sum is also

$$(2n+1)+(2n-1)+\cdots+1=(n+1)^2.$$

The two shapes therefore have the same sequence and the same difference table for every nonnegative integer dilation. They are Ehrhart-equivalent. This is a useful limit on what a table can reveal: it records the counting function, not a unique geometry.

The equality is not a numerical accident. Both polygons have area 1, four boundary lattice points, and no interior lattice points, so the polygon formula gives $(n+1)^2$ for each. Their shapes and their corresponding counting arguments remain different.

Equal totals at every scale are therefore weaker than equal point sets, equal layers, or a geometric map between the shapes. A plain difference table cannot distinguish those notions because it receives only one number per stage.

# Keep one coordinate and the collision disappears

The input can retain more information. Instead of giving every lattice point weight 1, retain its horizontal coordinate:

$$C_P(q)=\sum_{(x,y)\in P\cap\mathbb Z^2}q^x.$$

At scale one, the square gives

$$C_Q(q)=2+2q,$$

while the stretched triangle gives

$$C_T(q)=1+2q+q^2.$$

Their ordinary counts agree because both expressions become 4 at $q=1$. Before that substitution, the weighted counts remember enough horizontal position to tell the shapes apart. A two-variable sum

$$\sum_{(x,y)\in P\cap\mathbb Z^2}u^xv^y$$

records the entire finite lattice-point set at that scale. It still does not turn one sampled scale into the continuous polygon, but it makes the information tradeoff explicit. Weighted Ehrhart theory develops this idea systematically.5

There are other ways to ask a richer family of questions. For example, the Ehrhart quasipolynomials of all rational translations of a rational polytope determine it up to an integer translation.6 One count is coarse; a carefully chosen profile can distinguish much more.

# Changing the weight changes the question

Coordinate weights preserve more location. A different weighting can instead remove a feature that the ordinary count mixes in.

For a positive dilation of a lattice polygon, give an interior lattice point weight 1, a nonvertex point on an edge weight $1/2$, and a vertex the fraction of a full turn occupied by the polygon’s interior angle. The sum of these solid-angle weights is

$$\text{area}(P)n^2.$$

In the unit square, for example, $nQ$ has $(n-1)^2$ interior points, $4(n-1)$ nonvertex edge points, and four right-angle vertices. The weighted sum is

$$(n-1)^2+\frac{4(n-1)}{2}+\frac{4}{4}=n^2.$$

The ordinary count is $(n+1)^2$; the solid-angle count is $n^2$. The first includes the boundary correction and the universal stage-zero point. The second isolates area. Neither is the uniquely correct count: each answers a different question. Macdonald’s solid-angle analogue of Ehrhart counting places this calculation in a general valuation theory.7

# Summation stacks the layers

Differencing removes a layer. Summation puts the layers back.

The square-pyramidal numbers make this literal:

$$1,\ 5,\ 14,\ 30,\ 55,\ldots$$

They count stacks whose horizontal layers contain $1^2,2^2,3^2,4^2,\ldots$ points. Therefore

$$S(n)=\sum_{k=1}^{n}k^2 \qquad\text{and}\qquad S(n+1)-S(n)=(n+1)^2.$$

The same argument works for a height-one lattice pyramid over any lattice polytope $Q$. Its integer-height slices are copies of $0Q,1Q,\ldots,nQ$, in reverse order, so

$$L_{\mathrm{Pyr}(Q)}(n)=\sum_{k=0}^{n}L_Q(k).$$

Taking one forward difference recovers the next slice:

$$\Delta L_{\mathrm{Pyr}(Q)}(n)=L_Q(n+1).$$

Sam and Woods use this slice-and-sum idea as the elementary core of a proof of Ehrhart’s theorem.3 The general proof is more careful, but the picture already explains why summing raises polynomial degree by one and differencing lowers it by one.

# The left edge keeps the sequence

A difference table does not only reveal the degree. Its left edge rebuilds the sequence.

Let $E$ shift a sequence forward, so $Ef(n)=f(n+1)$. The definition of a forward difference says

$$E=I+\Delta.$$

Advancing from $a_0$ to $a_n$ applies the shift $n$ times. Because $I$ and $\Delta$ commute, the ordinary binomial theorem gives

$$\begin{aligned} a_n &=E^n a_0\\ &=(I+\Delta)^n a_0\\ &=\sum_{k=0}^{n}\binom{n}{k}\Delta^k a_0. \end{aligned}$$

This is Newton’s forward formula.4 The formula is therefore a finite operator identity at each integer $n$, not a convergence claim and not a test that the sequence is polynomial. What is special about a degree-$d$ polynomial is that the expansion terminates globally: $\Delta^k a_0=0$ for every $k>d$, so the upper limit can be replaced by $d$ for every $n$.

The basis in that formula is not arbitrary. Pascal’s identity gives

$$\begin{aligned} \Delta\binom{n}{k} &=\binom{n+1}{k}-\binom{n}{k}\\ &=\binom{n}{k-1}. \end{aligned}$$

The binomial polynomials lower one index at a time under differencing, just as ordinary powers lower degree under differentiation. That lowering property is why the left-edge values are their coefficients.

For the triangular sequence as indexed in the opening, the left edge is $1,2,1$. Therefore

$$a_n =\binom{n}{0}+2\binom{n}{1}+\binom{n}{2} =\frac{(n+1)(n+2)}{2}.$$

The apparent shift is only indexing: $a_0=1$ is the first triangular number, not the zeroth. For a general sequence, the same identity still reconstructs each term, but the number of left-edge coefficients needed grows with $n$.

# Why the cube table contains 1, 6, 6

The left edge of the cube table is

$$0,\ 1,\ 6,\ 6,\ 0,\ldots$$

Those numbers are not specific to cubes. For the sequence $a_n=n^m$,

$$\left.\Delta^k n^m\right|_{n=0} =\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^m =k!\,S(m,k),$$

where $S(m,k)$ is a Stirling number of the second kind: the number of ways to partition an $m$-element set into $k$ nonempty blocks.

The alternating sum has a direct counting meaning. There are $j^m$ functions from an $m$-element set to $j$ labeled targets. Inclusion-exclusion removes the functions that miss one or more targets, leaving the surjections onto $k$ targets. An unordered partition into $k$ blocks becomes a surjection after the blocks are assigned to the $k$ target labels, which can be done in $k!$ ways.

For $m=3$,

$$S(3,1)=1,\qquad S(3,2)=3,\qquad S(3,3)=1.$$

Multiplying by $1!,2!,3!$ gives $1,6,6$. Newton’s formula then reads

$$n^3 =\binom{n}{1}+6\binom{n}{2}+6\binom{n}{3}.$$

This is the change of basis hiding in the difference table: ordinary powers are being rewritten in binomial polynomials, and Stirling numbers are the conversion coefficients.

# Tables that do not flatten

Polynomial tables eventually reach zero. Other sequences leave different signatures.

# A polynomial with a clock

Integer polytopes give polynomial counts. Rational polytopes generally give quasipolynomials: each residue class follows a polynomial, but the formulas can differ periodically.

The interval

$$P=\left[0,\frac12\right]$$

already shows the effect. Its $n$th dilation contains

$$L_P(n)=\left\lfloor\frac n2\right\rfloor+1$$

integer points, so the totals begin

$$1,\ 1,\ 2,\ 2,\ 3,\ 3,\ldots$$

and the first differences alternate

$$0,\ 1,\ 0,\ 1,\ldots$$

The linear trend has been removed, but the period-two clock remains. Higher differences keep oscillating instead of becoming zero. A nonflattening table can therefore mean “polynomial growth plus a periodic residue,” not only exponential or recursive growth.

# Exponential and recursive signatures

For $a_n=2^n$,

$$\Delta a_n=2^{n+1}-2^n=2^n,$$

so every row of the table repeats the same powers of two, shifted and shortened. More generally, $a^n$ is an eigenfunction of the difference operator:

$$\Delta a^n=(a-1)a^n.$$

The Fibonacci numbers have a different pattern.

Reproduce this figure

fibonacci_diff.typ_diagram-style.typtypst compile fibonacci_diff.typ fibonacci_diff.png --ppi 500 --root ..

Reading down the left edge applies the signed binomial transform

$$b_n=\Delta^n a_0 =\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}a_k.$$

For Fibonacci,

$$\Delta^n F_0=(-1)^{n+1}F_n.$$

One quick explanation comes from Binet’s formula. Differencing sends an exponential $\alpha^n$ to $(\alpha-1)\alpha^n$ at the row level, and sends its left-edge transform to $(\alpha-1)^n$. The two Fibonacci roots satisfy $\varphi-1=-\psi$ and $\psi-1=-\varphi$, so the roots exchange places and pick up alternating signs.

The table never becomes constant because Fibonacci is not polynomial, but it still exposes the algebra governing the sequence.

# Exact sequences and noisy measurements

Everything above uses exact values. A difference table is much less forgiving when the entries contain measurement or rounding error.

Suppose an otherwise smooth sequence contains a small alternating error $\varepsilon(-1)^n$. One difference turns it into

$$\Delta\bigl(\varepsilon(-1)^n\bigr) =-2\varepsilon(-1)^n.$$

After $k$ rows, its magnitude is $2^k\varepsilon$. The highest-frequency error doubles at every step even while differencing removes the smooth polynomial trend.

Random error has a related but distinct amplification law. If the observation errors $\varepsilon_n$ are independent, have mean zero, and share variance $\sigma^2$, then

$$\Delta^k\varepsilon_n =\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}\varepsilon_{n+j}.$$

Independence removes the cross terms in the variance, so

$$\text{Var}(\Delta^k\varepsilon_n) =\sigma^2\sum_{j=0}^{k}\binom{k}{j}^2 =\sigma^2\binom{2k}{k}.$$

Thus the standard deviation grows by $\sqrt{\binom{2k}{k}}$, asymptotically close to $2^k/(\pi k)^{1/4}$. The exact $2^k$ gain above belongs to a deterministic alternating mode. If errors are correlated, the variance is instead $c^\top\Sigma c$, where $c_j=(-1)^{k-j}\binom{k}{j}$; the independence formula must not be reused unchanged.

For an exact sequence with a difference law known to continue, a constant row settles the polynomial question. With measured data, high-order differences are a diagnostic, not proof of a polynomial law; smoothing, uncertainty, and out-of-sample checks matter.

# What the table is saying

A first difference is the net change at the next step. It becomes the amount added only when the underlying stages are nested. Repeated differences measure how that growth itself changes. For polynomial sequences, the process ends after finitely many rows, and the left edge records the coefficients in the binomial basis.

In geometric counting, the flow of information matters. A filtered family of objects is measured by a valuation; differencing then takes the discrete derivative of that measurement. Weighted counts retain selected structure that a plain total discards. When the sets form a filtration, totals become layers, layers become changes in the boundary, and a pyramid is a running sum of its slices. The table is not only a way to guess a formula. Read with its assumptions visible, it is a record of how the object grows – and of what was forgotten in turning that object into a sequence.

# References

[1] Ardila, F., Beck, M., Hoşten, S., Pfeifle, J., and Seashore, K. “Root Polytopes and Growth Series of Root Lattices.” SIAM Journal on Discrete Mathematics 25(1):360–378, 2011. ↩

[2] Beck, M. and Robins, S. Computing the Continuous Discretely. Springer, 2007. Chapters 2 and 3 cover Pick’s theorem and Ehrhart counting. ↩

[3] Sam, S. V. and Woods, K. M. “A Finite Calculus Approach to Ehrhart Polynomials.” The Electronic Journal of Combinatorics 17, R68, 2010. ↩

[4] Graham, R. L., Knuth, D. E., and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. 2nd ed., Addison-Wesley, 1994. Chapter 2 develops finite differences, falling factorials, and Newton’s formula. ↩

[5] De Loera, J. A., Valencia, C. E., Villarreal, R. H., and Wang, C. “Ehrhart Functions of Weighted Lattice Points.” arXiv:2412.17679. ↩

[6] Higashitani, A., Murai, S., and Yoshinaga, M. “Ehrhart Quasi-polynomials and Parallel Translations.” arXiv:2307.08151. ↩

[7] Beck, M. and Ehrenborg, R. “Ehrhart-Macdonald Reciprocity Extended.” Moscow Mathematical Journal 5(3):495–504, 2005. ↩