Sucesión de Fibonacci

En matemáticas, a sucesión de Fibonacci é a sucesión de números naturais:

${\textstyle 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597\ldots \,}$ (secuencia A000045 na OEIS)

A espiral de Fibonacci: unha aproximación da espiral áurea xerada debuxando arcos circulares conectando as esquinas opostas dos cadrados axustados aos valores da sucesión;^[1] acaroando sucesivamente cadrados de lado 0, 1, 1, 2, 3, 5, 8, 13, 21 e 34.

Gráfica da sucesión de Fibonacci ata ${\displaystyle f_{7}}$

A sucesión comeza cos números 0 e 1,^[2] e a partir destes a relación de recorrencia que a define é que «cada termo é a suma dos dous anteriores».

Aos elementos desta sucesión chámaselles números de Fibonacci. Esta sucesión foi descrita en Europa por Leonardo de Pisa, matemático italiano do século XIII tamén coñecido como Fibonacci. Ten numerosas aplicacións en ciencias da computación, matemáticas e teoría de xogos. Tamén aparece en configuracións biolóxicas, como por exemplo nas ramas das árbores, na disposición das follas no tallo, nas flores das alcachofas e xirasois, nas inflorescencias do brócoli romanesco e na configuración das piñas das coníferas.

Historia

Moito antes de ser coñecida en occidente, a sucesión de Fibonacci xa estaba descrita nas matemáticas da India, en conexión coa prosodia sánscrita.^[3][4]

Susantha Goonatilake fai notar que o desnvolvemento da secuencia de Fibonacci "atribúese en parte a Pingala (ano 200), posteriormente asociado con Virahanka (cara ao ano 700), Gopāla (cara a 1135), e Hemachandra (cara a 1150)".^[5] Parmanand Singh cita a Pingala (cara a 450) como precursor no descubrimento da secuencia.^[6]

A sucesión foi descrita e dada a coñecer en occidente por Fibonacci como a solución a un problema da cría de coellos: «Certo home tiña unha parella de coellos nun lugar pechado e desexaba saber cantos se poderían reproducir nun ano a partir da parella inicial, tendo en conta que de forma natural teñen unha parella nun mes, e que a partir do segundo comezan a reproducirse».^[7]

Número de Mes	Explicación da xenealoxía	Parellas de coellos
Comezo do mes 1	Nace unha parella de coellos (parella A).	1 parella en total.
Fin do mes 1	A parella A ten un mes de idade. Crúzase a parella A.	1+0=1 parella en total.
Fin do mes 2	A parella A dá a luz á parella B. Vólvese cruzar a parella A.	1+1=2 parellas en total.
Fin do mes 3	A parella A dá a luz á parella C. A parella B cumpre 1 mes. Crúzanse as parellas A e B.	2+1=3 parellas en total.
Fin do mes 4	As parellas A e B dan a luz a D e E. A parella C cumpre 1 mes. Crúzanse as parellas A, B e C.	3+2=5 parellas en total.
Fin do mes 5	A, B e C dan a luz a F, G e H. D e E cumpren un mes. Crúzanse A, B, C, D e E.	5+3=8 parellas en total.
Fin do mes 6	A, B, C, D e E dan a luz a I, J, K, L e M. F, G e H cumpren un mes. Crúzanse A, B, C, D, E, F, G e H.	8+5=13 parellas en total.
...	...	...
	...	...

Nota: ao contar a cantidade de letras distintas en cada mes, pódese saber a cantidade de parellas totais que hai ata ese mes.

Páxina do Liber Abaci de Fibonacci da Biblioteca Nacional Central de Florencia que mostra nun cadro á dereita a sucesión de Fibonacci coas posicións da secuencia etiquetadas en números romanos e en latín; e o valor dos números en cifras arábigas.

Desta maneira Fibonacci presentou a sucesión no seu libro Liber Abaci, publicado en 1202. Moitas propiedades da sucesión de Fibonacci foron descubertas por Édouard Lucas, responsable de nomeala como se coñece na actualidade.^[8]

Tamén Kepler describiu os números de Fibonacci, e o matemático escocés Robert Simson descubriu en 1753 que a relación entre dous números de Fibonacci sucesivos ${\displaystyle f_{n+1}/f_{n}}$ se achega á relación áurea fi (${\displaystyle \phi }$) cando n tende a infinito; é máis, o cociente de dous termos sucesivos de toda sucesión recorrente de orde dous tende ao mesmo límite. Esta sucesión tivo popularidade no século XX especialmente no ámbito musical, no que compositores con tanta sona como Béla Bartók, Olivier Messiaen, a banda Tool e Delia Derbyshire a utilizaron para a creación de acordes e de novas estruturas de frases musicais.

Definición recursiva

Os números de Fibonacci quedan definidos pola ecuación:

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

partindo de dous primeiros valores predeterminados:

${\displaystyle f_{0}=0\,}$

