Secuencia de Fibonacci

En matemáticas, la secuencia de Fibonacci es una secuencia en la que cada número es la suma de los dos anteriores. Los números que forman parte de la secuencia de Fibonacci se conocen como números de Fibonacci , comúnmente denotados F _n  . Muchos escritores comienzan la secuencia con 0 y 1, aunque algunos autores la comienzan desde 1 y 1 ^{[1] [2]} y algunos (como hizo Fibonacci) desde 1 y 2. A partir de 0 y 1, la secuencia comienza ^[3]

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

Los números de Fibonacci fueron descritos por primera vez en las matemáticas indias ya en el año 200 a. C. en un trabajo de Pingala sobre la enumeración de posibles patrones de poesía sánscrita formados por sílabas de dos longitudes. ^{[4] [5] [6]} Su nombre se debe al matemático italiano Leonardo de Pisa, también conocido como Fibonacci , quien introdujo la secuencia en las matemáticas de Europa occidental en su libro de 1202 Liber Abaci . ^[7]

Los números de Fibonacci aparecen inesperadamente a menudo en matemáticas, tanto que existe una revista entera dedicada a su estudio, Fibonacci Quarterly . Las aplicaciones de los números de Fibonacci incluyen algoritmos informáticos como la técnica de búsqueda de Fibonacci y la estructura de datos de montículo de Fibonacci , y gráficos llamados cubos de Fibonacci utilizados para interconectar sistemas paralelos y distribuidos. También aparecen en entornos biológicos , como la ramificación de los árboles, la disposición de las hojas en un tallo , los brotes de la fruta de una piña , la floración de una alcachofa y la disposición de las brácteas de una piña , aunque no se dan en todas las especies.

Los números de Fibonacci también están estrechamente relacionados con la proporción áurea : la fórmula de Binet expresa el n- ésimo número de Fibonacci en términos de n y la proporción áurea, e implica que la razón de dos números de Fibonacci consecutivos tiende a la proporción áurea a medida que n aumenta. Los números de Fibonacci también están estrechamente relacionados con los números de Lucas , que obedecen a la misma relación de recurrencia y con los números de Fibonacci forman un par complementario de secuencias de Lucas .

Los números de Fibonacci pueden definirse por la relación de recurrencia ^[8] y para n > 1 .$${\displaystyle F_{0}=0,\quad F_{1}=1,}$$$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$

En algunas definiciones más antiguas, se omite el valor , de modo que la secuencia comienza con y la recurrencia es válida para n > 2. [ ^{9] [10]}${\displaystyle F_{0}=0}$${\displaystyle F_{1}=F_{2}=1,}$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

Los primeros 20 números de Fibonacci F _n son: ^[3]

O 0	F1​	F2​	F3​	F4​	F 5	F6​	F7​	F 8	F9​	F10​	F11​	F 12	F13​	F 14	F 15	F16​	F 17	F 18	F 19
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

La secuencia de Fibonacci aparece en las matemáticas indias , en conexión con la prosodia sánscrita . ^{[5] [11] [12]} En la tradición poética sánscrita, había interés en enumerar todos los patrones de sílabas largas (L) de 2 unidades de duración, yuxtapuestas con sílabas cortas (S) de 1 unidad de duración. Contando los diferentes patrones de L y S sucesivos con una duración total dada se obtienen los números de Fibonacci: el número de patrones de duración m unidades es F _{m +1} . ^[6]

El conocimiento de la secuencia de Fibonacci fue expresado ya por Pingala ( c.  450 a. C.–200 a. C.). Singh cita la fórmula críptica de Pingala misrau cha ("los dos están mezclados") y a los eruditos que la interpretan en contexto diciendo que el número de patrones para m pulsos ( F _{m +1} ) se obtiene añadiendo una [S] a los casos F _m y una [L] a los casos F _{m −1} . ^[13] Bharata Muni también expresa conocimiento de la secuencia en el Natya Shastra (c. 100 a. C.–c. 350 d. C.). ^{[14] [4]} Sin embargo, la exposición más clara de la secuencia surge en la obra de Virahanka (c. 700 d. C.), cuyo propio trabajo se ha perdido, pero está disponible en una cita de Gopala (c. 1135): ^[12]

Las variaciones de dos metros anteriores [son la variación]... Por ejemplo, para [un metro de longitud] cuatro, al mezclar variaciones de metros de dos [y] tres, sucede cinco. [resuelve los ejemplos 8, 13, 21]... De esta manera, el proceso debe seguirse en todas las mātrā-vṛttas [combinaciones prosódicas]. ^[a]

A Hemachandra (c. 1150) también se le atribuye el conocimiento de la secuencia, ^[4] escribiendo que "la suma del último y el anterior al último es el número... del siguiente mātrā-vṛtta". ^{[16] [17]}

