The Theorem of Finite Differences

Raise the natural numbers to some power, say the cube, and lay the results out in a row. We thus have the sequence

0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, etc.

Next, subtract from each cube its lower neighbor and lay out the results in a row. These are the first-order differences and they comprise

1, 7, 19, 37, 61, 91, 127, 169, 217, 271, etc.

The second-order differences, calculated in the same way from the first-order differences, then comprise

6, 12, 18, 24, 30, 36, 42, 48, 54, etc.

Finally, the third-order differences all equal six.

In general, for any n-th power of the natural numbers or for certain n-th order polynomials the n-th order difference is a constant: that statement lays out for us in simple form the theorem of finite differences. As a further example I will lay out here the difference table for the 4-th power of the natural numbers up to ten, placing each difference under its subtrahend. So we have

x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

x^{4} |
0 | 1 | 16 | 81 | 256 | 625 | 1296 | 2401 | 4096 | 6561 | 10000 |

^{4}_{1} |
1 | 15 | 65 | 175 | 369 | 671 | 1105 | 1695 | 2465 | 3439 | 4641 |

^{4}_{2} |
14 | 50 | 110 | 194 | 302 | 434 | 590 | 770 | 974 | 1202 | 1454 |

^{4}_{3} |
36 | 60 | 84 | 108 | 132 | 156 | 180 | 204 | 228 | 252 | 276 |

^{4}_{4} |
24 | 24 | 24 | 24 | 24 | 24 | 24 | 24 | 24 | 24 | 24 |

We can now reverse that analysis and synthesize the zeroth-order difference (the original function of x, the fourth power in this case) from the sequence of remainders in the column headed zero. We know that the x-th value of f(x) equals the sum of the first x values of the first-order difference: thus, for example, we have 1+15+65+175 = 256 for x = 4. But each of the addenda in that sequence contains the remainder one once, so that remainder contributes itself four times to the sum. Likewise, the second-order remainder 14 appears in each second-order difference once, so it contributes itself 1, 2, and 3 times respectively to each of the first-order differences and, thus, contributes itself 1+2+3 = 6 times to the final sum 256. But that sum comprises the first-order Gaussian sum for x-1 in this case. In like manner we show that the third-order remainder 36 contributes itself to the final sum a number of times equal to the second-order Gaussian sum for x-2. In general, then, the j-th order remainder contributes itself to the final sum comprising f(x) a number of times equal to the (j-1)-th order Gaussian sum for x-(j-1).

But those Gaussian sums comprise elements of a row in Pascal's triangle. If we count the zero at the head of the column of remainders in the table as the zeroth-order remainder, then we can write the sum for the n-th power of x as