${\displaystyle f_{1}=1\,}$

obtéñense os seguintes números:

• ${\displaystyle f_{2}=1\,}$
• ${\displaystyle f_{3}=2\,}$
• ${\displaystyle f_{4}=3\,}$
• ${\displaystyle f_{5}=5\,}$
• ${\displaystyle f_{6}=8\,}$
• ${\displaystyle f_{7}=13\,}$
• ${\displaystyle f_{8}=21\,}$

para ${\displaystyle n=2,3,4,5,\ldots }$

Esta maneira de definir, de feito considerada algorítmica, é usual en Matemática discreta.

É importante definir ${\displaystyle f_{0}=0\,}$ para que se poida cumprir a importante propiedade de que:

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

Representacións alternativas

Para analizar a sucesión de Fibonacci (e, en xeral, calquera sucesión) é conveniente obter outras maneiras de representala matematicamente.

Función xeradora

Unha función xeradora para unha sucesión calquera ${\displaystyle a_{0},a_{1},a_{2},\dots }$ é a función ${\displaystyle f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}+\cdots }$, é dicir, unha serie formal de potencias onde cada coeficiente é un elemento da sucesión. Os números de Fibonacci teñen a función xeradora

(4) ${\displaystyle f\left(x\right)={\frac {x}{1-x-x^{2}}}}$

Cando esta función se expande en potencias de ${\displaystyle x\,}$, os coeficientes resultan ser a sucesión de Fibonacci:

${\displaystyle {\frac {x}{1-x-x^{2}}}=0x^{0}+1x^{1}+1x^{2}+2x^{3}+3x^{4}+5x^{5}+8x^{6}+13x^{7}+\cdots }$

Fórmula explícita

A definición da sucesión de Fibonacci é recorrente; é dicir que se necesitan calcular varios termos anteriores para poder calcular un termo específico. Pódese obter unha fórmula explícita da sucesión de Fibonacci (que non require calcular termos anteriores) notando que as ecuacións (1), (2) e (3) definen a relación de recorrencia

${\displaystyle f_{n+2}-f_{n+1}-f_{n}=0\,}$

coas condicións iniciais

${\displaystyle f_{0}=0\,}$ e ${\displaystyle f_{1}=1\,}$

O polinomio característico desta relación de recorrencia é ${\displaystyle t^{2}-t-1=0}$, e as súas raíces son

${\displaystyle t={\frac {1\pm {\sqrt {5}}}{2}}}$

Desta maneira, a fórmula explícita da sucesión de Fibonacci terá a forma

${\displaystyle f_{n}=b\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+d\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}$.

Se se teñen en conta as condicións iniciais, entón as constantes ${\displaystyle b}$ e ${\displaystyle d}$ satisfán a ecuación anterior cando ${\displaystyle n=0}$ e ${\displaystyle n=1}$, é dicir que satisfán o sistema de ecuacións

${\displaystyle \left.{\begin{array}{rcl}b+d&=&0\\b\left({\frac {1+{\sqrt {5}}}{2}}\right)+d\left({\frac {1-{\sqrt {5}}}{2}}\right)&=&1\end{array}}\right\}}$

Ao resolver este sistema de ecuacións obtense

${\displaystyle b={\frac {1}{\sqrt {5}}},d=-{\frac {1}{\sqrt {5}}}}$

Polo tanto, cada número da sucesión de Fibonacci pode ser expresado como

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

Para simplificar aínda máis é necesario considerar o número áureo

${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$

de maneira que a ecuación (5) se reduce a

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

Esta fórmula atribúese ao matemático francés Édouard Lucas, e é facilmente demostrable por indución matemática. A pesar de que a sucesión de Fibonacci consta unicamente de números naturais, a súa fórmula explícita inclúe o número irracional ${\displaystyle \varphi \,}$ (fi). De feito, a relación con este número é estreita. Este tipo de fórmulas pechadas para obter o elemento n das recurrencias son coñecidas como fórmulas de Binet, aínda que non foi o seu descubridor.

Forma matricial

Outra maneira de obter a sucesión de Fibonacci é considerando o sistema de ecuacións lineares

${\displaystyle \left.{\begin{array}{rcl}f_{n}&=&f_{n}\\f_{n-1}+f_{n}&=&f_{n+1}\end{array}}\right\}}$

Este sistema pode representarse mediante a súa notación matricial como

${\displaystyle {\begin{bmatrix}0&1\\1&1\end{bmatrix}}{\begin{bmatrix}f_{n-1}\\f_{n}\end{bmatrix}}={\begin{bmatrix}f_{n}\\f_{n+1}\end{bmatrix}}}$

Coñecendo a ${\displaystyle f_{0}=0}$ e ${\displaystyle f_{1}=1}$, ao aplicar a fórmula anterior ${\displaystyle n}$ veces obtense

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

