Polynomial Differences

Find the polynomial $ Ax^5 + Bx^4 + Cx^3 + Dx^2 + Ex +F$ given:

\[\begin{array} {|r|r|}\hline f(1) & 1 \\ \hline f(2) & 1 \\ \hline f(3) & 2 \\ \hline f(4) & 3 \\ \hline f(5) & 5 \\ \hline f(6) & 8 \\ \hline  \end{array}\]

In the past I would have viewed this as a 6 variable linear system and given the complexity gone to linear algebra and matrices probably with a computer assist. 

But I saw a new way to approach this via @eylem_99 that relies on analyzing the delta or differences. The idea comes from a tool I’ve only ever seen used for making sense of polynomials.  Calculate the deltas between the values of a function: for instance from above f(2) -  f(1) = 0 and f(3) - f(2) = 1 and then calculate the second level deltas etc. If the interval between the starting values is constant then eventually after n iterations where n is the same as the degree of the equation you’ll reach a constant value.  You can prove this via algebra but essentially these deltas are approximations of the various derivatives. When you reach the nth level the derivative becomes constant and the approximation is completely accurate.

So its a fun exercise to do this on various polynomials and see what falls out. What had never occurred to me was this also can be used to reverse additional values for the function by generating the deltas in reverse!

So for example from the above values we can regenerate  f(0), f(-1), and f(-2) starting with constant delta -3 on the right:

-2   110             

          -74        

-1   36    46    

         -28  -25

0     8    21 11  

          -7 -14         -3

1     1     7 8  

            0 -6          -3

2     1     1 5

            1 -1          -3

3     2     0 2

            1 1          -3

4     3     1 -1

            2 0

5     5     1

            3

6     8

The final delta is actually $ f’’’’‘(x) $ and note that in general since the first and highest degree term in the polyomial is $Ax^5$ the fifth derivative works out to 5! * A. so $ A = - \frac{3}{5!} = - \frac{1}{40} $

At this point you could generate a simpler degree 4 equation by subtracting $Ax^5$ from all the values and then go and repeat the process recursively to find the value of B, C etc.

There are also a few more shortcuts that can be taken.  From above we can see f(0) = 8. This implies F = 8.  Now adding and subtracting complements f(1) and f(-1) and f(2) and f(-2) generates simpler linear equations for finding B,C,D, and E.

2B + 2D + 16 = 37 and -1/20 + 2C + 2E = -35

32B + 16D + 16 = 111 -32/20 + 16C + 4E = -109

From there its not to difficult to get the rest of the constants and certainly simpler than the matrix math. This is especially true if you don’t need the original equation and just want to find f(0) or f(8) for example.

A Bit Further A few years later I’ve learned that this technique was first discovered by Isaac Newton and led to Newton’s Forward Difference Formula or the backward version Newton’s Backward Difference Formula.

In particular what’s extra interesting is the relationship to the binomial coefficients. The tree form above shows part of what’s going on. We’re deriving the nodes farther down by subtracting the two parents but its essentially the same process as in Pascal’s triangle.

This is easier to see conceptually by looking at a few examples. I’m going to work out the forward and backwards for a degree polynomial with 3 values $a_0, a_1, $ and  $a_2 $  and  three top level differences $ \Delta_1 = a_1 - a_0$, $\Delta_2,$ and $\Delta_3 $ where the next few are the second and third level differences.

Computing Left to Right

$a_0$

                $a_1 - a_0$

$a_1$                                $a_2 - 2a_1 + a_0$

                $a_2 - a_1$                                          $a_3 - 3a_2 + 3a_1 - a_0$

$a_2$                                $a_3 - 2a_2 + a_1$

                $a_3 - a_2$

$a_3$

This tree is generated by computing the differences column by column from left to right. Notice how in each column the coefficients follow Pascal’s triangle. This is happening because we’re using the same rules to generate each level (with a slight variation because of the subtraction)

Backwards Example

$a_0$

                                           $\Delta_1$

$a_0 + \Delta_1$                                                            $\Delta_2$

                                           $\Delta_1 + \Delta_2$                                            $\Delta_3$

$a_0 + 2 \Delta_1 + \Delta_2$                                                $\Delta_3 + \Delta_2$

                                           $\Delta1 + 2\Delta_2 + \Delta_3$

$a_0 + 3 \Delta_1 + 3 \Delta_2 + \Delta_1$

This version is generated going column to column from right to left. This time every entry in the leftmost column has binomial coefficients.

Another interesting way of thinking about this is based on these examples if we let $a_0 = f(x), a_1 = f(x+1), a_2 = f(x+2) $ etc. and apply the result for from first tree:

\[\Delta_3 = {3 \choose 0} f(x+3) - {3 \choose 1} f(x+2) + {3 \choose 2} f(x+1) - {3 \choose 3} f(x)\]

But $ \Delta_3 $ is 0 for a 2nd degree polynomial so out pops this nice recurrence relation:

\[0 = {3 \choose 0} f(x+3) - {3 \choose 1} f(x+2) + {3 \choose 2} f(x+1) - {3 \choose 3} f(x)\]

Extra: Extension