(Eq'n 1)

What I have done above looks like something less than a proper deductive proof of the proposition encoded in Equation 1, but it seems solid enough. My analysis leaves little room for surprises that would invalidate it, so I seem to have something more than an inductive proof. For now I will leave open the question of whether I can make a proper axiomatic-deductive proof of the proposition or whether its origin in multiple subtractions necessitates that it remain a kind of deductive-inductive hybrid proof.

Equation 1 resembles the scalar (or dot) product of two vectors, the sum of component-by-component partial products. That resemblance extends to the vector analogues themselves: we have the components of what I call the Pascal feignvector given by

(Eq'n 2)

for all values of the index i from 0 to n and the components of what I call the Babbage feignvector for the given value of n, which components I designate as

(Eq'n 3)

These sets do not, of course, comprise true vectors: they lack the appropriate geometric transformation properties and thus resemble true vectors only to the extent of comprising ordered sequences of components. In that notation Equation 1 becomes

(Eq'n 4)

in which equation we follow the convention of automatically summing over all relevant values of repeated indices.

I have already discussed Pascal's triangle in the essay on Gaussian sums, so I won't go into it here.

Each of the feignvectors [B;n] comprises a row of what I call Babbage's triangle. In accordance with Equation 3 I laid out the Babbage triangle like this

n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

1 | 1 | |||||||

2 | 1 | 2 | ||||||

3 | 1 | 6 | 6 | |||||

4 | 1 | 14 | 36 | 24 | ||||

5 | 1 | 30 | 150 | 240 | 120 | |||

6 | 1 | 62 | 540 | 1560 | 1800 | 720 | ||

7 | 1 | 126 | 1806 | 8400 | 16800 | 15120 | 5040 | |

8 | 1 | 254 | 5796 | 40824 | 126000 | 191520 | 141120 | 40320 |

You can see an alternate version of that array and of Equation 5, the algorithmic generator of it, at http://mycetes.pwp.blueyonder.co.uk/babbage/de1maths.htm.

Each row of that array represents the feignvector for the power shown in the column headed by the letter n. The diagonal array of numbers at the upper right of the array clearly comprises the set of the factorials of the natural numbers in row order (i.e. the last element in the n-th row equals n!). Inspection of my original version of that figure led me to discern, after some time, that each element in column #2 equals twice the sum of the element above it and one. After some more time, during which I inspected the diagram further (i.e. sat and stared at it, waiting for inspiration to strike), I formed a conjecture and then tested and verified it with the column #3 and then with other elements of the array. The rule that I thus derived states that the element in the n-th row and the i-th column equals i times the sum of the element above it and the element above it in the column to the left; that is,

(Eq'n 5)

That equation bears a strong resemblance to the algorithmic equation that generates Pascal's triangle; indeed, only differs from it in the multiplication of the sum by the column number.

Instead of that algorithm, though, I would
much prefer to have an equation analogous to Equation 2, by which equation I
could calculate [B;n]_{i} directly from the values of n and i. As a
first step in that direction I divided the elements in each column of the
Babbage triangle by the number at the head of the column, which number equals
the factorial of the column index. That process yields

i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

n | ||||||||

0 | 1 | |||||||

1 | 1 | 1 | ||||||

2 | 1 | 3 | 1 | |||||

3 | 1 | 7 | 6 | 1 | ||||

4 | 1 | 15 | 25 | 10 | 1 | |||

5 | 1 | 31 | 90 | 65 | 15 | 1 | ||

6 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | |

7 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 |

Finding the algorithm that generates that triangle doesn't take long. We expect something similar to the algorithm expressed in Equation 5 and this triangle does not disappoint that expectation. We can generate any element of this reduced Babbage triangle by multiplying the element above the desired one by the column index and then adding to that product the element to its left. Thus, if we want to calculate the element of the sixth row , third column, we have (3x25)+15=90. So we have in general

(Eq'n 6)

We notice two facts about the triangle immediately: 1) the elements of the second diagonal comprise the set of the first Gaussian sums and 2) the elements of the second column comprise the successive powers of two, each less one. Each of those facts points to a path that leads to a solution of the problem that I stated above. Following the first of those paths, from mid-April to mid-June 2004, I made very little progress toward the solution. Then I followed the second path and found the desired solution in two days near the end of June.

Let's begin with the already given fact that

(Eq'n 7)

Now use that fact to generate the elements of the third column. We have

(Eq'n 8)

Using that result, then generate the fourth column using the same multiply and add algorithm to set up the series and then separating the terms of the series into suitable enmeshments to add up directly. We thus get

(Eq'n 9)

Continuing that procedure we obtain

(Eq'n 10)

(Eq'n 11)

With Equations 7 - 11 before us we can continue by induction and formulate the general rule that we seek:

(Eq'n 12)

Let me note that the recognition that the
coefficients of the j^{n} terms comprise the rows of Pascal's triangle
made this an easy solution to induce.

Multiplying Equation 12 by the factorial of the column index, which we divided out earlier, recovers the elements of the Babbage triangle for us:

(Eq'n 13)

Substituting that equation into Equation 1 by way of Equation 3 gives us at last

(Eq'n 14)

We certainly took the scenic route to reach that conclusion and we seem to have made very little progress in doing so. The formula on the right side of Equation 14 doesn't seem to offer any improvement over the outright n-fold multiplication of x, but we base that judgment upon an implicit intent to carry out the calculation with pencil and paper. If Charles Babbage had completed the construction of his Difference Engine, that formula would have provided the basis for the first mechanization of calculation. The success of that endeavor would have enabled Babbage to go on to build his Analytical Engine and begin the computer revolution a century before Atanasoff, Mauchly and Eckert did.

hcdg