La secuencia de Fibonacci aparece por primera vez en el libro Liber Abaci ( El libro del cálculo , 1202) de Fibonacci ^{[18] [19]} donde se utiliza para calcular el crecimiento de las poblaciones de conejos. ^{[20] [21]} Fibonacci considera el crecimiento de una población de conejos idealizada ( biológicamente irreal) , asumiendo que: una pareja reproductora de conejos recién nacidos se coloca en un campo; cada pareja reproductora se aparea a la edad de un mes, y al final de su segundo mes siempre producen otra pareja de conejos; y los conejos nunca mueren, sino que continúan reproduciéndose para siempre. Fibonacci planteó el problema matemático del conejo : ¿cuántas parejas habrá en un año?

• Al final del primer mes se aparean, pero todavía sólo queda una pareja.
• Al final del segundo mes producen una nueva pareja, por lo que hay 2 parejas en el campo.
• Al final del tercer mes, la pareja original produce una segunda pareja, pero la segunda pareja solo se aparea para gestar durante un mes, por lo que hay 3 parejas en total.
• Al final del cuarto mes, la pareja original ha producido otra nueva pareja, y la pareja nacida hace dos meses también produce su primera pareja, totalizando 5 parejas.

Al final del mes n , el número de parejas de conejos es igual al número de parejas maduras (es decir, el número de parejas en el mes n – 2 ) más el número de parejas vivas el mes pasado (mes n – 1 ). El número en el mes n es el n -ésimo número de Fibonacci. ^[22]

El nombre "secuencia de Fibonacci" fue utilizado por primera vez por el teórico de números del siglo XIX Édouard Lucas . ^[23]

Como toda secuencia definida por una recurrencia lineal homogénea con coeficientes constantes , los números de Fibonacci tienen una expresión en forma cerrada . ^[24] Se la conoce como fórmula de Binet , llamada así por el matemático francés Jacques Philippe Marie Binet , aunque ya era conocida por Abraham de Moivre y Daniel Bernoulli : ^[25]

$${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{ n}}{\sqrt {5}}},}$$

dónde

$${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\aproximadamente 1,61803\,39887\ldots }$$

es la proporción áurea , y ψ es su conjugado : ^[26]

$${\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \sobre \varphi }\aproximadamente -0,61803\,39887\ldots .}$$

Dado que , esta fórmula también se puede escribir como${\displaystyle \psi =-\varphi ^{-1}}$

$${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}- (-\varphi )^{-n}}{2\varphi -1}}.}$$

Para ver la relación entre la secuencia y estas constantes, ^[27] observe que φ y ψ son ambas soluciones de la ecuación y, por lo tanto, las potencias de φ y ψ satisfacen la recursión de Fibonacci. En otras palabras,${\textstyle x^{2}=x+1}$${\displaystyle x^{n}=x^{n-1}+x^{n-2},}$

$${\displaystyle {\begin{aligned}\varphi ^{n}&=\varphi ^{n-1}+\varphi ^{n-2},\\[3mu]\psi ^{n}&=\psi ^{n-1}+\psi ^{n-2}.\end{aligned}}}$$

De ello se deduce que para cualesquiera valores a y b , la secuencia definida por

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

satisface la misma recurrencia,

$${\displaystyle {\begin{aligned}U_{n}&=a\varphi ^{n}+b\psi ^{n}\\[3mu]&=a(\varphi ^{n-1}+\varphi ^{n-2})+b(\psi ^{n-1}+\psi ^{n-2})\\[3mu]&=a\varphi ^{n-1}+b\psi ^{ n-1}+a\varphi ^{n-2}+b\psi ^{n-2}\\[3mu]&=U_{n-1}+U_{n-2}.\end{aligned} }}$$

Si se eligen a y b de modo que U ₀ = 0 y U ₁ = 1 , entonces la secuencia resultante U _n debe ser la secuencia de Fibonacci. Esto es lo mismo que exigir que a y b satisfagan el sistema de ecuaciones:

$${\displaystyle \left\{{\begin{aligned}a+b&=0\\\varphi a+\psi b&=1\end{aligned}}\right.}$$

que tiene solucion

$${\displaystyle a={\frac {1}{\varphi -\psi }}={\frac {1}{\sqrt {5}}},\quad b=-a,}$$

produciendo la fórmula requerida.

Tomando los valores iniciales U0 y U1 _como constantes arbitrarias, una solución más general es _:

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

dónde

$${\displaystyle {\begin{aligned}a&={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{aligned}}}$$

Dado que para todo n ≥ 0 , el número F _n es el entero más cercano a . Por lo tanto, se puede hallar redondeando , utilizando la función del entero más cercano:${\textstyle \izquierda|{\frac {\psi ^{n}}{\sqrt {5}}}\derecha|<{\frac {1}{2}}}$${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$$${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.}$$

De hecho, el error de redondeo se vuelve rápidamente muy pequeño a medida que n crece, siendo menor que 0,1 para n ≥ 4 y menor que 0,01 para n ≥ 8. Esta fórmula se invierte fácilmente para encontrar un índice de un número de Fibonacci F :$${\displaystyle n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.}$$

En lugar de utilizar la función floor se obtiene el índice más grande de un número de Fibonacci que no es mayor que F : donde , , ^[28] y . ^[29]$${\displaystyle n_{\mathrm {más grande} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,}$$${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}$${\displaystyle \ln(\varphi )=0,481211\ldots }$${\displaystyle \log _{10}(\varphi )=0,208987\ldots }$

Como F _n es asintótico a , el número de dígitos en F _n es asintótico a . En consecuencia, para cada entero d > 1 hay 4 o 5 números de Fibonacci con d dígitos decimales.${\displaystyle \varphi ^{n}/{\sqrt {5}}}$${\displaystyle n\log _{10}\varphi \aproximadamente 0,2090\,n}$

De manera más general, en la representación de base b , el número de dígitos en F _n es asintótico a${\displaystyle n\log _{b}\varphi ={\frac {n\log \varphi }{\log b}}.}$

Johannes Kepler observó que la proporción de números consecutivos de Fibonacci converge . Escribió que "como 5 es a 8, así es 8 a 13, prácticamente, y como 8 es a 13, así es 13 a 21 casi", y concluyó que estas proporciones se aproximan a la proporción áurea ^{[30] [31]}${\displaystyle \varphi \colon }$ $${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$$

Esta convergencia se mantiene independientemente de los valores iniciales y , a menos que . Esto se puede verificar utilizando la fórmula de Binet. Por ejemplo, los valores iniciales 3 y 2 generan la secuencia 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... . La proporción de términos consecutivos en esta secuencia muestra la misma convergencia hacia la proporción áurea.${\displaystyle U_{0}}$${\displaystyle U_{1}}$${\displaystyle U_{1}=-U_{0}/\varphi }$

En general, , porque la relación entre números de Fibonacci consecutivos se aproxima a .${\displaystyle \lim _{n\to \infty }{\frac {F_{n+m}}{F_{n}}}=\varphi ^{m}}$${\displaystyle \varphi }$

Dado que la proporción áurea satisface la ecuación$${\displaystyle \varphi ^{2}=\varphi +1,}$$

Esta expresión se puede utilizar para descomponer potencias superiores como una función lineal de potencias inferiores, que a su vez se pueden descomponer hasta una combinación lineal de y 1. Las relaciones de recurrencia resultantes producen números de Fibonacci como coeficientes lineales : Esta ecuación se puede demostrar por inducción en n ≥ 1 : Para , también es el caso de que y también es el caso de que${\displaystyle \varphi ^{n}}$${\displaystyle \varphi }$$${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$$${\displaystyle \varphi ^{n+1}=(F_{n}\varphi +F_{n-1})\varphi =F_{n}\varphi ^{2}+F_{n-1}\varphi =F_{n}(\varphi +1)+F_{n-1}\varphi =(F_{n}+F_{n-1})\varphi +F_{n}=F_{n+1}\varphi +F_{n}.}$$${\displaystyle \psi =-1/\varphi }$${\displaystyle \psi ^{2}=\psi +1}$$${\displaystyle \psi ^{n}=F_{n}\psi +F_{n-1}.}$$

Estas expresiones también son verdaderas para n < 1 si la secuencia de Fibonacci F _n se extiende a números enteros negativos utilizando la regla de Fibonacci.${\displaystyle F_{n}=F_{n+2}-F_{n+1}.}$

La fórmula de Binet proporciona una prueba de que un entero positivo x es un número de Fibonacci si y solo si al menos uno de o es un cuadrado perfecto . ^[32] Esto se debe a que la fórmula de Binet, que se puede escribir como , se puede multiplicar por y resolver como una ecuación cuadrática en mediante la fórmula cuadrática :${\displaystyle 5x^{2}+4}$${\displaystyle 5x^{2}-4}$${\displaystyle F_{n}=(\varphi ^{n}-(-1)^{n}\varphi ^{-n})/{\sqrt {5}}}$${\displaystyle {\sqrt {5}}\varphi ^{n}}$${\displaystyle \varphi ^{n}}$

$${\displaystyle \varphi ^{n}={\frac {F_{n}{\sqrt {5}}\pm {\sqrt {5{F_{n}}^{2}+4(-1)^{n}}}}{2}}.}$$

Comparando esto con , se deduce que${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}=(F_{n}{\sqrt {5}}+F_{n}+2F_{n-1})/2}$

$${\displaystyle 5{F_{n}}^{2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2}\,.}$$

En particular, el lado izquierdo es un cuadrado perfecto.

Un sistema bidimensional de ecuaciones diferenciales lineales que describe la secuencia de Fibonacci es

$${\displaystyle {F_{k+2} \choose F_{k+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{k+1} \choose F_{k}}}$$denotado alternativamente$${\displaystyle {\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},}$$

lo que da como resultado . Los valores propios de la matriz A son y correspondientes a los respectivos vectores propios${\displaystyle {\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}}$ ${\displaystyle \varphi ={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}}$${\displaystyle \psi =-\varphi ^{-1}={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}}$$${\displaystyle {\vec {\mu }}={\varphi \choose 1},\quad {\vec {\nu }}={-\varphi ^{-1} \choose 1}.}$$

Como el valor inicial es$${\displaystyle {\vec {F}}_{0}={1 \choose 0}={\frac {1}{\sqrt {5}}}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}{\vec {\nu }},}$$

de ello se deduce que el término n es$${\displaystyle {\begin{aligned}{\vec {F}}_{n}&={\frac {1}{\sqrt {5}}}A^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}A^{n}{\vec {\nu }}\\&={\frac {1}{\sqrt {5}}}\varphi ^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}(-\varphi )^{-n}{\vec {\nu }}\\&={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}{\varphi \choose 1}\,-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}{-\varphi ^{-1} \choose 1}.\end{aligned}}}$$

A partir de esto, el n- ésimo elemento de la serie de Fibonacci puede leerse directamente como una expresión de forma cerrada :$${\displaystyle F_{n}={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}.}$$

De manera equivalente, el mismo cálculo se puede realizar mediante la diagonalización de A mediante el uso de su descomposición propia :

$${\displaystyle {\begin{aligned}A&=S\Lambda S^{-1},\\[3mu]A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}}$$

dónde

$${\displaystyle \Lambda ={\begin{pmatrix}\varphi &0\\0&-\varphi ^{-1}\!\end{pmatrix}},\quad S={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}.}$$

Por lo tanto, la expresión en forma cerrada para el n- ésimo elemento de la serie de Fibonacci viene dada por

$${\displaystyle {\begin{aligned}{F_{n+1} \choose F_{n}}&=A^{n}{F_{1} \choose F_{0}}\\&=S\Lambda ^{n}S^{-1}{F_{1} \choose F_{0}}\\&=S{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}S^{-1}{F_{1} \choose F_{0}}\\&={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}{\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&\varphi ^{-1}\\-1&\varphi \end{pmatrix}}{1 \choose 0},\end{aligned}}}$$

Lo cual nuevamente produce$${\displaystyle F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.}$$

La matriz A tiene un determinante de −1, y por lo tanto es una matriz unimodular 2 × 2 .

Esta propiedad se puede entender en términos de la representación de fracción continua para la proporción áurea φ :

$${\displaystyle \varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\ddots }}}}}}.}$$