unha vez aquí, simplemente hai que diagonalizar a matriz, facilitando así a operación de potenciación, e obtendo polo tanto a fórmula explícita para a sucesión que está especificada arriba.

Máis aínda

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

Estas igualdades poden probarse mediante indución matemática.

Propiedades da sucesión

Ao construír bloques cunha lonxitude dos lados que sexan números de Fibonacci obtense un debuxo semellante ao rectángulo áureo.

Os números de Fibonacci aparecen en numerosas aplicacións de diferentes áreas. Por exemplo, en modelos da crianza de coellos o de plantas, ao contar o número de cadeas de bits de lonxitude ${\displaystyle n}$ que non teñen ceros consecutivos e nunha vasta cantidade de contextos diferentes. De feito, existe unha publicación especializada chamada Fibonacci Quartely^[9] dedicada ao estudo da sucesión de Fibonacci e temas afíns. Trátase dun tributo ao amplamente que aparecen os números de Fibonacci nas matemáticas e nas súas aplicacións noutras áreas. Algunhas das propiedades desta sucesión son as seguintes:

• A razón entre un termo e o inmediatamente anterior varía continuamente, pero estabilízase no número áureo. É dicir:

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

Este límite non é privativo da sucesión de Fibonacci. Calquera sucesión recorrente de orde 2, como a sucesión 3, 4, 7, 11, 18..., tende ao mesmo límite. Isto foi demostrado por Barr e Schooling nunha carta publicada na revista londiniense "The Field" do 14 de decembro de 1912. Os cocientes son oscilantes; é dicir, que un cociente é menor ao límite e o seguinte é maior. Os cocientes poden ordenarse en dúas sucesións que se aproximan asintoticamente por exceso e por defecto ao valor límite.

• Calquera número natural pode escribirse mediante a suma dun número limitado de termos da sucesión de Fibonacci, cada un deles distinto aos demais. Por exemplo, ${\displaystyle 17=13+3+1}$, ${\displaystyle 65=55+8+2}$.
• Tan só un termo de cada tres é par, un de cada catro é múltiplo de 3, un de cada cinco é múltiplo de 5 etc. Isto pode xeneralizarse, de forma que a sucesión de Fibonacci é periódica nas congruencias módulo ${\displaystyle m}$, para calquera ${\displaystyle m}$.
• A sucesión pode expresarse mediante outra fórmula explícita chamada forma de Binet (de Jacques Binet). Se ${\displaystyle \textstyle \alpha ={\frac {1+{\sqrt {5}}}{2}}}$ e ${\displaystyle \textstyle \beta ={\frac {1-{\sqrt {5}}}{2}}}$, entón

${\displaystyle f_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}}$ e ${\displaystyle f_{n}\approx {\frac {\alpha ^{n}}{\sqrt {5}}}\,}$

• Cada número de Fibonacci é a media do termo que se atopa dúas posicións antes e o termo que se atopa unha posición despois. É dicir

${\displaystyle f_{n}={\frac {f_{n-2}+f_{n+1}}{2}}}$

• O anterior tamén pode expresarse así: calcular o seguinte número a un dado é 2 veces este número menos o número dúas posicións máis atrás.

${\displaystyle f_{n+1}=f_{n}*2-f_{n-2}}$

• A suma dos ${\displaystyle n}$ primeiros números é igual ao número que ocupa a posición ${\displaystyle n+2}$ menos un. É dicir

${\displaystyle f_{0}+f_{1}+f_{2}+\cdots +f_{n}=f_{n+2}-1}$

• Outras identidades interesantes inclúen as seguintes:

${\displaystyle f_{0}-f_{1}+f_{2}-\cdots +(-1)^{n}f_{n}=(-1)^{n}f_{n-1}-1}$

${\displaystyle f_{1}+f_{3}+f_{5}+\cdots +f_{2n-1}=f_{2n}}$

${\displaystyle f_{0}+f_{2}+f_{4}+\cdots +f_{2n}=f_{2n+1}-1}$

${\displaystyle f_{0}^{2}+f_{1}^{2}+f_{2}^{2}+\cdots +f_{n}^{2}=f_{n}f_{n+1}}$

${\displaystyle f_{1}f_{2}+f_{2}f_{3}+f_{3}f_{4}+\cdots +f_{2n-1}f_{2n}=f_{2n}^{2}}$

${\displaystyle f_{1}f_{2}+f_{2}f_{3}+f_{3}f_{4}+\cdots +f_{2n}f_{2n+1}=f_{2n+1}^{2}-1}$

Se ${\displaystyle k\geq 1}$, entón ${\displaystyle f_{n+k}=f_{k}f_{n+1}+f_{k-1}f_{n}\,}$ para calquera ${\displaystyle n\geq 0}$

${\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}}$ (Identidade de Cassini)

${\displaystyle f_{n+1}^{2}+f_{n}^{2}=f_{2n+1}}$

${\displaystyle f_{n+2}^{2}-f_{n+1}^{2}=f_{n}f_{n+3}}$

