## Wednesday, February 19, 2014

### Polynomials as recurrence relations

if you have some amount of numbers you can find what the next one should be following the pattern for a degree p polynomial going through p+1 points. Like if you have -4.5, 2.3, 2, 1, you do 4*(-4.5)-6*(2.3)+4*(2)-1 and find the next number should be 11 so that a smooth curve could be drawn through the numbers if they were vertical values one apart horizontally on a graph. The 4, -6, 4, -1 are from the (p+2)th row of the Pascal's triangle.

To start consider the x^2 series starting with 0...
0, 1, 4
I noticed you can always find the next term by additions and subtractions of the initial 3 terms as follows:
4 + (4-1) + (4-1)-(1-0) = 9
This simplifies to the recurrence relationship:
A(n) = 3*(A(n-1) - A(n-2)) + A(n-3)
For example:
25 = 3*(16-9) + 4
And then I wondered what happens if you start it with other values than squares...
3, 8, 15
24 = 3*(15-8) - 3
I found the significance of this number is if you find the quadratic equation that fits these three points with any x values each a distance 1 apart, like here I randomly chose 4,5,6 as the x coordinates:

This function evaluated at the next integer 7 is 24.
The y values don't have to be positive or integers:
4.5, -3.2, 7
35.1 = 3*(7+3.2)+4.5
This function evaluated at 7 = 35.1

I also found that 3*(A(n+1)-A(n+2))+A(n+3) works equally well for finding A(n) going backwards knowing the 3 values to the right of A(n).

A similar formula can be found for cubic polynomials and it is:

Notice the coeffiecents in both this recurrence relationship and the one for squares if the A(n) is brought to the same side read as row number P-2 where P is the power of the polynomial in Pascals triangle with alternating signs negative first, I believe this is true in general.

Now to show this one for cubes works as well:
2, -5, 7.5, 16
-3 = 4*(16)-6*(7.5)+4*(-5)-(2)