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
ax^{2}+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, S_{n}
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
S_{n}
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 ax^{2}+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 ax^{3}+bx^{2}+cx+d.
One way to proceed is to substitute values in our equation (ax^{3}+bx^{2}+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:
2x^{3}+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.
The
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 x^{n}
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
The nth, Δ^{n}, difference, is n!a_{0}
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
[2.01]
Suppose the steps along the x axis are h. The next f(x) value at x+h is:
[2.02]
We recall, by definition:
[2.03]
That is, the difference is equation 2.02 minus equation 2.01:
[2.03]
If we expand the left-hand parts of each term, we find:
[2.04]
The last term, a_{n} cancels, leaving a new
constant, a_{n-1}h, (which will cancel out in the
2nd difference):
[2.05]
Therefore for a polynomial of degree n, step h
[2.06]
This is reminiscent of:
[2.07]
Applying 2.06 again, we get:
[2.07]
If we apply the
formula
2.06 n
times, we have:
Or
Of course, because this is a constant (it is independent of x), the n+1 difference and further differences will be zero, so:
When h=1, we can write for a polynomial of degree n: