Sucesión de Fibonacci

En matemáticas, la sucesión o serie de Fibonacci es la siguiente sucesión infinita de números naturales:

La sucesión comienza con los números 0 y 1;^[2]​ a partir de estos, «cada término es la suma de los dos anteriores», es la relación de recurrencia que la define.

A los elementos de esta sucesión se les llama hijos de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemática y teoría de juegos. También aparece en configuraciones biológicas, como por ejemplo en las ramas de los árboles, en la disposición de las hojas en el tallo, en las flores de alcachofas y girasoles, en las inflorescencias del brécol romanesco, en la configuración de las piñas de las coníferas, en la reproducción de los conejos y en cómo el ADN codifica el crecimiento de formas orgánicas complejas. De igual manera, se encuentra en la estructura espiral del caparazón de algunos moluscos, como el nautilus.

Leonardo Pisano, Leonardo de Pisa, o Leonardo Bigollo, también conocido como Fibonacci, nació en 1170 y murió en 1240. Mucho antes de ser conocida en occidente, la sucesión de Fibonacci ya estaba descrita en la matemática en la India, en conexión con la prosodia sánscrita.^[3]​^[4]​

Susantha Goonatilake hace notar que el desarrollo de la secuencia de Fibonacci «es atribuido en parte a Pingala (año 200), posteriormente asociado con Virahanka (hacia el año 700), Gopāla (hacia 1135) y Hemachandra (hacia 1150)».^[5]​ Parmanand Singh cita a Pingala (hacia 450) como precursor en el descubrimiento de la secuencia.^[6]​

La sucesión fue descrita y dada a conocer en occidente por Fibonacci como la solución a un problema de la cría de conejos:

Nota: al contar la cantidad de letras distintas en cada mes, se puede saber la cantidad de parejas totales que hay hasta ese mes.

De esta manera Fibonacci presentó la sucesión en su libro Liber Abaci, publicado en 1202. Muchas propiedades de la sucesión de Fibonacci fueron descubiertas por Édouard Lucas, responsable de haberla denominado como se la conoce en la actualidad.^[7]​

También Kepler describió los números de Fibonacci, y el matemático escocés Robert Simson descubrió en 1753 que la relación entre dos números de Fibonacci sucesivos ${displaystyle f_{n+1}/f_{n}}$ se acerca a la relación áurea fi (${displaystyle phi }$) cuando ${displaystyle n}$ tiende a infinito; es más: el cociente de dos términos sucesivos de toda sucesión recurrente de orden dos tiende al mismo límite. Esta sucesión tuvo popularidad en el siglo XX especialmente en el ámbito musical, en el que compositores con tanto renombre como Béla Bartók, Olivier Messiaen, la banda Tool y Delia Derbyshire la utilizaron para la creación de acordes y de nuevas estructuras de frases musicales.

Los números de Fibonacci quedan definidos por las ecuaciones

(1)${displaystyle f_{0}=0,}$

(2)${displaystyle f_{1}=1,}$

(3)${displaystyle f_{n}=f_{n-1}+f_{n-2},}$

Esto produce los siguientes números:

y así sucesivamente.

Esta manera de definir, de hecho considerada algorítmica, es usual en Matemática discreta.

Es importante definir ${displaystyle f_{0}=0,}$ para que se pueda cumplir la importante propiedad de que:

${displaystyle f_{n}}$ divide a ${displaystyle f_{m*n}}$, para cualquier ${displaystyle m,n>=1}$.

Para analizar la sucesión de Fibonacci (y, en general, cualquier sucesión) es conveniente obtener otras maneras de representarla matemáticamente.

${displaystyle {frac {1pm {sqrt {5}}}{2}}={frac {b}{a}}={frac {c}{b}}}$, donde c=a+b; a≠0; b≠0; b>a

${displaystyle bb=ac}$

${displaystyle b^{2}=ac}$

${displaystyle b^{2}=a*(a+b)}$

${displaystyle b^{2}=a^{2}+ab}$

