How many numbers are required to define a sequence without stating a rule/function for generating the next term in the sequence?

Question

I'm wondering if there is some minimum number of numbers required to define a sequence, without explicitly stating the rule that generates the next term in the sequence. For instance if I write $(1,a_2,a_3,...)$, and hide the remaining numbers in the sequence behind $(a_2,a_3,...)$, we don't know what the sequence is or what rules define it. If I then write $(1,2,a_3,...)$, it still isn't clear. Is the rule for determining the next number in the sequence $a_{i+1}=2 a_i$? Is it $a_{i+1}=a_i+1$?

If I write $(1,2,4,8,16)$, it's clear the rule is $a_{i+1}=2a_i=2^{i-1}$. Could I even shorten this to $(1,2,4,...)$ and figure this out? Is this an example of the minimum number of numbers required to define the sequence of powers of $2$. As J.W. Tanner says in the comments, you can come up with a polynomial whose first terms are $1,2,4,8,16,23$, so apparently not.

How about the Fibonacci sequence? I think it's clear what the rule is if I write $(0,1,1,2,3,5,8,...)$, even if I hadn't learned of this sequence before. I can't learn anything from $(0,1)$. What about $(0,1,1)$? It's hard to decide if I can learn the rule from this or if I need more numbers from the sequence. Typically you would just say $a_0=0,a_1=1,$ and $a_{i} = a_{i-1} + a_{i-2}$ for $i>1$. But that defeats the point of the question. The point is to ask how many numbers we need in order to define/learn the sequence without explicitly stating the rule that generates the next term in the sequence, and writing $a_{i} = a_{i-1} + a_{i-2}$ is explicitly stating the rule.

How does this idea generalise?

Answer 1

Even your example of $1,2,4,8,16$ doesn't automatically mean that the sequence is uniquely defined by $a_i=2^{i-1}$

As humans, we would probably assume that was the sequence you meant, but we could also say that the sequence is defined by $$a_i=\frac{i^4}{24} - \frac{i^3}4+\frac{23i^2}{24}-\frac{3i}4+1$$ (which I found using WolframAlpha)

This then gives \begin{align}a_6&=\frac{6^4}{24} - \frac{6^3}4+\frac{23\times 6^2}{24}-\frac{3\times 6}4+1\\ &=31\end{align} as opposed to the $32$ you would expect.

Even if we then specify that the $6$th term is $32$, we then get a new generating function which then gives the $7$th term as $a_7=63$, again not $64$ as we expect.

So, the conclusion is that you can never uniquely define a sequence simply from its first $n$ terms, you can only uniquely define a sequence with its generating function

Answer 2

Consider the sequence $1,1,2,3.$ At first look, it seems to be the first terms of Fibonacci numbers, but it's not true that the only sequence which starts with $1,1,2,3,5$ are Fibonacci numbers.

Here we can say that these are the first terms of triangle read by rows in which row n lists A000041(n-1) 1's followed by the list of juxtaposed lexicographically ordered partitions of n that do not contain 1 as a part.

Or we can say these are the numbers of rooted trees with n vertices in which vertices at the same level have the same degree.

Or these are the terms generated by $a_n=\lfloor(3^n / 2^n)\rfloor$.

In your example the terms of $1,2,4,8,16$ are not necessarily generated by $a_n=2^n$

For example we can say these are the coefficients of expansion of $$\frac{(1-x)}{(1-2^x)}$$ in powers of $x$.

Or these are the numbers of positive divisors of $n!$.

Or these are Pentanacci Numbers.

For more information look at :oeis.org

Answer 3

If you have $n$ data points, there is always a polynomial, of degree at most $n-1$, that it fits. So in general, there are never enough data points.
For example, given $1,2,4,\ldots$, the rule might be $a_n=(n^2-n+2)/2$.
Conversely, if you know what the function 'looks like', each data point can narrow it down. If you know it is linear, $a_n=an+b$, two datapoints are enough. $a=a_2-a_1$, then $b=a_1-a$. If you know it is quadratic, three points are enough.
If you know $a_n=pa_{n-1}+qa_{n-2}$, it turns out you need four points to find $p$ and $q$. $a_3=pa_2+qa_1$ gives one equation and $a_4=pa_3+qa_2$ gives another. Two equations are usually enough the two values $p$ and $q$

Answer 4

By the strong law of small numbers, any term could be next.

for powers of 2, you have recurrences like $a_n=2a_{n-1}$ or $a_n=a_{n-1}+2a_{n-2}$ etc. that work out to powers of two, but you could have something like the first 5 defined and then $$a_n=a_{n-2}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5}$$ in which case the next value is 31, then 60, then ...

You can also define fibonacci with itself, $$a_{n+z}= F_{z+1}a_n+F{z}a_{n-1}$$ which only takes the first $z+2$( including 0) terms being defined.

Just because there's a possible rule, does not rule out 2 million others.

Answer 5

There is an uncountably infinite number of sequences of natural numbers (even ones starting $a_0, a_1, a_2, a_3$, as anything whatsoever can follow). That this is so is simple to prove by Cantor's diagonalization argument.