Phi forma parte dunha expresión da sucesión de Fibonacci.

${\displaystyle f_{n+2}^{2}-f_{n}^{2}=f_{2n+2}}$

${\displaystyle f_{n+2}^{3}+f_{n+1}^{3}-f_{n}^{3}=f_{3n+3}}$

${\displaystyle f_{n}=\varphi ^{n+1}-(f_{n+1})\varphi }$ (con φ = número áureo) ou despexando f(n+1) e aplicando 1/φ = φ-1:

${\displaystyle f_{n+1}=\varphi ^{n}+(1-\varphi )f_{n}}$

• O máximo común divisor de dous números de Fibonacci é outro número de Fibonacci. Máis especificamente

${\displaystyle \mathrm {mcd} \left(f_{n},f_{m}\right)=f_{\mathrm {mcd} \left(n,m\right)}}$

Isto significa que ${\displaystyle f_{n}\,}$ e ${\displaystyle f_{n+1}\,}$ son primos relativos e que ${\displaystyle f_{k}\,}$ divide exactamente a ${\displaystyle f_{nk}\,}$

• Os números de Fibonacci aparecen ao sumar as diagonais do triángulo de Pascal. É dicir que para calquera ${\displaystyle n\geq 0}$,

Os números de Fibonacci son a suma das diagonais (marcadas en vermello) do triángulo de Pascal.

${\displaystyle f_{n+1}=\sum _{j=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\begin{pmatrix}n-j\\j\end{pmatrix}}}$

e máis aínda

${\displaystyle f_{3n}=\sum _{j=0}^{n}{\begin{pmatrix}n\\j\end{pmatrix}}2^{j}f_{j}}$

• Se ${\displaystyle f_{p}=a}$, tal que ${\displaystyle a}$ é un número primo, entón ${\displaystyle p}$ tamén é un número primo, cunha única excepción, ${\displaystyle f_{4}=3}$; 3 é un número primo, pero 4 non o é.
• A suma infinita dos termos da sucesión ${\displaystyle \textstyle {\frac {f_{n}}{10^{n}}}}$ é exactamente ${\displaystyle \textstyle {\frac {10}{89}}}$.
• A suma de dez números Fibonacci consecutivos é sempre 11 veces superior ao sétimo número da serie.
• O último díxito de cada número repítese periodicamente cada 60 números. Os dous últimos, cada 300; a partir de aí, repítense cada ${\displaystyle 15\times 10^{n-1}}$ números.

Xeneralizacións

Expansión a índices negativos

Gráfica da sucesión de Fibonacci estendida ao campo dos números reais.

O concepto fundamental da sucesión de Fibonacci é que cada elemento é a suma dos dous anteriores. Neste sentido a sucesión pode expandirse ao conxunto dos números enteiros como ${\displaystyle \ldots ,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,\ldots }$ de maneira que a suma de calquera dos números consecutivos é o inmediato seguinte. Para poder definir os índices negativos da sucesión, despéxase ${\displaystyle f_{n-2}\,}$ da ecuación (3) de onde se obten

${\displaystyle f_{n-2}=f_{n}-f_{n-1}\,}$

Desta maneira, ${\displaystyle f_{-n}=f_{n}\,}$ se ${\displaystyle n}$ é impar e ${\displaystyle f_{-n}=-f_{n}\,}$ se ${\displaystyle n}$ é par.

Expansión ao campo de números reais

A sucesión pódese expandir ao campo dos números reais tomando a parte real da fórmula explícita (ecuación (6)) cando ${\displaystyle n}$ é calquera número real. A función resultante

${\displaystyle f(x)={\frac {\varphi ^{x}-\cos(\pi x)\varphi ^{-x}}{\sqrt {5}}}}$

ten as mesmas características que a sucesión de Fibonacci:

• ${\displaystyle f(0)=0~}$
• ${\displaystyle f(1)=1~}$
• ${\displaystyle f(x)=f(x-1)+f(x-2)~}$ para calquera número real ${\displaystyle x}$

Números Gibonacci

Unha sucesión de Fibonacci xeneralizada (ou números Gibonacci^[10]), é unha sucesión ${\displaystyle g_{0},g_{1},g_{2},\ldots }$ onde

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

É dicir, cada elemento dunha sucesión de Fibonacci xeneralizada é a suma dos dous anteriores, pero non necesariamente comeza en 0 e 1.

Unha característica notable é que, se ${\displaystyle g_{0},g_{1},g_{2},\ldots }$ é unha sucesión de Fibonacci xeneralizada, entón

(10) ${\displaystyle g_{n}=f_{n-1}g_{0}+f_{n}g_{1}~}$

Por exemplo, a ecuación (7) pode xeneralizarse a

