Next Number in a Sequence

Date: 03/13/2002 at 07:15:40
From: KJS
Subject: Next number in a sequence -- infinite answers?

Question submitted via WWW:

This site rocks - I'm a computer scientist and math enthusiast.

My question: I recall reading not too long ago that there is an 
infinite number of mathematical answers to the question "What is the 
next number in this sequence: [x, y, z ...]?" (Where [x, y, z ...] is 
any sequence of integers.)  The reasoning (which I only vaguely 
recall) is that given any sequence, one can construct an infinite 
number of n-degree polynomials that satisfy the sequence, hence 
discern an infinite number of answers.  I further recall that because 
this was proven, all questions of this form have been removed from 
the SAT.

What is the proof for this?

Thanks!

Date: 03/13/2002 at 09:00:48
From: Doctor Rick
Subject: Re: Next number in a sequence -- infinite answers?

Hi, KJS.

I don't know about the SAT, but it is true that you can pick any 
answer you please to such a question and justify it using a 
polynomial. Of course, the intended answer is generally much "simpler" 
or more "satisfying," but these are subjective and not well-defined 
mathematical principles.

Here is how it works. Let's say the numbers given are a[1], a[2], ..., 
a[n-1], and you pick any number you wish for a[n]. We want to find a 
polynomial f(x) such that 

  f(1) = a[1]
  f(2) = a[2]
  ...
  f(n) = a[n]

We can find a polynomial of degree n-1 that will fit these conditions. 
For instance, a line (1st-degree polynomial) can be found that will 
pass through any two given points; a quadratic (2nd-degree polynomial) 
can be found that will pass through any three given points, etc.

Here is one way to find the polynomial that fits the conditions. First 
fit the points (1, a[1]) and (2, a[2]) with a line:

  y = (x-1)(a[2]-a[1]) + a[2]

We'll call this linear function f_1(x).

  f_1(x) = (x-1)(a[2]-a[1]) + a[2]

Now consider the quadratic function

  f_2(x) = b[1](x-1)(x-2) + f_1(x)

The first term is zero at both points x=1 and x=2; therefore 
f(1) = a[1] and f(2) = a[2], regardless of the value of b[1]. 
Evaluate f(3):

  f_2(3) = 2b[1] + f_1(3)

We want this to equal a[3]; we can solve for b[1] such that this is 
true:

  b[1] = (a[3] - f_1(3))/2

Do you see that the same process can be repeated indefinitely? Now 
that we have a polynomial that fits the first three points, we can add 
a cubic term:

  f_3(x) = b[2](x-1)(x-2)(x-3) + f_2(x)

Then we can solve for b[2] such that f_3(4) = a[4], and so on.

See also this item in our Dr. Math Archives:

  Predicting the Next Number in a Sequence
  http://mathforum.org/dr.math/problems/jwsmith.8.30.96.html   

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/   

Date: 03/13/2002 at 09:16:59
From: Doctor Peterson
Subject: Re: Next number in a sequence -- infinite answers?

Hi, KJS.

This page shows the method, call finite differences, that can be used 
to find the polynomial of degree n that fits n+1 points in a sequence:

   Method of Finite Differences
   http://mathforum.org/dr.math/problems/gillett.10.12.00.html   

You can extend the method to find polynomials of any degree greater 
than n as well; just choose the next term arbitrarily and find the 
polynomial that fits the extended sequence, and so on. This is not a 
new discovery, but it may have taken test-writers some time to realize 
its implications.

Here is a sample answer I've given to a sequence puzzle of the sort 
you are talking about:

   Terms and Rules
   http://mathforum.org/dr.math/problems/william.12.14.01.html   

Really, there's a lot more to this than just that you can find 
polynomial solutions. There are also infinitely many other sequences 
that follow more complicated rules than that - after all, a sequence 
doesn't even have to follow a rule you can state mathematically, but 
can be entirely random and still be called a sequence! So it's 
entirely meaningless to ask, "What is THE next number in THE sequence 
that starts with ...?" It could be absolutely anything. What they 
really mean is, "What is the next number in the sequence a test writer 
or puzzle maker is most likely to intend by the following?" In a way 
it's more psychology than math: what kind of sequence would a 
reasonably normal person think was "nice" enough to ask about? 

Some of the puzzles we get of this form are very simple (linear, for 
example); others are extremely tricky, but once you see the trick 
there's no question it's the "right" answer. You're looking for a 
sequence that is as easy as possible to define. And if the question 
were stated that way, it might be a reasonable test question, 
particularly if you were told what category of sequence it is. But 
usually they work much better as challenging puzzles than as test 
questions.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/