# Finding the correct formula for a sequence

As already discussed a little bit in the chatroom the following question came to my mind while studying some sequences of natural numbers.

If you need to find closed formulas (not piecewise function or polynomials which interpolate the numbers) for sequences like

(i) 2-4-8-16-...

(ii) 1-8-64-512-...

the first thing you'll probably try is to find a rule how the numbers are build up. In (i) it seems to be that the next number is the previous number multiplied by the factor 2, in (ii) we always multiply the previous number by 8.

My question is; What is the minimum number of numbers you need to find an unique closed formula expression? Lets take for simplicity only the the natural numbers.

Is there for exmaple a sequence $a(n)=?$ where $a(1)=2,a(2)=4, a(3)=8,a(4)=16$ but $a(5)\not=32$ and if yes is there also a sequence where $a(5)=32$ but $a(6)\not=64$ and so on?

-
You will need more restrictions. Here are two examples: 2, 4, 8, 16, 42, 42, 42, 42 2, 4, 8, 16, 32, 2, 3, 5, 7 , 11, 13, 17 – PyRulez Jun 10 '13 at 12:59
(i) is obviously part of the sequence $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 56953,\ldots$ of numbers $n$ such that $n$ and $n^3$ have the same number of ones in binary expansion – Hagen von Eitzen Jun 10 '13 at 14:54

Whatever "rule" of the "formula" $f(n)$ you come up with, you can always say that $$h(n):=\begin{cases} f(n),& n\leq N \\ g(n),& n>N \end{cases}$$ is a new "rule" where $N$ and $g$ are completely arbitrary. Even more, for any finite sequence $a(1)$, $a(2)$, $\dots, a(N)$ you can come up with a formula $f$ (for example, a polynomial) that agrees with all $a(n)$ up to $N$, but you can force $f(N+1)$ to be arbitrary.

In a way, IQ test "continue the sequence" are mathematically ill-posed: there are infinitely many continuations of any sequence, and some of them may be equally "natural". However, sometimes you may think of finding the rule for the sequence with the smallest complexity, e.g. Kolmogorov complexity.

-

Sure. Given $n$ values, you can always construct a $n-1$ degree polynomial which matches those values. Since the first five numbers in your example are in GP, i.e. are increasing exponentially ($2^n$), it is unlikely that the resulting polynomial will grow fast enough to match $2^n$ for the next value of $n$ as well.

If $p(x)$ is a $n-1$ polynomial which satisfies $p(n)=2^n$ for $n=1,2,3,4$, then $p$ is:

$$p(x)=\frac 13(x^3-3x^2+8x)$$

(which comes from a simple WolframAlpha computation., taking $p(x) = ax^3+bx^2+cx+d$)

This can be done for any number of terms of the sequence you want to match.

Of course, the polynomial is only interesting if you can get it to match $n$ terms without requiring an $n-1$ polynomial, as then there are lesser chances of over-fitting occurring.

-