## Modeling Sequences with Polynomials

November 11, 2010 at 20:10 (math.RA, mathematica)

Suppose I asked you to find the next term in the sequence

2, 4, 6, 8, 10, …

Of course the expected answer is 12. But then I could tell you that these terms correspond with the formula

$f(n) = -2 + \frac{197}{30}n - \frac{15}{4}n^2 + \frac{17}{12}n^3 - \frac{1}{4}n^4 + \frac{1}{60}n^5$

so the actual sequence has

2, 4, 6, 8, 10, 14, 26, 58, 130, 272, …

This illustrates a common misconception that there is a unique solution to these sorts of problems. In fact, starting with the first five evens, we can pick any real number as the sixth term and find a polynomial of degree at most 5 to model it using some basic linear algebra.

In general, when given the first $n>0$ terms of a sequence, we can find a polynomial of degree at most $n-1$ that will fit those terms. We can do so by solving a system of linear equations whose form can easily be worked out on paper by looking at a few small cases; this technique is described in detail in the article “When Every Answer Is Correct: Why Sequences and Number Patterns Fail the Test”, by Donald L. White. Another way to find a polynomial involves finite differences, but I won’t go into that here; if you’re interested, see this thread on MHF, or do some internet searches.

Here is some Mathematica code I wrote to find a polynomial given a list of terms. There should be a more concise way to write it; I’m not very versed in Mathematica shortcuts.

SeqPolyFit[L_] := (
len = Length[L];
M = Table[i^j, {i, 1, len}, {j, 0, len - 1}];
S = LinearSolve[M, L];
Sum[S[[i]] * n^(i - 1), {i, 1, len}]
)


Example usage:

I couldn’t find an online tool that does this computation, although it seems like someone would have made one by now. Maybe I’ll make one down the road.