Next Number in a SequenceDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/