Find the next number puzzles

[mchainmail]

For problems such as "what's the next number in the sequence: ...", I know it is possible to create an nth degree polynomial that satisfies all points. Does anyone have more information on this, or how to go about creating the polynomial?

[Qaanol]

For problems such as "what's the next number in the sequence: ...", I know it is possible to create an nth degree polynomial that satisfies all points. Does anyone have more information on this, or how to go about creating the polynomial?

This should have what you’re looking for. There’s a brief discussion of the matter on Wikipedia as well.

[Tirian]

That wikipedia page is a little light on describing or even linking to the most practical method for generating the interpolation polynomial, so here's another link to the Lagrange technique.

[Qaanol]

Also, if you’re looking at that type of “puzzle”, you’ll probably want the next entry to be an integer. You can either just pick an arbitrary value of your choice and find the polynomial interpolating that, or you can leave that y as a variable to come up with a general expression.

[tomtom2357]

I don't know how to figure out the remaining coefficients of the interpolating polynomial, but here is a (sort of) easy way to find the first coefficient. Let the function f(x₁,y₁,x₂,y₂,...) evaluate the first coefficient of the interpolating polynomial between said points (this may seem circular, but recursion is needed to calculate this for more than two points). For two points this is easy f(x₁,y₁,x₂,y₂)=(y₂-y₁)/(x₂-x₁), now for the recursion bit, f(x₁,y₁,x₂,y₂,...,x_n-1,y_n-1,x_n,y_n)=(f(x₂,y₂,x₃,y₃,...,x_n,y_n)-f(x₁,y₁,x₂,y₂,...x_n-1,y_n-1))/(x_n-x₁)