Is there a way of making "guess the next number in the sequence" rigorous?

Question

This is maybe more of a question for matheducators.SE than math.SE but I'm more interested in the math than the education.

A common problem given to middle and high school kids (at least in America) is something like "Find the next number in the sequence $2,4,8,16,\dots$". Now I am not against this problem, finding patterns is necessary not only in math but in life.

This question is not quite rigorous of course. The "obvious" next number is $32$ but it could easily be $-3324.22$ or whatever.

So my question is, is there a way to make this problem rigorous? Is there a way to ask this question that's rigorous, say appropriate for an introductory proof class at a university?

I think no, because the goal is to teach inductive reasoning. The goal is to guess a pattern and if there was some way of deductively arriving at the conclusion, it would violate the spirit of the problem. But I'm curious if anyone can think of some way.

Answer 1

There's a way to formalize what it means to solve this problem using Bayesian inference. It requires that you choose a prior distribution on some space of sequences. One relatively natural prior is the Kolmogorov prior, which is based on how complicated a program printing out the sequence is, and the corresponding solution method is called Solomonoff induction.

Unfortunately it's uncomputable, so you can't actually do it. But you can try to approximate it. As far as actual algorithms for solving this problem go, maybe check out computational learning theory.

For example, the virtue of recognizing $1, 2, 4, 8, \dots$ as the sequence of powers of $2$ is that powers of $2$ can be printed by a very short program, and so this sequence has a high prior probability.

Answer 2

You would need to constrain the possible sequences somehow, which takes all the fun out of pattern searching.

One way to do this is to impose a priori that the numbers must be the values of some unspecified polynomial in $n$ (the position of the number).

But there are many more "unmathematical" kinds of sequence, such as detecting similarities that are not defined by single mathematical maps (first add 1, then multiply by 2, then subtract 3, then add 4, then multiply by 5: you cannot infer this pattern unless you have been "taught" that the basic operations of algebra somehow belong together, and this is cultural).

Answer 3

The implied task is "Find the simplest function that generates these numbers." The trouble is, as you know, that this is difficult to make rigorous. Sometimes it can be made rigorous, using complexity theory; but this is not for middle and high school kids. Also it falls down on sequences like "JFMAMJ...". So if you set a problem like this, you had better be sure that there is only one simple answer. But you can never prove that there is only one simple answer! This, I suppose, is why some people refuse to take such problems seriously.

I think such problems do have a place in maths/intelligence tests, but they come with a risk.