Help with a different approach to extracting a polynomial equation from differences

It is well known that we can determine the degree of a polynomial can be found by finding when the differences are the same. i.e. if the second differences are the same, it is a polynomial of the 2nd degree and if the third differences are the same, it is a polynomial of the 3rd degree.

I've noticed that the coefficient of the highest degree in the equation can be determined by looking at the corresponding differences.

I.e. Given:

x   y    D1y  D2y  D3y
1   1    -4   12   12
2   -3   8    24   12
3   5    32   36
4   37   68
5   105


D here stands for Delta.

Right away, you can tell the the equation that matches this will be a polynomial of the third degree.

I've found that the relation between the differences for $\ \Delta\$ 3y will be related to the coefficient such that:

$\ a\ = \frac{\Delta 3y}{3!}$ where $\ a\$ is the coefficient for $\ x^3\$ Here this would be a = 2

What I would like to figure out is how to determine the coefficient for $\ x^2\$.

I know it is possible to create a matrix of equations and solve, but I am curious about a different approach.

My thought was to consider the equation as if it had no $\ x^3\$ term. So in order to do that I must change the differences as if $\ x^3\$ wasn't apart of the equation and this would let me extract the $\ x^2\$ term.

So I calculated out all of the $\ \Delta y\$ terms using an equation of just $\ 2x^3\$

x   y    D1y   D2y   D3y
1   2    14    24    12
2   16   38    36    12
3   54   74    48
4   128  122
5   250


I found that if I subtracted these values from the ones in the original equation I would be left with a constant second difference of -12 meaning that $\ b = \frac{-12}{2!}\ = -6$ where b is the coefficient of $\ x^2\$

What I can't figure out is a quick way to determine a value of $\ \Delta 2y\$ for $\ 2x^3\$ without adding up all of the numbers manually. If I could do this then the process would be much faster and thus this process would be more practical for polynomial equations of very large degrees.

-

From the first line of values of $x, y, D1y, D2y, D3y$ which are $1, 2, 14, 24, 12$, you can get that the polynomial is

$$\frac{12}{3!} (x-1)(x-2)(x-3) + \frac{24}{2!} (x-1)(x-2) + \frac{14}{1} (x-1) + 2 =2x^3$$

This is known as the method of differences. It should be easy to see how this generalizes. As to why this works, you should convince yourself

1. There exists a unique polynomial of degree $n$ in which the first $n-1$ differences are 0, and the last difference is 1.
2. Show that this polynomial has the form $\frac{1}{n!} \prod_{i=1}^n (x-i)$.
3. The starting value of $x$, which is 1, tells us that we want the polynomial product to start with $(x-1)$. If your starting value of $x$ was 0 (more common), then the polynomials will be shifted by 1 and hence have the form $x(x-1)(x-2) ...$.
-
Nice work, @Calvin, as usual ;-) – amWhy Jun 12 '13 at 23:10
I read the link you posted and from what I understand, the page refers to a method to calculate more values of y given a set of x and y values and while not knowing the original function. It didn't answer my question per se, but it did give me a great idea about how to solve my problem. I'm sort of wondering if you knew that before you directed me there :P. – Klik Jun 12 '13 at 23:15
You're last edit made things much clearer. I will accept this as answer. – Klik Jun 12 '13 at 23:24
@TheWeirdNerd This is a common method, and is the discrete version of Maclaurin expansion. Sadly I can't seem to find a good writeup of it anywhere. You can try this. – Calvin Lin Jun 12 '13 at 23:24