${displaystyle a^{2}-b^{2}+ab=0}$

Reemplazando las variables por pares de valores consecutivos de la sucesión de Fibonacci (a=1;b=2 o a=3;b=5) se ve que:

${displaystyle (1)^{2}-(2)^{2}+(1)*(2)=1}$

${displaystyle (3)^{2}-(5)^{2}+(3)*(5)=-1}$

Con la fórmula siguiente se puede establecer cuán fuerte es la relación áurea entre dos números: 0 Es una relación áurea perfecta y en los extremos 1 y - 1 son números pertenecientes a la sucesión Fibonacci ${displaystyle -1<=a^{2}-b^{2}+ab<=1}$

Una función generadora para una sucesión cualquiera ${displaystyle a_{0},a_{1},a_{2},dots }$ es la función ${displaystyle f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}+cdots }$, es decir, una serie formal de potencias donde cada coeficiente es un elemento de la sucesión. Los números de Fibonacci tienen la función generadora

(4)${displaystyle fleft(x ight)={frac {x}{1-x-x^{2}}}}$

Cuando esta función se expande en potencias de ${displaystyle x,}$, los coeficientes resultan ser la sucesión de Fibonacci:

La definición de la sucesión de Fibonacci es recurrente; es decir que se necesitan calcular todos los términos anteriores para poder calcular un término específico. Se puede obtener una fórmula explícita de la sucesión de Fibonacci (que no requiere calcular términos anteriores) notando que las ecuaciones (1), (2) y (3) definen la relación de recurrencia

con las condiciones iniciales

El polinomio característico de esta relación de recurrencia es ${displaystyle t^{2}-t-1=0}$, y sus raíces son

De esta manera, la fórmula explícita de la sucesión de Fibonacci tendrá la forma

Si se toman en cuenta las condiciones iniciales, entonces las constantes ${displaystyle b}$ y ${displaystyle d}$ satisfacen la ecuación anterior cuando ${displaystyle n=0}$ y ${displaystyle n=1}$, es decir que satisfacen el sistema de ecuaciones

Al resolver este sistema de ecuaciones se obtiene

Por lo tanto, cada número de la sucesión de Fibonacci puede ser expresado como

(5)${displaystyle f_{n}={frac {1}{sqrt {5}}}left({frac {1+{sqrt {5}}}{2}} ight)^{n}-{frac {1}{sqrt {5}}}left({frac {1-{sqrt {5}}}{2}} ight)^{n}}$

Para simplificar aún más es necesario considerar el número áureo

de manera que la ecuación (5) se reduce a

(6)${displaystyle f_{n}={frac {varphi ^{n}-left(1-varphi ight)^{n}}{sqrt {5}}}}$

Esta fórmula se le atribuye al matemático francés Édouard Lucas, y es fácilmente demostrable por inducción matemática. A pesar de que la sucesión de Fibonacci consta únicamente de números naturales, su fórmula explícita incluye al número irracional ${displaystyle varphi ,}$. De hecho, la relación con este número es estrecha.

Observando los valores que adoptan los dos sumandos de la fórmula (5), se comprueba que el segundo sumando siempre tiene un valor absoluto menor que ${displaystyle 1}$, y va cambiando de signo sucesivamente, compensando la parte no entera, irracional, que tiene el primer sumando, para que la suma de dos números irracionales dé un número natural.

Teniendo en cuenta entonces que ese segundo sumando de la fórmula (5) es siempre un número de valor absoluto menor que ${displaystyle 0.5}$, (el máximo valor absoluto es para ${displaystyle n=0}$, aproximadamente ${displaystyle 0.4472}$), la fórmula puede escribirse, eliminando este segundo sumando, así:

(7)${displaystyle f_{n}=operatorname {int} left({frac {1}{sqrt {5}}}left({frac {1+{sqrt {5}}}{2}} ight)^{n}+{frac {1}{2}} ight)}$

o lo que es lo mismo, empleando el número áureo ${displaystyle varphi }$ :

