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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: