Número de series de Fibonacci que contienen un cierto número entero

Como dijo Edward, su problema se reduce a encontrar soluciones a$F_na+F_{n+1}b = k$para una dada$k$.

Si estás dispuesto a considerar negativo$a$y$b$, entonces hay un número infinito de soluciones para cada$n$, a partir de la identidad de Bezout y

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

Si encuentras una solución$(a,b)$dónde$b \ge a$entonces siempre puedes cambiar a una solución más pequeña$(b-a, a)$. Por lo tanto, solo vale la pena buscar soluciones en las que$a > b$.

Una cosa fácil para comenzar es si su$k$, es divisible por cualquier número de Fibonacci$F_n$entonces puedes usar$(a,b,n) = (\frac{k}{F_n},0,n)$, desde$\frac{k}{F_n}F_n + 0 F_{n+1} = k$.

Sospecho que estás buscando soluciones con positivo$a$y$b$aunque.

Si eliges un$n$tal que$F_nF_{n+1} < k$entonces siempre habrá algo positivo$a$y$b$. Realiza la división de enteros para encontrar$i$y$j$tal que$k = F_nF_{n=1}i + j$, y$i \ge 1$, y$0 \le j < F_nF_{n+1}$. Luego usa la identidad de Bezout para resolver$a'F_n + bF_{n+1} = j$, que siempre tendrá una solución donde$-F_{n+1} < a'$y$0 \le b$, entonces podemos asignar$a = a' + iF_{n+1}$(entonces$a > 0$) Llegar

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

Esta no es una respuesta completa, pero dado que aún no puedo comentar (mínimo de 50 repeticiones), y dado que todo esto no puede caber en un comentario de todos modos, solo publicaré esto.

Sean los dos enteros iniciales$a$y$b$. Entonces comenzará la "secuencia elemental de Fibonacci"

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

¡Ajá! Tenga en cuenta que cada término en esta secuencia que no está en la "tupla elemental" tiene la forma

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

dónde$F_n$es el$n$número de Fibonacci.

Ahora puedes empezar a contar. No he desarrollado completamente el siguiente bit, así que dejaré un ejemplo. Supongamos que queremos encontrar las sucesiones que contienen$12$(que no está en la tupla elemental). Queremos que todas las soluciones enteras sean

$$F_na+F_{n+1}b=12$$ Primero, deja $n=1$. Tenemos $$a+b=12$$ para el cual hay cinco soluciones que satisfacen sus condiciones:

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

Después de eso, tenemos

$$a+2b=12$$ que tiene una sola solución

(a,b)
(2,5)

Resulta que no hay soluciones más allá de eso, así que hay exactamente$6$secuencias elementales de Fibonacci que contienen el número$12$y cumple sus condiciones.

¡Espero que esto haya ayudado!