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

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?

• I could come up with a polynomial whose first terms are $1, 2, 4, 8, 16, 23$ – J. W. Tanner Feb 5 '20 at 11:12
• This kid of conclusion is not rue always true and just using some "guesses" you cannot always find the general recurrence relation, for example if you search "$1,1,2,3,5$" in oeis.org you will get 1241 results which start with "$1,1,2,3,5$" – user715522 Feb 5 '20 at 11:13

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

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$$

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.

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.
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.