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:

SeqPolyFit Example

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.

Advertisements

2 Comments

  1. Jerry said,

    Expand[InterpolatingPolynomial[{2, 4, 6, 8, 10, 14}, n]] does the job as well in Mathematica. It works in Wolfram Alpha, too.

    • dansesacrale said,

      Wow, thanks for that info. I didn’t know about that, obviously.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: