Method of Finite Differences

Date: 10/12/2000 at 14:36:30
From: Victoria Gillett
Subject: Turning a series into an equation

I was given the equation 3n^2 - 4n - 2. By plugging in 1, 2, 3, 4, 5 
for n, I worked out the series:
     
     -3, 2, 13, 30, 53.

If I were given only the series, how would I work through the series 
in order to find it the equation?

Date: 10/12/2000 at 17:56:01
From: Doctor Greenie
Subject: Re: Turning a series into an equation

Hi, Victoria. Thanks for sending your question to us here at Dr. Math.

The most elementary method I know of to find the equation from the 
series is called the method of "finite differences." The key to this 
method is the fact that the equation is a polynomial of degree k if 
and only if the k-th row of differences generated by the series is 
constant. That probably doesn't mean anything to you if you haven't 
seen the method before; I'll show you the method for your series in a 
few moments.

I found an in-depth demonstration of WHY the method of finite 
differences works in "Finite Differences and Polynomials," from the 
Dr. Math archives, at the following URL:

   http://mathforum.org/dr.math/problems/harris.6.17.99.html   

Often you can find answers to the questions you have in the Dr. Math 
archives. It takes some practice to be able to find the information 
you are looking for (and of course sometimes the help you need is not 
in the archives). I found the above URL by going to the Dr. Math main 
page, clicking on the "Search the Archives" link, and searching on the 
phrase "finite difference." I had to click on the button that told 
the search to look for that exact phrase, since it would have found 
many unrelated URLs if it looked for the words "finite" and 
"difference" separately. Of course, in your case, you probably didn't 
know the term "finite differences," so you would not have been able to 
perform the same search.

Anyway, always be sure to take a minute or two to TRY to find answers 
to your questions in the archives before you send us your questions.

In my search, I did not find any place in the archives where an 
example of the use of the method of finite differences is provided, so 
I will demonstrate the method using your example. So, suppose I have 
the sequence:

     -3, 2, 13, 30, 53

and I need to find the polynomial expression that generates this 
sequence.

I start by writing out the terms of the sequence, with a bit of space 
between the entries:

     -3    2    13    30    53

Beneath this row I write a "first row of differences" - the numbers 
showing the differences between the successive numbers in the first 
row:

     -3    2    13    30    53
         5   11    17    23

It is absolutely essential that you understand what is being done 
here. The first entry in this "first row of differences" is 5 because 
the difference between the first and second numbers in the original 
row is 5; the second entry in this row is 11 because the difference 
between the second and third numbers in the original row is 11; and so 
on. Each entry in each successive row of differences is written 
between the two entries in the preceding row to help the reader see 
where it came from.

I see that the numbers in my first row of differences are not all the 
same, so I next write a "second row of differences," showing the 
differences between the successive entries in the first row of 
differences:

     -3    2    13    30    53
         5   11    17    23
           6     6     6

Here the differences are all the same; my method of finite differences 
tells me that, since this occurs in my second row of differences, the 
polynomial that generates the sequence will be of degree 2 - that is, 
it is a polynomial of the form:

     f(n) = an^2 + bn + c   ..........................[1]

To find the values of a, b, and c for your example (we know we should 
end up with a = 3, b = -4, and c = -2, because we know the generating 
polynomial was 3n^2-4n-2), we can substitute values of n = 1, n = 2, 
and n = 3 into the polynomial [1] above. For example, if n = 1, we 
know the polynomial generates the first number in the sequence, which 
is -3, so we get the equation:

     f(1) = a*(1^2) + b*1 + c = -3

or

     a + b + c = -3   ................................[2]

Evaluating f(2) and f(3) similarly (these are the 2nd and 3rd numbers 
in the sequence), we find

     4a + 2b + c = 2   ...............................[3]

and

     9a + 3b + c = 13   ..............................[4]

Equations [2], [3], and [4] are a system of 3 equations in 3 unknowns 
that can be solved; the solution is (as it must be):

     (a,b,c) = (3,-4,-2)

Write back if you need help solving systems of 3 equations in 3 
unknowns - or better yet, try finding help on that in our archives.

Note that I needed 3 equations because I had 3 unknowns. I could have 
used any of the numbers in the sequence to build these three 
equations. For instance, I could have used the 5th number in the 
sequence to get the equation

     f(5) = 25a + 5b + c = 53

However, I chose to use the first three numbers in the sequence so 
that the coefficients in my system of 3 equations and 3 unknowns would 
be as small as possible.

If your original sequence had been generated by a polynomial of degree 
4, that is:

     f(n) = an^4 + bn^3 + cn^2 + dn + e

then you would have found that it was not until the fourth row of 
differences that the differences were constant; then you would have 5 
unknowns (a, b, c, d, and e) so you would need 5 equations in those 
variables to solve for a, b, c, d, and e; to get those equations you 
would use the first 5 terms of your sequence.

I remember having fun as a young math student (probably between about 
7th and 9th grades) playing with this method and discovering how 
nicely it works. If you have the time and interest, make up another 
polynomial of degree 2, generate the sequence, and then go through the 
method again to see if you can get back to your original polynomial by 
starting from the numbers in the sequence. Then maybe you can get 
really bold and try the same thing with an original polynomial of 
degree 3.

Have fun!

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/