## Difference Tables

Consider a sequence C = (C0, C1, C2, …). Define:

A0,j = Cj,
Ai,j = Ai,j+1 − Ai,j, and
Ri = Ai,o.

This might be pictured:

 C0 C1 C2 C3 C4 C5 || || || || || || R0 = A0,0 A0,1 A0,2 A0,3 A0,4 A0,5 … R1 = A1,0 A1,1 A1,2 A1,3 A1,4 … R2 = A2,0 A2,1 A2,2 A2,3 … R3 = A3,0 A3,1 A3,2 …

R = (R0, R1, R2, …) is another sequence. We might call C the sequence generated by R and R the generator of C.

It turns out that

$C_n = \sum_{k=0}^{n} \dbinom{n}{k} R_k$;

$R_n = \sum_{k=0}^{n} (-1)^{n-k} \dbinom{n}{k} C_k$.

The first of these formulae is particularly handy if the the sequence R is finite (or rather, is eventually zero):

$C_n = \sum_{k} R_k \dbinom{n}{k}$.

Given some unknown sequence, this formula may be used to find empirically the power-series closed form, if it has one.

For example, consider the tetrahedral numbers C = (0, 1, 4, 10, 20, 35, …). We find that R = (0, 1, 2, 1).

Therefore $C_n = \dbinom{n}{1} + 2 \dbinom{n}{2} + \dbinom{n}{3} = \dbinom{n+2}{3}$.

This is not a proof of course, but it can be a useful experimental tool. It is also useful for manipulating sum sequences and difference sequences.