${\displaystyle {\begin{bmatrix}0&1\\1&1\end{bmatrix}}^{n}{\begin{bmatrix}g_{0}\\g_{1}\end{bmatrix}}={\begin{bmatrix}g_{n}\\g_{n+1}\end{bmatrix}}}$

Isto significa que calquera cálculo sobre unha sucesión de Fibonacci xeneralizada se pode efectuar usando números de Fibonacci.

Potencias de ${\displaystyle \varphi }$

Unha sucesión de Fibonacci xeneralizada moi importante, é a formada polas potencias do número áureo.

${\displaystyle \varphi ^{n}=\varphi ^{n-1}+\varphi ^{n-2}}$.

A importancia desta sucesión reside no feito de que se pode expandir directamente ao conxunto dos números reais.

${\displaystyle \varphi ^{x}=\varphi ^{x-1}+\varphi ^{x-2}}$.

...e ao dos complexos.

${\displaystyle \varphi ^{z}=\varphi ^{z-1}+\varphi ^{z-2}}$.

Sucesión de Lucas

Gráfica da sucesión de Lucas estendida ao campo dos números reais.

Un exemplo de sucesión de Fibonacci xeneralizada é a sucesión de Lucas, descrita polas ecuacións

• ${\displaystyle l_{0}=2~}$
• ${\displaystyle l_{1}=1~}$
• ${\displaystyle l_{n}=l_{n-1}+l_{n-2}~}$ para ${\displaystyle n\geq 2}$

${\textstyle 2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,\ldots \,}$ (secuencia A000032 na OEIS)

A sucesión de Lucas ten unha gran similitude coa sucesión de Fibonacci e comparte moitas das súas características. Algunhas propiedades interesantes inclúen:

• A proporción entre un número de Lucas e o seu sucesor inmediato aproxímase ao número áureo. É dicir

${\displaystyle \lim _{n\to \infty }{\frac {l_{n+1}}{l_{n}}}=\varphi }$

• A fórmula explícita para a sucesión de Lucas é

${\displaystyle l_{n}=\varphi ^{n}+(-\varphi )^{-n}}$

• A suma dos primeiros ${\displaystyle n}$ números de Lucas é o número que se atopa na posición ${\displaystyle n+2}$ menos un. É dicir

${\displaystyle l_{0}+l_{1}+l_{2}+\cdots +l_{n}=l_{n+2}-1}$

• Calquera fórmula que conteña un número de Lucas pode expresarse en termos de números de Fibonacci mediante a igualdade

${\displaystyle l_{n}=f_{n-1}+f_{n+1}~}$

e usando a ecuación (10) dos números Gibonacci temos tamén

${\displaystyle l_{n}=2f_{n-1}+f_{n}~}$

• Calquera fórmula que conteña un número de Fibonacci pode expresarse en termos de números de Lucas mediante a igualdade

${\displaystyle f_{n}={\frac {l_{n-1}+l_{n+1}}{5}}}$

Polinomios de Fibonacci

Hai varios tipos de polinomios de Fibonacci, os máis frecuentes están definidos como^[11][10]

${\displaystyle f_{n+1}(x)=xf_{n}(x)+f_{n-1}(x)}$

Unha pequena lista dos primeiros polinomios é:

${\displaystyle f_{1}(x)=1}$

${\displaystyle f_{2}(x)=x}$

${\displaystyle f_{3}(x)=x^{2}+1}$

${\displaystyle f_{4}(x)=x^{3}+2x}$

${\displaystyle f_{5}(x)=x^{4}+3x+1}$

Están relacionados de varias formas moi simples cos Polinomios de Chebyshev, por exemplo,^[10] ${\displaystyle f_{n}(2x)}$ son ${\displaystyle U_{n-1}(x)}$ sen alternancia de signo.

Unha segunda definición menos frecuente ten a recurrencia multiplicada por x no segundo termo^[12]

${\displaystyle f_{n+1}(x)=f_{n}(x)+xf_{n-1}(x)}$

Algoritmos de cálculo

Cálculo de ${\displaystyle f_{7}}$ usando o algoritmo recursivo.

Para calcular o ${\displaystyle n}$-ésimo elemento da sucesión de Fibonacci existen varios algoritmos. A definición mesma pode empregarse como un, que en pseudocódigo resulta:

función ${\displaystyle {\it {fib}}(n)\,}$

se ${\displaystyle n<2\,}$ entón

devolve ${\displaystyle n\,}$

noutro caso

devolve ${\displaystyle {\it {fib}}(n-1)+{\it {fib}}(n-2)\,}$

Empregando técnicas de análise dos algoritmos é posible demostrar que, a pesar da súa simplicidade, o algoritmo require efectuar ${\displaystyle f_{n+1}-1}$ sumas para poder atopar o resultado. Dado que a sucesión ${\displaystyle f_{n}}$ crece tan rápido como ${\displaystyle \varphi ^{n}}$, entón o algoritmo está na orde de ${\displaystyle \varphi ^{n}}$. É dicir, que este algoritmo é moi lento. Por exemplo, para calcular ${\displaystyle f_{50}}$ este algoritmo require efectuar 20 365 011 073 sumas.

