Finite Differences: An Example (or Two)

Clay Kitchings

(Motivated from Brualdi’s Introductory Combinatorics, 2010)

Finite differences have many applications including figurate numbers (triangular numbers, square numbers, etc.). It turns out that any sequence of numbers generated by a polynomial of degree p in n has a finite number of differences in a difference table.

We will use what we can figure out about general terms of sequences to find the sums of sequences.

Consider the square numbers:

0 1 4 9 … “0^th order differences” (The sequence itself)

1 3 5 … “1^st order differences”

2 2 … “2^nd order differences”

0 … “3^rd order differences”

Notice that the differences in the 4^th row are zero (the entire row will be zero is the sequence continues)

Generally speaking, let h₀, h₁, h₂, …, h_n, … be a sequence of numbers.

Let h₀, h₁, h₂, …, h_n, … denote a new sequence containing the first order differences.

Similarly denotes the 2^nd order differences and likewise denotes the p^th order differences.

Difference table in general:

h₀ h₁ h₂ h₃ h₄ …

h₀ h₁ h₂ h₃ …

²h₀ ²h₁ ²h₂ …

³h₀ ³h₁ …

…

Note: The notation in each row above is distinct for each row. In other words, in each row need not represent the original h₀ in the 0^th row.

By definition, we let . (The 0^th differences represent the sequence itself.)

Theorem (proof omitted; induction suggested):

Let h_n = a_pn^p + a_p-1n^p-1 + … + a₁n + a₀ represent the general term of a sequence of a polynomial of degree p in n.

Then for each n ≥ 0. (The (p+1)^st difference is zero as we saw in the squares example on the 3^rd row of the difference table)

Of particular interest is what happens along the “0^th diagonal” of the difference table:

h₀ h₁ h₂ h₃ h₄ …

h₀ h₁ h₂ h₃ …

²h₀ ²h₁ ²h₂ …

³h₀ ³h₁ …

…

Once the (p+1)^st row (of zeros) occurs, write down the entries in the 0^th column.

Consider the squares example:

0 1 4 9 … “0^th order differences” (The sequence itself)

1 3 5 … “1^st order differences”

2 2 … “2^nd order differences”

0 … “3^rd order differences”

In this case, suppose we did not know the general term of this sequence. (Of course, we know it is n² since that’s how we constructed it.)

To find the general term of the sequence, I claim you compute

In general, if the 0^th diagonal has entries c₀, c₁, c₂, …, c_p, the general term is

***

Obviously this can be useful if you know you have a polynomial sequence of degree p in n and wish to find the general term of the sequence.

But we wish to find the sum of such numbers in these sequences.

It will be helpful to know a particular identity: .

Algebraic and combinatorial proofs exist for this identity but I do not demonstrate them here. To visualize this identity consider Pascal’s Triangle. The sum (or partial sum) of any diagonal may be found one entry below the sum, offset by one. Notice the example in yellow. Consider the diagonal with entries 1, 4, and 10. These three numbers sum to 15, and notice 15 in the row below and offset by one entry just beneath it. This, in essence, is what the above identity tells us. If we extend another row on the triangle, we would find 1+4+10+20 = 35, and the pattern would continue as far as we wish to extend the table. The identity works for any diagonal in Pascal’s Triangle.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

Now if we sum both sides of (***) above, we obtain:

Now if we apply the identity above we obtain the following:

(*)

Let’s go back to the square numbers above. Our 0^th diagonal is 0, 1, 2, 0, 0, 0…

This implies that if h_n represents 0, 1, 4, 9, 16, …, n², …, then we can compute the sum of h_n using our derived formula (*):

This process yields the sum of h_n for any sequence