Los convergentes de la fracción continua para φ son cocientes de números de Fibonacci sucesivos: φ _n = F _{n +1} / F _n es el n -ésimo convergente, y el ( n  + 1) -ésimo convergente se puede hallar a partir de la relación de recurrencia φ _{n +1} = 1 + 1 / φ _n . ^[33] La matriz formada a partir de convergentes sucesivos de cualquier fracción continua tiene un determinante de +1 o −1. La representación matricial da la siguiente expresión en forma cerrada para los números de Fibonacci:

$${\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}$$

Para un n dado , esta matriz se puede calcular en O (log n ) operaciones aritméticas, utilizando el método de exponenciación por cuadrado .

Tomando el determinante de ambos lados de esta ecuación se obtiene la identidad de Cassini ,$${\displaystyle (-1)^{n}=F_{n+1}F_{n-1}-{F_{n}}^{2}.}$$

Además, dado que A ⁿ A ^m = A ^{n + m} para cualquier matriz cuadrada A , se pueden derivar las siguientes identidades (se obtienen a partir de dos coeficientes diferentes del producto matricial , y se puede deducir fácilmente la segunda a partir de la primera cambiando n por n + 1 ),$${\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\[3mu]F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.\end{aligned}}}$$

En particular, con m = n ,$${\displaystyle {\begin{aligned}F_{2n-1}&={F_{n}}^{2}+{F_{n-1}}^{2}\\[6mu]F_{2n{\phantom {{}-1}}}&=(F_{n-1}+F_{n+1})F_{n}\\[3mu]&=(2F_{n-1}+F_{n})F_{n}\\[3mu]&=(2F_{n+1}-F_{n})F_{n}.\end{aligned}}}$$

Estas dos últimas identidades proporcionan una manera de calcular los números de Fibonacci recursivamente en O (log n ) operaciones aritméticas. Esto coincide con el tiempo necesario para calcular el n -ésimo número de Fibonacci a partir de la fórmula matricial de forma cerrada, pero con menos pasos redundantes si se evita volver a calcular un número de Fibonacci ya calculado (recursión con memorización ). ^[34]

La mayoría de las identidades que involucran números de Fibonacci se pueden demostrar usando argumentos combinatorios utilizando el hecho de que se puede interpretar como el número de secuencias (posiblemente vacías) de 1 y 2 cuya suma es . Esto se puede tomar como la definición de con las convenciones , lo que significa que no existe tal secuencia cuya suma sea −1, y , lo que significa que la secuencia vacía "suma" 0. A continuación, es la cardinalidad de un conjunto :${\displaystyle F_{n}}$${\displaystyle n-1}$${\displaystyle F_{n}}$${\displaystyle F_{0}=0}$${\displaystyle F_{1}=1}$${\displaystyle |{...}|}$

${\displaystyle F_{0}=0=|\{\}|}$

${\displaystyle F_{1}=1=|\{()\}|}$

${\displaystyle F_{2}=1=|\{(1)\}|}$