(8)${displaystyle f_{n}=operatorname {int} left({frac {varphi ^{n}}{sqrt {5}}}+{frac {1}{2}} ight)}$

Otra manera de obtener la sucesión de Fibonacci es considerando el sistema lineal de ecuaciones

Este sistema se puede representar mediante su notación matricial como

Conociendo a ${displaystyle f_{0}=0}$ y ${displaystyle f_{1}=1}$, al aplicar la fórmula anterior ${displaystyle n}$ veces se obtiene

(9)${displaystyle {egin{bmatrix}0&1\1&1end{bmatrix}}^{n}{egin{bmatrix}0\1end{bmatrix}}={egin{bmatrix}f_{n}\f_{n+1}end{bmatrix}}}$

Los autovalores de la matriz ${displaystyle {egin{bmatrix}0&1\1&1end{bmatrix}}}$, son precisamente ${displaystyle varphi ={frac {1+{sqrt {5}}}{2}}}$ y ${displaystyle psi ={frac {1-{sqrt {5}}}{2}}}$, (el número áureo ${displaystyle varphi }$; y el negativo de su inverso o conjugado ${displaystyle psi ={frac {-1}{varphi }}=1-varphi }$); y sus autovectores ${displaystyle (psi ,-1)}$ y ${displaystyle (varphi ,-1)}$.

Aplicando técnicas de descomposición espectral de la matriz, utilizando sus autovalores, y la base de sus autovectores, o diagonalizando la matriz, se puede substituir o simplificar la operación de potenciación de la matriz, y obtener, por otros dos métodos, la fórmula explícita (5) que proporciona el término general de la sucesión.

También se verifica

(10)${displaystyle {egin{bmatrix}0&1\1&1end{bmatrix}}^{n}={egin{bmatrix}f_{n-1}&f_{n}\f_{n}&f_{n+1}end{bmatrix}}}$

Esta igualdad puede probarse mediante inducción matemática.

Los números de Fibonacci aparecen en numerosas aplicaciones de diferentes áreas. Por ejemplo, en modelos de la crianza de conejos o de plantas, al contar el número de cadenas de bits de longitud ${displaystyle n}$ que no tienen ceros consecutivos y en una vasta cantidad de contextos diferentes. De hecho, existe una publicación especializada llamada Fibonacci Quarterly^[9]​ dedicada al estudio de la sucesión de Fibonacci y temas afines. Se trata de un tributo a la amplitud con la que los números de Fibonacci aparecen en matemática y sus aplicaciones en otras áreas. Algunas de las propiedades de esta sucesión son las siguientes:

${displaystyle lim _{n o infty }{frac {f_{n+1}}{f_{n}}}=varphi }$

El concepto fundamental de la sucesión de Fibonacci es que cada elemento es la suma de los dos anteriores. En este sentido la sucesión puede expandirse al conjunto de los números enteros como ${displaystyle ldots ,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,ldots }$ de manera que la suma de cualesquiera dos números consecutivos es el inmediato siguiente. Para poder definir los índices negativos de la sucesión, se despeja ${displaystyle f_{n-2},}$ de la ecuación (3) de donde se obtiene

De esta manera, ${displaystyle f_{-n}=f_{n},}$ si ${displaystyle n}$ es impar y ${displaystyle f_{-n}=-f_{n},}$ si ${displaystyle n}$ es par.^[11]​

La sucesión se puede expandir al campo de los números reales tomando la parte real de la fórmula explícita (ecuación (6)) cuando ${displaystyle n}$ es cualquier número real. La función resultante

tiene las mismas características que la sucesión de Fibonacci:

Una sucesión de Fibonacci generalizada es una sucesión ${displaystyle g_{0},g_{1},g_{2},ldots }$ donde

(11)${displaystyle g_{n}=g_{n-1}+g_{n-2},}$ para ${displaystyle n=2,3,4,5,ldots }$

Es decir, cada elemento de una sucesión de Fibonacci generalizada es la suma de los dos anteriores, pero no necesariamente comienza en 0 y 1.

