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 …           “0th order differences” (The sequence itself)

         1                3                5 …                    “1st order differences”

                  2                2 …                             “2nd order differences”

                           0 …                                      “3rd order differences”

 

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

 

 

Generally speaking, let h0, h1, h2, …, hn, … be a sequence of numbers.

 

Let h0, h1, h2, …, hn, … denote a new sequence containing the first order differences. 

Similarly  denotes the 2nd order differences and likewise  denotes the pth order differences.

 

 

Difference table in general:

 

h0               h1               h2               h3               h4              

         h0           h1           h2           h3          

                  2h0          2h1          2h2         

                           3h0          3h1         

                                   

 

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

 

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

 

 

 

Theorem (proof omitted; induction suggested):

 

Let hn = apnp + ap-1np-1 + … + a1n + a0 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 3rd row of the difference table)

 

 

 

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

 

h0               h1               h2               h3               h4              

h0           h1           h2           h3          

2h0          2h1          2h2         

3h0          3h1         

 

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

 

Consider the squares example:

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

         1                3                5 …                    “1st order differences”

                  2                2 …                             “2nd order differences”

                           0                                      “3rd order differences”

 

 

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

 

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

 

 

 

 

 

In general, if the 0th diagonal has entries c0, c1, c2, …, cp, 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 0th diagonal is 0, 1, 2, 0, 0, 0

 

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

 

 

 

 

 

 

 

This process yields the sum of hn for any sequence