The well-known Fibonacci Sequence is generated by the simple recursive formula
The first few terms are
Of course, choosing and as the first two terms is rather arbitrary, so let's replace them by general natural numbers and . Then, we get the recursive definition
The Fibinacci numbers have many special properties (which have been called and used many times), but why should these properties be limited to Fibonacci numbers? If we can find other starting values so that then we can use the properties of general Fibonacci sequences to find relations involving and maybe solve a problem.
But which numbers occur in general Fibonacci sequences?
Obviously, every number occurs in the sequence starting with and at .
But it also occurs in , and so on.
This makes a total of sequences that contain .
Are there more? Is there a formula or a asymptote to the number of sequences that contain ? Which have the most occurences?
For searching Fibonacci sequences that contain , let's sort them by index.
How many starting values are there so that ? We've already solved this as the number of natural numbers so that is also a natural number. There are possible values for .
Now, . This is equivalent to which has solutions.
. This has solutions, unless , then it has solutions.
From now on, I won't write exact solutions any more but rather the asymptotic number of solutions. So, and , using Big O Notation.
. This has asymptotically solutions since there are about naturals less than , but only of them can be reached by taking steps of size .
There are approximately naturals less than that are divisible by , but only of them can be reached with steps of size , so the equation has about
In total, for a given , there are approximately
Fibonacci-like sequences that contain at some position.