nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Series - Finding Differences and Polynomial Formulae

Section Contents
  1. Determining the Degree of an Equation from Its Values
  2. The Scheme
  3. Rationale
  4. Proof

Determining the Degree of an Equation from Its Values

There are times when we know a lot about a sequence. We can generate its values, find its sum, but we do not know the equation that produces the sequence. For instance, we know the natural numbers are 1, 2, 3, etc, and we can compute the sum of these for any number of terms, but we might not know the formula for the series.

If we knew, say, that the sum of the natural numbers was a quadratic equation, or polynomial of degree 2, then we know that the equation is ax2+bx+c. We do not know a, b, or c, but we can compute all the values we need to find the coefficients using simultaneous equations, or other techniques.

In the table below, n refers to the natural numbers, Sn is the sum of n terms,Δ or Δ1 is the first difference, being the differences between two successive sums, and Δ2 is the second difference, being the differences between successive Δ1 values.

n 1 2 3 4 5
Sn 1 3 6 10 15
Δ1
2 3 4 5
Δ2

1 1 1

We note that the Δ2 values, the second differences, are all the same: we have reached a constant value, and this means that the polynomial which is the equation for the sums of the natural numbers is a quadratic of the form ax2+bx+c. Had we reached the third difference, then the equation would be a cubic, and similarly for the other degrees.

The Scheme

Isaac Newton did a great deal of work on differences, and this led to the development of calculus. (Ironically, we will use calculus to give a rational for this scheme - ironically... because originally, it was the sums which were used to give a rational or proof of calculus!)

The scheme mentioned here is highly simplified.

First we write out some values for analysis, using integral x-values beginning at 0. Then we compute the differences between these values (the first differences) and successively compute the differences between the differences until we reach a repeating constant value (successive differences will be zero).

The difference (first, second, etc) at which we reach this constant value is the degree of the polynomial generating the values. For instance, in the table below, we have some values for various n's. The differences have been computed in the table.

n 0 1 2 3 4
f(n) 7 12 29 70 147
Δ1
5 17 41 77
Δ2

12 24 36
Δ3


12 12

Because the constant values appear at the third difference, we conclude that the equation producing our values is of degree 3. We can represent it as ax3+bx2+cx+d.

One way to proceed is to substitute values in our equation (ax3+bx2+cx+d) , and produce four simultaneous equations:
d=7 (n=0)                       [1]
a+b+c+d=12 (n=1)         [2]
8a+4b+2c+d=29  (n=2)   [3]
27a+9b+3c+d=70 (n=3)  [4]

First eliminate d from 2, 3, and 4:
a+b+c=5               [5]
8a+4b+2c=22        [6]
27a+9b+3c=63       [7]

Eliminate c from 6 and 7, using 5:
6a+2b=12               [8]
24a+6b=48              [9]

Eliminating b, we obtain:
6a=12, so a=2
Substituting a=2 in 8, we obtain:
12+2b=12, giving b=0
Substituting a=2 and b=0 in Equation 5:
2+0+c=5, so c=3

So the required equation is:
2x3+3x+7

Rationale

Consider the following numbers:
n 0 1 2 3
f(n) 0 1 2 3
Δ1
1 1 1
The formula is evidently y=x, and the constant values occur at the first difference, indicating, as we know, that the equation is of degree 1, and is a straight line. The constant values are the tangents to the curve, and because it is a straight line, they are all the same.

In the following diagram, the red rectangles represent the differences between successive y-values. As they are of unit width, they also approximate the tangent to the curve in the area.
differencesGraphThe tangent to a polynomial is always one degree less than the polynomial. So we would expect the differences to be represented by a curve which is one degree less than the actual curve.

Similarly, as we take more differences, approximating more tangents of tangents (or higher order differentials), these differences finally represent a constant value, a straight line parallel to the x-axis,.
From calculus, we note that the nth differential of a polynomial of degree n is the coefficient of the xn term times factorial n (This is an observation only, and in no way indicates that difference equations should behave in the same way). In our example, the third difference was 12, and the coefficient of the cubic term was 2: 12=3!*2.
Actually, however, the constant term obtained through this scheme is always n! times the coefficient of the polynomial where n is the degree of the polynomial (and also the nth differences where the constant value appears).

This area concerning differences is quite fascinating and was also fascinating to Newton, who filled his notebooks with discoveries in this area.
We can note the following
  1. The nth, Δn, difference,  is n!a0
  2. The n+1 difference, Δn+1, and higher differences, are zero

Proof

We have a polynomial f(x), where, in fact, the x's are specific values
poly[2.01]
Suppose the steps along the x axis are h. The next f(x) value at x+h is:
poly2 [2.02]
We recall, by definition:
p3 [2.03]
That is, the difference is equation 2.02 minus equation 2.01:
p4[2.03]
If we expand the left-hand parts of each term, we find:
p5[2.04]
The last term, an cancels, leaving a new constant, an-1h, (which will cancel out in the 2nd difference):
p6 [2.05]
Therefore for a polynomial of degree n, step h
p7[2.06]

This is reminiscent of:
p1[2.07]
Applying 2.06 again, we get:
p9[2.07]
If we apply the formula 2.06 n times, we have:
p10
Or
10c
Of course, because this is a constant (it is independent of x), the n+1 difference and further differences will be zero, so:
p11
When h=1, we can write for a polynomial of degree n:
10d




Ken Ward's Mathematics Pages