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_{0}, h_{1}, h_{2}, É,
h_{n}, É be a sequence of numbers.

Let h_{0}, h_{1}, h_{2}, É, 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_{0} h_{1} h_{2} h_{3} h_{4} É

h_{0} h_{1} h_{2} h_{3} É

^{2}h_{0} ^{2}h_{1} ^{2}h_{2} É

^{3}h_{0} ^{3}h_{1} É

É

Note: The
notation in each row
above is distinct for each row. In other words, in each row need
not represent the original h_{0} 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_{p}n^{p} + a_{p-1}n^{p-1}
+ É + a_{1}n + a_{0} 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_{0} h_{1} h_{2} h_{3} h_{4} É

h_{0} h_{1} h_{2} h_{3} É

^{2}h_{0} ^{2}h_{1} ^{2}h_{2} É

^{3}h_{0} ^{3}h_{1} É

É

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^{2} 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_{0}, c_{1}, c_{2}, É, 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^{2}, É, then
we can compute the sum of h_{n} using our
derived formula (*):

This
process yields the sum of h_{n}
for any sequence