A difference table is a discrete derivative

December 10, 2024revised September 20, 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

Download source bundleextract, then runtar -xf difference-tables-triangular_diff.tar && cd difference-tables-triangular_diff/difference-tables && typst compile triangular_diff.typ triangular_diff.png --ppi 500 --root ..

Requires Typst 0.15.1; pinned diagram packages download on first compile.

Individual files:triangular_diff.typ_diagram-style.typ

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.

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

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

# Differences peel off degree

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

Download source bundleextract, then runtar -xf difference-tables-cubes_table.tar && cd difference-tables-cubes_table/difference-tables && uv run --locked cubes_table.py

Requires uv and Python 3.12; the locked packages download on first run.

Individual files:cubes_table.pylockfilefigure_quality.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

Download source bundleextract, then runtar -xf difference-tables-hexagonal_growth.tar && cd difference-tables-hexagonal_growth/difference-tables && uv run --locked hexagonal_growth.py

Requires uv and Python 3.12; the locked packages download on first run.

Individual files:hexagonal_growth.pylockfilefigure_quality.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, with the initial point shown separately:

The figure’s source bundle also reproduces these lattice counts.

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

Those degrees describe this measurement under its radius index. A process with size $s(t)=t$, sampled only at times $t=n^2$, instead gives the sequence $s(n^2)=n^2$. A difference table describes a chosen measurement under a chosen stage index, not an intrinsic degree of the underlying process.

The same hexagon is the ball of radius $n$ for the six moves $(1,0)$, $(0,1)$, $(-1,1)$, and their negatives: a coordinate model of 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.

# A scalar count 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 scalar count sequence and hence the same difference table for every nonnegative integer dilation. They are Ehrhart-equivalent. The counting step, before differencing, does not retain 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. The loss occurs when each stage is reduced to one number; a complete difference table only rearranges that sequence.

# 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

This name now has a concrete job. Cardinality, coordinate-weight sums, and solid-angle sums are all valuations: measurements satisfying $v(A\cup B)+v(A\cap B)=v(A)+v(B)$. The same filtered objects can therefore give different sequences before any difference is taken. Whether a difference still describes a literal layer depends on what that measurement retained.

# 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

Download source bundleextract, then runtar -xf difference-tables-fibonacci_diff.tar && cd difference-tables-fibonacci_diff/difference-tables && typst compile fibonacci_diff.typ fibonacci_diff.png --ppi 500 --root ..

Requires Typst 0.15.1; pinned diagram packages download on first compile.

Individual files:fibonacci_diff.typ_diagram-style.typ

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 records how a chosen measurement changes under a chosen indexing, along with what was forgotten in reducing an object to 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. ↩