What is the next number in the sequence 1, 1, 1, 1?

If we let an be

an = (41/24)(n - 1)(n - 2)(n - 3)(n - 4) + 1

then we have

a1 = 1
a2 = 1
a3 = 1
a4 = 1
a5 = 42

Therefore the next number might as well be 42. The same trick can be pulled off with any given integer sequence. In fact, it can be any number you like. This is not particularly hard to prove.

If we have been given a sequence of numbers

a1, a2, a3, a4

and we wish to find the value of a5, then we are effectively being asked to find the the function f(n) such that

f(1) = a1
f(2) = a2
f(3) = a3
f(4) = a4

and then to evaluate f(5). Now, as we all know, if we are given any two points we can find a straight line through them. Given any three points we can find a parabola

f(x) = b2x2 + b1x + b0

through them. Correspondingly, given any n points on a graph, we can find a polynomial of degree n - 1:

f(x) = b0 + b1x + ... + bn-1xn-1

which will go through of all of them. (Well, you can't if two points are directly above each other, but this is obviously impossible in this case.) This is called Lagrange interpolation. So suppose we know

f(1) = a1
f(2) = a2
...
f(n - 1) = an-1

and we want an to be 42. To find f(x), we have to solve the set of simultaneous equations;

f(1) = b0 + b1 + ... + bn-1 = a1
f(2) = b0 + 2b1 + ... + 2n-1bn-1 = a2
...
f(n) = b0 + nb1 + ... + nn-1bn-1 = an = 42

We have n equations with n unknowns (being the bk). The solution will yield a polynomial f(x) which satisfies our simultaneous equations and additionally has f(n) = an, for any given an. So for any integer sequence, you can arbitrarily pick your own next number and find a polynomial that proves you correct.

This is a very pedantic point to make, but you have to be a pedant to be a mathematician, because making unjustified assumptions while answering questions can be catastrophic. However, often the answer in questions like these is either fairly obvious or easy to find, so while this technique is an entertaining party trick (if one is at a particularly dull party), it's usually quicker to just find the next integer by traditional methods.

Back to Blog
Back to Things Of Interest

Facebook Twitter Reddit Email Hacker News StumbleUpon