Para evitar facer tantas contas, é común recorrer a unha calculadora e utilizar a ecuación (6), non obstante, dado que ${\displaystyle \varphi }$ é un número irracional, a única maneira de utilizar esta fórmula é utilizando unha aproximación de ${\displaystyle \varphi }$ e obtendo en consecuencia un resultado aproximado pero incorrecto. Por exemplo, se se usa unha calculadora de 10 díxitos, entón a fórmula anterior arroja como resultado ${\displaystyle f_{50}=1.258626903\times 10^{10}}$ aínda cando o resultado correcto é ${\displaystyle f_{50}=12586269025}$. Este erro faise cada vez máis grande conforme crece ${\displaystyle n}$.

Un método máis práctico evitaría calcular as mesmas sumas máis dunha vez. Considerando un par ${\displaystyle (i,j)\,}$ de números consecutivos da sucesión de Fibonacci, o seguinte par da sucesión é ${\displaystyle (j,i+j)\,}$, desta maneira se divisa un algoritmo onde só se require considerar dos números consecutivos da sucesión de Fibonacci en cada paso. Este método é o que usaríamos normalmente para facer o cálculo a lapis e papel. O algoritmo se expresa en pseudocódigo como:

función ${\displaystyle {\it {fib}}(n)\,}$

${\displaystyle i\gets 1}$

${\displaystyle j\gets 0}$

para ${\displaystyle k\,}$ dende ${\displaystyle 0\,}$ ata ${\displaystyle n-1\,}$ facer

${\displaystyle t\gets i+j}$

${\displaystyle j\gets i}$

${\displaystyle i\gets t}$

devolve ${\displaystyle j\,}$

Esta versión require efectuar só ${\displaystyle n}$ sumas para calcular ${\displaystyle f_{n}}$, o que significa que este método é considerablemente máis rápido que o primeiro algoritmo. Por exemplo, este segundo só require efectuar 50 sumas para calcular ${\displaystyle f_{50}}$.

Cálculo de ${\displaystyle f_{100}}$ usando o algoritmo “divide e vencerás”.

Un algoritmo aínda máis rápido conséguese partindo da ecuación (8). Utilizando as propiedades dos expoñentes é posible calcular ${\displaystyle x^{n}}$ como

${\displaystyle x^{n}={\begin{cases}x&{\mbox{se }}n=1\\\left(x^{\frac {n}{2}}\right)^{2}&{\mbox{se }}n{\mbox{ é par}}\\x\times x^{n-1}&{\mbox{se }}n{\mbox{ é impar}}\end{cases}}}$

Desta maneira aparece o algoritmo de tipo “divide e vencerás” onde só se requiriría facer, aproximadamente, ${\displaystyle \log _{2}(n)}$ multiplicacións matriciais. Non obstante, non é necesario almacenar os catro valores de cada matriz dado que cada unha ten a forma

${\displaystyle {\begin{bmatrix}a&b\\b&a+b\end{bmatrix}}}$

Desta maneira, cada matriz queda completamente representada polos valores ${\displaystyle a}$ e ${\displaystyle b}$, e o seu cadrado pódese calcular como

${\displaystyle {\begin{bmatrix}a&b\\b&a+b\end{bmatrix}}^{2}={\begin{bmatrix}a^{2}+b^{2}&b(2a+b)\\b(2a+b)&(a+b)^{2}+b^{2}\end{bmatrix}}}$

Polo tanto o algoritmo queda como segue:

función ${\displaystyle {\it {fib}}(n)\,}$

se ${\displaystyle n\leq 0}$ entón

devolve ${\displaystyle 0\,}$

${\displaystyle i\gets n-1}$

${\displaystyle auxOne\gets 0}$

${\displaystyle auxTwo\gets 1}$

${\displaystyle (a,b)\gets (auxTwo,auxOne)}$

${\displaystyle (c,d)\gets (auxOne,auxTwo)}$

mentres ${\displaystyle i>0\,}$ facer

se ${\displaystyle i\,}$ é impar entón

${\displaystyle auxOne\gets (db+ca)}$

${\displaystyle auxTwo\gets (d(b+a)+cb))}$

${\displaystyle (a,b)\gets (auxOne,auxTwo)}$

${\displaystyle auxOne\gets (c^{2}+d^{2})}$

${\displaystyle auxTwo\gets (d(2c+d))}$

${\displaystyle (c,d)\gets (auxOne,auxTwo)}$

${\displaystyle i\gets i\div 2}$

devolve ${\displaystyle a+b\,}$

A pesar do arduo que parece, este algoritmo permite reducir enormemente o número de operacións que se precisan para calcular números de Fibonacci moi grandes. Por exemplo, para calcular ${\displaystyle f_{100}}$, en vez de facer as 573 147 844 013 817 084 100 sumas do algoritmo recursivo ou as 100 sumas co algoritmo iterativo, o cálculo redúcese a tan só nove multiplicacións matriciais.

