Number of Fibonacci series that contain a certain integer

Question

In my question, I consider general Fibonacci sequences (sequences satisfying the recurrence relation $F_{n+2}=F_{n+1}+F_n$ independent of their starting value). Given two arbitrary different integers, the second being greater than the first, one can reverse the above equation to determine the lowest possible starting values of a Fibonacci series containing those two numbers. Let's call them elementary tuple of a certain Fibonacci series. Then a certain Fibonacci series starting with an elementary tuple (elementary Fibonacci series) is uniquely characterized by two different integers.

Now, can we calculate or estimate the number of elementary Fibonacci series that contain a certain integer $n$ where $n$ is not in the elementary tuple (otherwise the number would be infinite)? Is the question easier if we consider all Fibonacci series and not only the elementary ones?

PS: I tagged it under combinatorics since I expect the solution to come from there. Naturally, I don't know, so please delete it if appropriate.

Answer 1

Like Edward said, your problem breaks down to finding solutions to $F_na+F_{n+1}b = k$ for a given $k$.

If you're willing to consider negative $a$ and $b$, then there are an infinite number of solutions for every $n$, from Bezout's identity and

$$ \gcd(F_n, F_{n+1}) = \gcd(F_n, F_{n+1} - F_n) = \gcd(F_n, F_{n-1}) = \dots = \gcd(F_0, F_1) = 1$$

If you find a solution $(a,b)$ where $b \ge a$ then you can always switch to s smaller solution $(b-a, a)$. So it's only really worth looking at solutions where $a > b$.

One easy thing to start with is if your $k$, is divisible by any Fibonacci number $F_n$ then you can use $(a,b,n) = (\frac{k}{F_n},0,n)$, since $\frac{k}{F_n}F_n + 0 F_{n+1} = k$.

I suspect you're looking for solutions with positive $a$ and $b$ though.

If you pick an $n$ such that $F_nF_{n+1} < k$ then there will always be a positive $a$ and $b$. Perform integer division to find $i$ and $j$ such that $k = F_nF_{n=1}i + j$, and $i \ge 1$, and $0 \le j < F_nF_{n+1}$. Then use Bezout's identity to solve $a'F_n + bF_{n+1} = j$, which will always have a solution where $-F_{n+1} < a'$ and $0 \le b$, then we can assign $a = a' + iF_{n+1}$ (so $a > 0$) to get

$$\begin{align}a F_n + bF_{n+1} & = (a' + iF_{n+1})F_n + bF_{n=1}\\ & = iF_nF_{n+1} + a'F_n + bF_{n+1}\\ & = iF_nF_{n+1} + j\\ & = k\\ \end{align}$$

Answer 2

This isn't a complete answer, but since I can't comment yet (50 rep minimum), and since all of this can't fit in a comment anyways, I'll just post this.

Let the two starting integers be $a$ and $b$. Then the "elementary Fibonacci sequence" will start

a
b
a+b
a+2b
2a+3b
3a+5b
5a+8b
...

Aha! Note that every term in this sequence that is not in the "elementary tuple" has the form

$$F_na+F_{n+1}b$$

where $F_n$ is the $n$th Fibonacci number.

Now you can start counting. I haven't fully developed the next bit, so I'll just let off with an example. Suppose we want to find the sequences which contain $12$ (that is not in the elementary tuple). We want all integer solutions to $$F_na+F_{n+1}b=12$$ First, let $n=1$. We have $$a+b=12$$ for which there are five solutions which satisfy your conditions:

(a,b)
(1,11)
(2,10)
(3,9)
(4,8)
(5,7)

After that, we have $$a+2b=12$$ which has only one solution

(a,b)
(2,5)

It turns out there are no solutions beyond that, so there are exactly $6$ elementary Fibonacci sequences that contain the number $12$ and satisfies your conditions.

Hope this helped!