Número de serie de Fibonacci que contienen un cierto entero

Question

En mi pregunta, considero general de Fibonacci secuencias (secuencias que satisface la relación de recurrencia $F_{n+2}=F_{n+1}+F_n$ independiente de su valor inicial). Dadas dos arbitraria diferentes números enteros, el segundo es mayor que el primero, uno puede invertir la ecuación anterior para determinar el mínimo posible a partir de los valores de una serie de Fibonacci que contiene esos dos números. Vamos a llamarlos primaria de la tupla de una cierta serie de Fibonacci. Luego de cierta serie de Fibonacci, comenzando con una primaria de la tupla (primaria la serie de Fibonacci) es la única que se caracteriza por dos diferentes números enteros.

Ahora, podemos calcular o estimar el número de primaria de la serie de Fibonacci que contienen un cierto entero $n$ donde $n$ no está en la escuela primaria de la tupla (de lo contrario, el número sería infinito)? Es la pregunta más fácil si tenemos en cuenta toda la serie de Fibonacci y no sólo de la escuela primaria?

PS: yo etiquetados bajo la combinatoria desde entonces esperar que la solución venga de allí. Naturalmente, yo no sé, así que por favor eliminar si es apropiado.

Answer 1

Esto no es una respuesta completa, pero ya no puedo comentar aún (50 rep mínimo), y ya que todo esto no puede caber en un comentario de todos modos, voy a publicar esto.

Vamos los dos a partir enteros ser$a$$b$. Luego de la "primaria secuencia de Fibonacci"

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

Aha! Tenga en cuenta que cada término de esta secuencia que no está en la "escuela primaria de la tupla" tiene la forma

$$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$ (que no está en la primaria de la tupla). Queremos que todos los enteros soluciones a $$F_na+F_{n+1}b=12$$ En primer lugar, vamos a $n=1$. Tenemos $$a+b=12$$ de los cinco que existen soluciones que satisfacen las condiciones:

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

Después de eso, tenemos $$a+2b=12$$ que sólo tiene una solución

(a,b)
(2,5)

Resulta que no hay soluciones más allá de eso, por lo que hay exactamente $6$ primaria Fibonacci secuencias que contienen el número de $12$ y satisface sus condiciones.

Espero que esto ayudó!

Answer 2

Como dijo Edward, su problema se descompone en la búsqueda de soluciones a $F_na+F_{n+1}b = k$ para un determinado $k$.

Si usted está dispuesto a considerar negativo $a$$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 usted encuentra una solución a $(a,b)$ donde$b \ge a$, entonces siempre se puede cambiar a s más pequeños de la solución de $(b-a, a)$. Por eso, no es realmente vale la pena, buscando soluciones donde $a > b$.

Una cosa fácil para empezar es si su $k$, es divisible por cualquier número Fibonacci $F_n$, entonces usted puede utilizar $(a,b,n) = (\frac{k}{F_n},0,n)$, ya que el $\frac{k}{F_n}F_n + 0 F_{n+1} = k$.

Sospecho que usted está buscando soluciones positivas $a$$b$, aunque.

Si usted escoge una $n$ tal que $F_nF_{n+1} < k$ entonces siempre habrá un positivo $a$$b$. Realizar la división entera para encontrar $i$ $j$ tal que $k = F_nF_{n=1}i + j$, e $i \ge 1$, e $0 \le j < F_nF_{n+1}$. A continuación, utilice la identidad de Bezout para solucionar $a'F_n + bF_{n+1} = j$, lo que siempre tendrá una solución donde$-F_{n+1} < a'$$0 \le b$, entonces podemos asignar $a = a' + iF_{n+1}$ (por lo $a > 0$) para obtener

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