A sucesión de Fibonacci na natureza

Botón de Camomila amarilla que mostra a ordenación en espirais de módulos 21 (cor azul) e 13 (cor ciano). Este tipo de enrolamentos utilizando números consecutivos de Fibonacci aparecen nunha gran variedade de plantas.

A secuencia de Fibonacci atópase en múltiples configuracións biolóxicas,^[13] onde aparecen números consecutivos da sucesión, como na distribución das pólas das árbores, a distribución das follas nun talo, os froitos do ananás,^[14] as flores da alcachofa, nas piñas das coníferas,^[15] ou na "árbore xenealóxica" das abellas melíferas.^[16] Non obstante, tamén se fixeron moitas invocacións infundadas á aparición dos números de Fibonacci aproveitando a súa relación co número áureo na literatura popular.^[17]

Przemysław Prusinkiewicz avanzou a idea de considerar a sucesión de Fibonacci na natureza como un grupo libre.^[18]

Ilustración do modelo de Vogel para n=1 ... 500

Un modelo do padrón da distribución das sementes do xirasol foi proposto por H. Vogel en 1979.^[19] Presenta a forma

${\displaystyle \theta ={\frac {2\pi }{\phi ^{2}}}n,\ r=c{\sqrt {n}}}$

onde n é o índice da flor e c é un factor de escala; entón as sementes alíñanse segundo espirais de Fermat. O ángulo de diverxencia, de aproximadamente 137,51°, está relacionado co número áureo. Debido a que o coeficiente é un número irracional, ningunha semente ten ningunha veciña co mesmo ángulo respecto ao centro, polo que se compactan eficientemente. Debido a que as aproximacións racionais ao número áureo son da forma F(j):F(j + 1), os veciños máis próximos ao número de sementes n están todos en n ± F(j) para cada índice j, que depende de r, a distancia ao centro. Adoita afirmarse que os xirasois e flores similares teñen 55 espirais nunha dirección e 89 na outra (ou algunha outra parella de números adxacentes da sucesión de Fibonacci), pero isto só é certo en certos rangos de raio, xeralmente raros (e por iso máis notables).^[20]

A árbore xenealóxica das abellas

Os machos dunha colmea de abellas teñen unha árbore xenealóxica que cumpre con esta sucesión. O feito é que un abáboro (1), o macho da abella, non ten pai, pero si que ten unha nai (1, 1), dous avós, que son os pais da raíña (1, 1, 2), tres bisavós, xa que o pai da raíña non ten pai (1, 1, 2, 3), cinco tataravós (1, 1, 2, 3, 5), oito pais dos tataravós (1, 1, 2, 3, 5, 8) e así sucesivamente, cumprindo coa sucesión de Fibonacci.

Recentemente, unha análise histórico-matemática sobre o contexto de Leonardo de Pisa e a proximidade da cidade de Béjaïa, unha importante exportadora de cera nos tempos de Leonardo (da que provén o nome en francés desta cidade, "Bougie", que significa "candea"), suxeriu que fosen os criadores de abellas de Béjaïa e o coñecemento da ascendencia das abellas o que inspirou os números Fibonacci máis que o modelo de reprodución dos coellos.^[21]

Divisibilidade

• Sexan n e m enteiros positivos. Se o número n é divisible por m entón o termo n-ésimo de Fibonacci é divisible polo termo m-ésimo da mesma sucesión. En efecto 4 divide a 12 e o termo de orde catro, o 3, divide a 144, termo de orde 12 na sucesión^[22]
• Calquera que sexa o enteiro m, entre os ${\displaystyle m^{2}-1}$ primeiros números de Fibonacci haberá polo menos un divisible por m. Por exemplo, para m = 4, entre os primeiros quince números están 8 e 144, números de Fibonacci, divisibles por 4^[23]
• Se k é un número composto diferente de 4, entón o número k-ésimo de Fibonacci é composto.^[24] Por exemplo, para o caso 10, composto distinto de 4, o décimo número de Fibonacci 55, é composto.
• Os números consecutivos de Fibonacci son primos entre si.

Notas

