Associated Topics || Dr. Math Home || Search Dr. Math

### 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]

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.

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

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

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/

Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search