Fun with Polynomials

When I started writing this post, it was to ask for help in solving a problem I'd been working on. I hit upon a solution halfway through, so I don't need help anymore, but I figured others might find it interesting, so I've outlined the problem and solution below. I do have one follow-up question, though. Details below the fold.

Consider the series defined by the polynomial x2:

0, 1, 4, 9, 16...

Now consider the series defined by the difference between consecutive elements in the series above:

1, 3, 5, 7...

Finally, consider the series defined by the difference between consecutive elements in that series:

2, 2, 2...

After two iterations of this process, we converge upon a series with a constant value. I'm fairly certain that all polynomials will eventually converge in this manner, and that the number of iterations needed will be equal to the polynomial's degree. For example, 2x3 + x2 + 4x + 7 will converge after three iterations:

0: 7, 14, 35, 82, 167, 302...
1: 7, 21, 47, 85, 135...
2: 14, 26, 38, 50...
3: 12, 12, 12...

I'm also fairly certain that the constant value of the final series derived thus from an Nth-degree polynomial will always be equal to the Nth derivative of that polynomial.

Now, rather than deriving such a series from a polynomial, we can simply construct one arbitrarily, starting with an arbitrary constant and working backwards, selecting for each series an arbitrary starting point, for example, we can choose a constant of 5 and work back four levels, with starting points of 3, 0, 7, and 4:

0: 5, 5, 5...
1: 3, 8, 13, 18...
2: 0, 3, 11, 24, 42...
3: 7, 7, 10, 21, 45, 87...
4: 4, 11, 18, 28, 49, 94, 181...

The problem I was trying to solve when I started this post was a general technique for determining the polynomial defining a series thus constructed. My first thought was that I could find the polynomial by repeatedly integrating, but calculus is designed for the summation of continuous functions rather than discrete series, so this produces only an approximation.

The actual solution turns out to be even easier. If you know that a series is defined by a polynomial of degree N, and know the first N + 1 terms of the series, you can generate a system of N + 1 linear equations which can then be used to solve for the coefficients of the polynomial. The polynomial defined by series 4 above, of course, takes the following form:

ax4 + bx3 + cx2 + dx + e

Now we just plug in values of x to generate linear equations:

x = 0: 0a + 0b + 0c + 0d + e = 4
x = 1: 1a + 1b + 1c + 1d + e = 11
x = 2: 16a + 8b + 4c + 2d + e = 18
x = 3: 81a + 27b + 9c + 3d + e = 28
x = 4: 256a + 64b + 16c + 4d + e = 49

We can then use standard linear algebra techniques to solve this system of equations and find the coefficients, which gives us the following:

(5x4 - 18x3 + 19x2 + 162x)/24 + 4

It would appear to be possible to use this technique for symbolic summation of a series defined by any arbitrary polynomial, though I have not attempted a formal proof of this (though I imagine that someone somewhere has already proven or disproven it).

The follow-up question: Is there a calculus-based method of solving the same problem, or was my original idea a dead end? I know that integral calculus is generally used to find the area under a continuous curve, but can it be adapted to the summation of discrete series?

Share this

The branch of mathematics

The branch of mathematics that deals with this is called finite difference equations. Check it out on Wikipedia, as my textbooks are packed in boxes right now.

Take a look at the book

Take a look at the book "Concrete Mathematics" by Donald Knuth, I think you'll enjoy it.

Take the derivative of the equation

Differencing is just a way to take a discrete derivative. Your series converge when you reach a point where the derivative is constant.

For your example: 2x3 + x2 + 4x + 7
You get the series: 7, 14, 35, 82, 167, 302...

The first derivative is: 6x2 + 2x + 4

The second derivative is: 12x + 2

The third derivative is: 12

Which is your converged value. The required number of derivatives (differences) is equal to the highest order of the polynomial.