${\displaystyle F_{3}=2=|\{(1,1),(2)\}|}$

${\displaystyle F_{4}=3=|\{(1,1,1),(1,2),(2,1)\}|}$

${\displaystyle F_{5}=5=|\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|}$

De esta manera, la relación de recurrencia puede entenderse dividiendo las secuencias en dos conjuntos no superpuestos donde todas las secuencias comienzan con 1 o 2: Excluyendo el primer elemento, los términos restantes en cada secuencia suman o y la cardinalidad de cada conjunto es o dando un total de secuencias, mostrando que esto es igual a .$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$${\displaystyle F_{n}}$$${\displaystyle F_{n}=|\{(1,...),(1,...),...\}|+|\{(2,...),(2,...),...\}|}$$${\displaystyle n-2}$${\displaystyle n-3}$${\displaystyle F_{n-1}}$${\displaystyle F_{n-2}}$${\displaystyle F_{n-1}+F_{n-2}}$${\displaystyle F_{n}}$

De manera similar se puede demostrar que la suma de los primeros números de Fibonacci hasta el n -ésimo es igual al ( n + 2) -ésimo número de Fibonacci menos 1. ^[35] En símbolos:$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$$

Esto se puede ver dividiendo todas las secuencias que suman en función de la ubicación de los primeros 2. Específicamente, cada conjunto consta de aquellas secuencias que comienzan hasta los dos últimos conjuntos, cada uno con cardinalidad 1.${\displaystyle n+1}$${\displaystyle (2,...),(1,2,...),...,}$${\displaystyle \{(1,1,...,1,2)\},\{(1,1,...,1)\}}$

Siguiendo la misma lógica que antes, sumando la cardinalidad de cada conjunto vemos que

${\displaystyle F_{n+2}=F_{n}+F_{n-1}+...+|\{(1,1,...,1,2)\}|+|\{(1,1,...,1)\}|}$

...donde los dos últimos términos tienen el valor . De esto se deduce que .${\displaystyle F_{1}=1}$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$

Un argumento similar, agrupando las sumas por la posición del primer 1 en lugar de los primeros 2, da dos identidades más: y En palabras, la suma de los primeros números de Fibonacci con índice impar hasta es el (2 n ) -ésimo número de Fibonacci, y la suma de los primeros números de Fibonacci con índice par hasta es el (2 n + 1) -ésimo número de Fibonacci menos 1. ^[36]$${\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}$$$${\displaystyle \sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}$$${\displaystyle F_{2n-1}}$${\displaystyle F_{2n}}$

Se puede utilizar un truco diferente para demostrar o, en palabras, que la suma de los cuadrados de los primeros números de Fibonacci hasta es el producto de los números de Fibonacci n -ésimo y ( n + 1) -ésimo. Para comprobarlo, se parte de un rectángulo de Fibonacci de tamaño y se descompone en cuadrados de tamaño ; de ahí se deduce la identidad comparando las áreas :$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$${\displaystyle F_{n}}$${\displaystyle F_{n}\times F_{n+1}}$${\displaystyle F_{n},F_{n-1},...,F_{1}}$

La secuencia también se considera utilizando el método simbólico . ^[37] Más precisamente, esta secuencia corresponde a una clase combinatoria especificable . La especificación de esta secuencia es . De hecho, como se indicó anteriormente, el -ésimo número de Fibonacci es igual al número de composiciones combinatorias ( particiones ordenadas ) de utilizando los términos 1 y 2.${\displaystyle (F_{n})_{n\in \mathbb {N} }}$${\displaystyle \operatorname {Seq} ({\mathcal {Z+Z^{2}}})}$${\displaystyle n}$${\displaystyle n-1}$

De ello se deduce que la función generadora ordinaria de la secuencia de Fibonacci, , es la función racional${\displaystyle \sum _{i=0}^{\infty }F_{i}z^{i}}$ ${\displaystyle {\frac {z}{1-z-z^{2}}}.}$

Las identidades de Fibonacci a menudo se pueden demostrar fácilmente mediante inducción matemática .

Por ejemplo, reconsidere Sumar a ambos lados da$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1.}$$${\displaystyle F_{n+1}}$

${\displaystyle \sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1}$

y entonces tenemos la fórmula para${\displaystyle n+1}$$${\displaystyle \sum _{i=1}^{n+1}F_{i}=F_{n+3}-1}$$

De manera similar, agregue a ambos lados de para obtener${\displaystyle {F_{n+1}}^{2}}$$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}+{F_{n+1}}^{2}=F_{n+1}\left(F_{n}+F_{n+1}\right)}$$$${\displaystyle \sum _{i=1}^{n+1}F_{i}^{2}=F_{n+1}F_{n+2}}$$

La fórmula de Binet es Esta se puede utilizar para demostrar identidades de Fibonacci.$${\displaystyle {\sqrt {5}}F_{n}=\varphi ^{n}-\psi ^{n}.}$$