1. John Hudson Tiner (2004). Exploring the Wold of Mathematics: From Ancient Record Keeping to the Latest Advances in Computers. Master Books división de New Leaf Publishing Group. ISBN 9781614581550.
2. A lenda que motivou esta sucesión "comezou cunha parella de coellos". Vorobiov: Números de Fibonacci
3. Singh, Parmanand (1985). "The So-called Fibonacci numbers in ancient and medieval India". Historia Mathematica 12 (3): 229–44. doi:10.1016/0315-0860(85)90021-7.
4. Knuth, Donald (1968). The Art of Computer Programming 1. Addison Wesley. ISBN 81-7758-754-4. Antes de que Fibonacci escribise o seu tratado, a secuencia F_n era estudada nas escolas da India, interesadas dende había moito tempo en patróns rítmicos... tanto Gopala (cara ao ano 1135 ) como Hemachandra (cara a 1150) mencionan os números 1, 2, 3, 5, 8, 13, 21 explicitamente [ver P. Singh Historia Math 12 (1985) 229–44]" p. 100 (3d ed)...
5. Goonatilake, Susantha (1998). Toward a Global Science. Indiana University Press. p. 126. ISBN 978-0-253-33388-9.
6. Agrawala, VS (1969). Pāṇinikālīna Bhāratavarṣa (Hn.). Varanasi-I: Tfeitowkhamba Vidyabhawan.
7. Laurence Sigler, Fibonacci's Liber Abaci, página 404
8. Handbook of discrete and combinatorial mathematics, sección 3.1.2
9. Fibonacci Quartely
10. Koshy, Thomas; Gao, Zhenguang (2017). Polynomial Extensions of a Diminnie Delight (PDF) 55. The Fibonacci Quarterly. pp. 13–21.
11. "Fibonacci Polynomial". Wolfram Mathworld.
12. "Fibonacci Polynomials". Oeis.
13. Douady, S; Couder, e (1996). "Phyllotaxis as a Dynamical Self Organizing Process" (PDF). Journal of Theoretical Biology 178 (178): 255–74. doi:10.1006/jtbi.1996.0026.^{[Ligazón morta]}
14. Jóns, Judy; Wilson, William (2006). "Science". An Incomplete Education. Ballantine Books. p. 544. ISBN 978-0-7394-7582-9.
15. Brousseau, A (1969). "Fibonacci Statistics in Conifers". Fibonacci Quartely (7): 525–32.
16. "Marks for the da Vinci Code: B–". Maths. Computer Science For Fun: CS4FN.
17. Simanek, D. "Fibonacci Flim-Flam". LHUP. Arquivado dende o orixinal o 01 de febreiro de 2010. Consultado o 03 de xullo de 2016.
18. Prusinkiewicz, Przemyslaw; Hanan, James (1989). Lindenmayer Systems, Fractals, and Plants (Lecture Notes in Biomathematics). Springer-Velag. ISBN 0-387-97092-4.
19. Vogel, H (1979). "A better way to construct the sunflower head". Mathematical Biosciences 44 (44): 179–89. doi:10.1016/0025-5564(79)90080-4.
20. Prusinkiewicz, Przemyslaw; Lindenmayer, Aristid (1990). The Algorithmic Beauty of Plants. Springer-Velag. pp. 101–7. ISBN 978-0-387-97297-8.
21. Scott, T. C.; Marketos, P. (2014). "On the Origin of the Fibonacci Sequence" (PDF). MacTutor History of Mathematics archive (en inglés) (University of St Andrews).
22. Vorobiov: Números de Fibonacci, Editorial Mir, Moscú. Esta sección esixe que a sucesión comece con 1 e con 0 (1974)
23. Vorobiov: Ibídem
24. Vorobiov: Op. cit

Véxase tamén

Wikimedia Commons ten máis contidos multimedia na categoría:  Sucesión de Fibonacci

Bibliografía

• Kolman, Bernard; Hill, David R. (2006). Álgebra Lineal. México: PEARSON EDUCACIÓN. ISBN 970-26-0696-9.
• Johnsonbaugh, Richard (2005). Matemáticas Discretas. México: PEARSON EDUCACIÓN. ISBN 970-26-0637-3.
• Brassard, G; Bratley, P. (1997). Fundamentos de Algoritmia. Madrid: PRETINCE HALL. ISBN 84-89660-00-X.
• Rosen, Kenneth H. (2003). Discrete mathematics and its applications. McGraw Hill. ISBN 0-07-123374-1.
• Rosen, Kenneth H.; Michaels, John G. (1999). Handbook of discrete and combinatorial mathematics. CRC. ISBN 0-8493-0149-1.
• Vorobiov, N. N. (1974). Números de Fibonacci. Moscova: Editorial Mir.
• Markushevich, A. I. (1974; 1981). Sucesiones recurrentes. Moscova: Editorial Mir.
• Pacioli, Luca (1946). La Divina Proporción. Buenos Aires: Editorial Losada.
• Hrant Arakelian (2014). Mathematics and History of the Golden Section. Logos, 404 p. ISBN 978-5-98704-663-0.

Outros artigos

• Número áureo
• Sucesión matemática
• Sistema-L
• Espiral logarítmica
• Montículo de Fibonacci

Ligazóns externas

• Fibonacci's Liber Abaci vista previa en Google Books (en inglés)
• The Fibonacci Sequence (en inglés)
• The Fibonacci Quarterly. Publicación trimestral, poden lerse gratuítos todos os números anteriores aos últimos 4 anos.