Una sucesión de fibonacci generalizada muy importante, es la formada por las potencias del número áureo.

La importancia de esta sucesión reside en el hecho de que se puede expandir directamente al conjunto de los números reales.

...y al de los complejos.

Una característica notable es que, si ${displaystyle g_{0},g_{1},g_{2},ldots }$ es una sucesión de Fibonacci generalizada, entonces

Por ejemplo, la ecuación (11) puede generalizarse a

Esto significa que cualquier cálculo sobre una sucesión de Fibonacci generalizada se puede efectuar usando números de Fibonacci.

Un ejemplo de sucesión de Fibonacci generalizada es la sucesión de Lucas, descrita por las ecuaciones

La sucesión de Lucas tiene una gran similitud con la sucesión de Fibonacci y comparte muchas de sus características. Algunas propiedades interesantes incluyen:

Para calcular el ${displaystyle n}$-ésimo elemento de la sucesión de Fibonacci existen varios algoritmos (métodos). Su definición misma puede emplearse como uno de estos algoritmos, aquí expresado en pseudocódigo:

función ${displaystyle { m {fib}}(n),}$

Usando técnicas de análisis de algoritmos es posible demostrar que, a pesar de su simplicidad, el algoritmo 1 requiere efectuar ${displaystyle f_{n+1}-1}$ sumas para poder encontrar el resultado. Dado que la sucesión ${displaystyle f_{n}}$ crece tan rápido como ${displaystyle varphi ^{n}}$, entonces el algoritmo está en el orden de ${displaystyle varphi ^{n}}$. Es decir, que este algoritmo es muy lento. Por ejemplo, para calcular ${displaystyle f_{50}}$ este algoritmo requiere efectuar 20.365.011.073 sumas.

Para evitar hacer tantas operaciones, es común recurrir a una calculadora y utilizar la ecuación (6) del matemático Édouard Lucas. Sin embargo, dado que ${displaystyle varphi }$ es un número irracional, la única manera de utilizar esta fórmula es empleando una aproximación de ${displaystyle varphi }$, obteniendo en consecuencia un resultado aproximado pero no exacto. Por ejemplo, si se usa una calculadora de 10 dígitos, entonces la fórmula anterior arroja como resultado ${displaystyle f_{50}=1.258626903 imes 10^{10}}$ aun cuando el resultado correcto es ${displaystyle f_{50}=12586269025}$. Este error se hace cada vez más grande conforme crece ${displaystyle n}$. De igual forma se puede crear una función utilizando la fórmula, muy eficiente, ${displaystyle O(log _{2}(n))}$, aunque hay que tener en cuenta algunas consideraciones, cada lenguaje de programación tiene una forma específica de implementación de las funciones matemáticas, y es probable que se necesite redondear el número obtenido de la ecuación, y en ciertos casos, si el número es muy grande, puede ser impreciso.

función ${displaystyle { m {fib}}(n),}$

Otro método más práctico a la recursión, que evita calcular las mismas sumas más de una vez, es la iteración. Considerando un par ${displaystyle (a,b),}$ de números consecutivos de la sucesión de Fibonacci, el siguiente par de la sucesión es ${displaystyle (b,b+a),}$, de esta manera se divisa un algoritmo donde solo se requiere considerar dos números consecutivos de la sucesión de Fibonacci en cada paso. Este método es el que se usaría normalmente para hacer el cálculo con lápiz y papel. El algoritmo se expresa en pseudocódigo como:

función ${displaystyle { m {fib}}(n),}$

función ${displaystyle { m {fib}}(n),}$

función ${displaystyle { m {fib}}(n),}$

Estas versiones requieren efectuar solo ${displaystyle n}$ sumas para calcular ${displaystyle f_{n}}$, lo cual significa que los métodos iterativos son considerablemente más rápidos que el algoritmo 1. Por ejemplo, en el algoritmo 3 solo se requiere efectuar 50 sumas para calcular ${displaystyle f_{50}}$.