Por ejemplo, para demostrar que la nota que el lado izquierdo se multiplica por se convierte en como se requiere, se utilizan los hechos y se simplifican las ecuaciones.${\textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$${\displaystyle {\sqrt {5}}}$$${\displaystyle {\begin{aligned}1+&\varphi +\varphi ^{2}+\dots +\varphi ^{n}-\left(1+\psi +\psi ^{2}+\dots +\psi ^{n}\right)\\&={\frac {\varphi ^{n+1}-1}{\varphi -1}}-{\frac {\psi ^{n+1}-1}{\psi -1}}\\&={\frac {\varphi ^{n+1}-1}{-\psi }}-{\frac {\psi ^{n+1}-1}{-\varphi }}\\&={\frac {-\varphi ^{n+2}+\varphi +\psi ^{n+2}-\psi }{\varphi \psi }}\\&=\varphi ^{n+2}-\psi ^{n+2}-(\varphi -\psi )\\&={\sqrt {5}}(F_{n+2}-1)\\\end{aligned}}}$$${\textstyle \varphi \psi =-1}$${\textstyle \varphi -\psi ={\sqrt {5}}}$

Se pueden derivar muchas otras identidades utilizando diversos métodos. A continuación se presentan algunas de ellas: ^[38]

La identidad de Cassini afirma que la identidad de Catalan es una generalización:$${\displaystyle {F_{n}}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}}$$$${\displaystyle {F_{n}}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}{F_{r}}^{2}}$$

$${\displaystyle F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}}$$$${\displaystyle F_{2n}={F_{n+1}}^{2}-{F_{n-1}}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}}$$donde L _n es el n - ésimo número de Lucas . El último es una identidad para duplicar n ; otras identidades de este tipo se obtienen mediante la identidad de Cassini.$${\displaystyle F_{3n}=2{F_{n}}^{3}+3F_{n}F_{n+1}F_{n-1}=5{F_{n}}^{3}+3(-1)^{n}F_{n}}$$

$${\displaystyle F_{3n+1}={F_{n+1}}^{3}+3F_{n+1}{F_{n}}^{2}-{F_{n}}^{3}}$$$${\displaystyle F_{3n+2}={F_{n+1}}^{3}+3{F_{n+1}}^{2}F_{n}+{F_{n}}^{3}}$$$${\displaystyle F_{4n}=4F_{n}F_{n+1}\left({F_{n+1}}^{2}+2{F_{n}}^{2}\right)-3{F_{n}}^{2}\left({F_{n}}^{2}+2{F_{n+1}}^{2}\right)}$$Estos se pueden encontrar experimentalmente usando reducción de red , y son útiles para configurar el tamiz de campo numérico especial para factorizar un número de Fibonacci.

De manera más general, ^[38]

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c-i}{F_{n}}^{i}{F_{n+1}}^{k-i}.}$$

o alternativamente

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c+i}{F_{n}}^{i}{F_{n-1}}^{k-i}.}$$

Poniendo k = 2 en esta fórmula, se obtienen nuevamente las fórmulas del final de la sección anterior Forma matricial.

La función generadora de la secuencia de Fibonacci es la serie de potencias

$${\displaystyle s(z)=\sum _{k=0}^{\infty }F_{k}z^{k}=0+z+z^{2}+2z^{3}+3z^{4}+5z^{5}+\dots .}$$

Esta serie es convergente para cualquier número complejo que satisfaga y su suma tenga una forma cerrada simple: ^[39]${\displaystyle z}$${\displaystyle |z|<1/\varphi ,}$

$${\displaystyle s(z)={\frac {z}{1-z-z^{2}}}.}$$

Esto se puede demostrar multiplicando por :${\textstyle (1-z-z^{2})}$$${\displaystyle {\begin{aligned}(1-z-z^{2})s(z)&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=0}^{\infty }F_{k}z^{k+1}-\sum _{k=0}^{\infty }F_{k}z^{k+2}\\&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=1}^{\infty }F_{k-1}z^{k}-\sum _{k=2}^{\infty }F_{k-2}z^{k}\\&=0z^{0}+1z^{1}-0z^{1}+\sum _{k=2}^{\infty }(F_{k}-F_{k-1}-F_{k-2})z^{k}\\&=z,\end{aligned}}}$$

donde todos los términos que involucran se cancelan debido a la relación de recurrencia de Fibonacci definitoria.${\displaystyle z^{k}}$${\displaystyle k\geq 2}$

La descomposición en fracciones parciales está dada por donde es la proporción áurea y es su conjugado .$${\displaystyle s(z)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi z}}-{\frac {1}{1-\psi z}}\right)}$$${\textstyle \varphi ={\tfrac {1}{2}}\left(1+{\sqrt {5}}\right)}$${\displaystyle \psi ={\tfrac {1}{2}}\left(1-{\sqrt {5}}\right)}$

La función relacionada es la función generadora de los números de negafibonacci y satisface la ecuación funcional${\textstyle z\mapsto -s\left(-1/z\right)}$${\displaystyle s(z)}$

$${\displaystyle s(z)=s\!\left(-{\frac {1}{z}}\right).}$$

