1
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ I could come up with a polynomial whose first terms are $1, 2, 4, 8, 16, 23$ $\endgroup$ – J. W. Tanner Feb 5 '20 at 11:12
  • 1
    $\begingroup$ 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$" $\endgroup$ – user715522 Feb 5 '20 at 11:13
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.