Un algoritmo todavía más rápido se deduce partiendo de la ecuación (10). Utilizando leyes de exponentes es posible calcular ${displaystyle x^{n}}$ como

De esta manera se divisa el algoritmo de tipo Divide y Vencerás donde solo se requeriría hacer, aproximadamente, ${displaystyle log _{2}(n)}$ multiplicaciones matriciales. Sin embargo, no es necesario almacenar los cuatro valores de cada matriz dado que cada una tiene la forma

De esta manera, cada matriz queda completamente representada por los valores ${displaystyle a}$ y ${displaystyle b}$, y su cuadrado se puede calcular como

Por lo tanto el algoritmo queda como sigue:

función ${displaystyle { m {fib}}(n),}$

A pesar de lo engorroso que parezca, este algoritmo permite reducir enormemente el número de operaciones que se necesitan para calcular números de Fibonacci muy grandes. Por ejemplo, para calcular ${displaystyle f_{100}}$, en vez de hacer las 573.147.844.013.817.084.100 sumas del algoritmo 1 o las 100 sumas con el algoritmo 3, el cálculo se reduce a tan solo 9 multiplicaciones matriciales.

La secuencia de Fibonacci se encuentra en múltiples configuraciones biológicas,^[12]​ donde aparecen números consecutivos de la sucesión, como en la distribución de las ramas de los árboles, la distribución de las hojas en un tallo, los frutos de la piña tropical,^[13]​ las flores de la alcachofa, en las piñas de las coníferas,^[14]​ o en el "árbol genealógico" de las abejas melíferas.^[15]​ Sin embargo, también se han hecho muchas invocaciones infundadas a la aparición de los números de Fibonacci aprovechando su relación con el número áureo en la literatura popular.^[16]​

Przemysław Prusinkiewicz avanzó la idea de considerar la sucesión de Fibonacci en la naturaleza como un grupo libre.^[17]​

Un modelo del patrón de distribución de las semillas del girasol fue propuesto por H. Vogel en 1979.^[18]​ Presenta la forma

donde n es el índice de la flor y c es un factor de escala; entonces las semillas se alinean según espirales de Fermat. El ángulo de divergencia, de aproximadamente 137.51°, está relacionado con el número áureo. Debido a que el coeficiente es un número irracional, ninguna semilla tiene ninguna vecina al mismo ángulo respecto al centro, por lo que se compactan eficientemente. Debido a que las aproximaciones racionales al número aúreo son de la forma F(j):F(j + 1), los vecinos más próximos al número de semillas n están todos en n ± F(j) para cada índice j, que depende de r, la distancia al centro. Suele afirmarse que los girasoles y flores similares tienen 55 espirales en una dirección y 89 en la otra (o alguna otra pareja de números adyacentes de la sucesión de Fibonacci), pero esto solo es cierto en ciertos rangos de radio, generalmente raros (y por ello más notables).^[19]​

Los machos de una colmena de abejas tienen un árbol genealógico que cumple con esta sucesión. El hecho es que un zángano (1), el macho de la abeja, no tiene padre, pero sí que tiene una madre (1, 1), dos abuelos, que son los padres de la reina (1, 1, 2), tres bisabuelos, ya que el padre de la reina no tiene padre (1, 1, 2, 3), cinco tatarabuelos (1, 1, 2, 3, 5), ocho trastatarabuelos (1, 1, 2, 3, 5, 8) y así sucesivamente, cumpliendo con la sucesión de Fibonacci.

Recientemente, un análisis histórico-matemático acerca del contexto de Leonardo de Pisa y la proximidad de la ciudad de Bejaia, una importante exportadora de cera en los tiempos de Leonardo (de la cual proviene el nombre en francés de esta ciudad, "Bougie", que significa "vela"), ha sugerido que fueron los criadores de abejas de Bejaia y el conocimiento de la ascendencia de las abejas lo que inspiró los números de Fibonacci más que el modelo de reproducción de conejos.^[20]​

Una de las curiosidades de dicha serie son los dígitos de sus elementos:

---