Si se utiliza el valor igual a 0,01, 0,001, 0,0001, etc., se muestran los primeros números de Fibonacci en la expansión decimal de . Por ejemplo,${\displaystyle z}$${\displaystyle s(z)}$${\displaystyle s(0.001)={\frac {0.001}{0.998999}}={\frac {1000}{998999}}=0.001001002003005008013021\ldots .}$

Las sumas infinitas sobre números de Fibonacci recíprocos a veces se pueden evaluar en términos de funciones theta . Por ejemplo, la suma de cada número de Fibonacci recíproco de índice impar se puede escribir como$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}={\frac {\sqrt {5}}{4}}\;\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{2},}$$

y la suma de los números recíprocos de Fibonacci al cuadrado como$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{{F_{k}}^{2}}}={\frac {5}{24}}\!\left(\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}-\vartheta _{4}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}+1\right).}$$

Si sumamos 1 a cada número de Fibonacci en la primera suma, también existe la forma cerrada$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{1+F_{2k-1}}}={\frac {\sqrt {5}}{2}},}$$

y hay una suma anidada de números de Fibonacci al cuadrado que da el recíproco de la proporción áurea ,$${\displaystyle \sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{\sum _{j=1}^{k}{F_{j}}^{2}}}={\frac {{\sqrt {5}}-1}{2}}.}$$

La suma de todos los números de Fibonacci recíprocos de índice par es ^[40] con la serie de Lambert ya que$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}={\sqrt {5}}\left(L(\psi ^{2})-L(\psi ^{4})\right)}$$ ${\displaystyle \textstyle L(q):=\sum _{k=1}^{\infty }{\frac {q^{k}}{1-q^{k}}},}$${\displaystyle \textstyle {\frac {1}{F_{2k}}}={\sqrt {5}}\left({\frac {\psi ^{2k}}{1-\psi ^{2k}}}-{\frac {\psi ^{4k}}{1-\psi ^{4k}}}\right)\!.}$

Por lo tanto, la constante recíproca de Fibonacci es ^[41]$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{k}}}=\sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}+\sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}=3.359885666243\dots }$$

Además, Richard André-Jeannin ha demostrado que este número es irracional . ^[42]

La serie de Millin da la identidad ^[43] que se sigue de la forma cerrada para sus sumas parciales cuando N tiende a infinito:$${\displaystyle \sum _{k=0}^{\infty }{\frac {1}{F_{2^{k}}}}={\frac {7-{\sqrt {5}}}{2}},}$$$${\displaystyle \sum _{k=0}^{N}{\frac {1}{F_{2^{k}}}}=3-{\frac {F_{2^{N}-1}}{F_{2^{N}}}}.}$$

Cada tercer número de la secuencia es par (un múltiplo de ) y, de manera más general, cada k -ésimo número de la secuencia es un múltiplo de F _k . Por lo tanto, la secuencia de Fibonacci es un ejemplo de una secuencia de divisibilidad . De hecho, la secuencia de Fibonacci satisface la propiedad de divisibilidad más fuerte ^{[44] [45]} donde mcd es la función máximo común divisor .${\displaystyle F_{3}=2}$$${\displaystyle \gcd(F_{a},F_{b},F_{c},\ldots )=F_{\gcd(a,b,c,\ldots )}\,}$$

En particular, tres números de Fibonacci consecutivos son coprimos entre sí porque tanto y . Es decir,${\displaystyle F_{1}=1}$${\displaystyle F_{2}=1}$

${\displaystyle \gcd(F_{n},F_{n+1})=\gcd(F_{n},F_{n+2})=\gcd(F_{n+1},F_{n+2})=1}$

para cada n .

Todo número primo p divide a un número de Fibonacci que puede determinarse por el valor de p módulo  5. Si p es congruente con 1 o 4 módulo 5, entonces p divide a F _{p −1} , y si p es congruente con 2 o 3 módulo 5, entonces p divide a F _{p +1} . El caso restante es que p = 5 , y en este caso p divide a F _p .

$${\displaystyle {\begin{cases}p=5&\Rightarrow p\mid F_{p},\\p\equiv \pm 1{\pmod {5}}&\Rightarrow p\mid F_{p-1},\\p\equiv \pm 2{\pmod {5}}&\Rightarrow p\mid F_{p+1}.\end{cases}}}$$

Estos casos se pueden combinar en una única fórmula no por partes , utilizando el símbolo de Legendre : ^[46]$${\displaystyle p\mid F_{p\;-\,\left({\frac {5}{p}}\right)}.}$$

La fórmula anterior se puede utilizar como una prueba de primalidad en el sentido de que si el símbolo de Legendre ha sido reemplazado por el símbolo de Jacobi , entonces esto es evidencia de que n es un primo, y si no se cumple, entonces n definitivamente no es un primo. Si n es compuesto y satisface la fórmula, entonces n es un pseudoprimo de Fibonacci . Cuando m es grande –digamos un número de 500 bits– entonces podemos calcular F _m (mod n ) eficientemente usando la forma matricial. Por lo tanto$${\displaystyle n\mid F_{n\;-\,\left({\frac {5}{n}}\right)},}$$

$${\displaystyle {\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}}\equiv {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{m}{\pmod {n}}.}$$Aquí la potencia matricial A ^m se calcula utilizando exponenciación modular , que se puede adaptar a matrices . ^[47]

Un primo de Fibonacci es un número de Fibonacci que es primo . Los primeros son: ^[48]

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ...

Se han encontrado números primos de Fibonacci con miles de dígitos, pero no se sabe si hay infinitos. ^[49]

F _kn es divisible por F _n , por lo que, además de F ₄ = 3 , cualquier primo de Fibonacci debe tener un índice primo. Como hayseries arbitrariamente largas de números compuestos , también hay series arbitrariamente largas de números compuestos de Fibonacci.

Ningún número de Fibonacci mayor que F ₆ = 8 es uno mayor o uno menor que un número primo. ^[50]

El único número cuadrado de Fibonacci no trivial es 144. ^[51] Attila Pethő demostró en 2001 que solo existe un número finito de números de Fibonacci de potencias perfectas . ^[52] En 2006, Y. Bugeaud, M. Mignotte y S. Siksek demostraron que 8 y 144 son las únicas potencias perfectas no triviales. ^[53]

1, 3, 21 y 55 son los únicos números de Fibonacci triangulares , lo cual fue conjeturado por Vern Hoggatt y demostrado por Luo Ming. ^[54]

Ningún número de Fibonacci puede ser un número perfecto . ^[55] De manera más general, ningún número de Fibonacci distinto de 1 puede ser multiplicado por uno perfecto , ^[56] y ninguna relación de dos números de Fibonacci puede ser perfecta. ^[57]

Con las excepciones de 1, 8 y 144 ( F ₁ = F ₂ , F ₆ y F ₁₂ ) cada número de Fibonacci tiene un factor primo que no es factor de ningún número de Fibonacci más pequeño ( teorema de Carmichael ). ^[58] Como resultado, 8 y 144 ( F ₆ y F ₁₂ ) son los únicos números de Fibonacci que son el producto de otros números de Fibonacci. ^[59]

La divisibilidad de los números de Fibonacci por un primo p está relacionada con el símbolo de Legendre, que se evalúa de la siguiente manera:${\displaystyle {\bigl (}{\tfrac {p}{5}}{\bigr )}}$$${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}0&{\text{if }}p=5\\1&{\text{if }}p\equiv \pm 1{\pmod {5}}\\-1&{\text{if }}p\equiv \pm 2{\pmod {5}}.\end{cases}}}$$

Si p es un número primo entonces ^{[60] [61]}$${\displaystyle F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}\quad {\text{and}}\quad F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}}.}$$

Por ejemplo,$${\displaystyle {\begin{aligned}{\bigl (}{\tfrac {2}{5}}{\bigr )}&=-1,&F_{3}&=2,&F_{2}&=1,\\{\bigl (}{\tfrac {3}{5}}{\bigr )}&=-1,&F_{4}&=3,&F_{3}&=2,\\{\bigl (}{\tfrac {5}{5}}{\bigr )}&=0,&F_{5}&=5,\\{\bigl (}{\tfrac {7}{5}}{\bigr )}&=-1,&F_{8}&=21,&F_{7}&=13,\\{\bigl (}{\tfrac {11}{5}}{\bigr )}&=+1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}$$

No se sabe si existe un primo p tal que

$${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p^{2}}}.}$$

Estos números primos (si los hay) se llamarían números primos Wall–Sol–Sol .

Además, si p ≠ 5 es un número primo impar entonces: ^[62]$${\displaystyle 5{F_{\frac {p\pm 1}{2}}}^{2}\equiv {\begin{cases}{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\pm 5\right){\pmod {p}}&{\text{if }}p\equiv 1{\pmod {4}}\\{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\mp 3\right){\pmod {p}}&{\text{if }}p\equiv 3{\pmod {4}}.\end{cases}}}$$

Ejemplo 1. p = 7 , en este caso p ≡ 3 (mod 4) y tenemos:$${\displaystyle {\bigl (}{\tfrac {7}{5}}{\bigr )}=-1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}+3\right)=-1,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}-3\right)=-4.}$$$${\displaystyle F_{3}=2{\text{ and }}F_{4}=3.}$$$${\displaystyle 5{F_{3}}^{2}=20\equiv -1{\pmod {7}}\;\;{\text{ and }}\;\;5{F_{4}}^{2}=45\equiv -4{\pmod {7}}}$$

Ejemplo 2. p = 11 , en este caso p ≡ 3 (mod 4) y tenemos:$${\displaystyle {\bigl (}{\tfrac {11}{5}}{\bigr )}=+1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}+3\right)=4,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}-3\right)=1.}$$$${\displaystyle F_{5}=5{\text{ and }}F_{6}=8.}$$$${\displaystyle 5{F_{5}}^{2}=125\equiv 4{\pmod {11}}\;\;{\text{ and }}\;\;5{F_{6}}^{2}=320\equiv 1{\pmod {11}}}$$