Sucesión De Fibonacci

${\textstyle 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597\ldots \,}$

A sucesión comeza cos números 0 e 1, 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.

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.

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)". Parmanand Singh cita a Pingala (cara a 450) como precursor no descubrimento da secuencia.

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».

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

 

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.

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.

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

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 (), () e () 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 () 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 \,}$ . De feito, a relación con este número é estreita.

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 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.

 

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

 

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

 

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

 

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 () 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.

A sucesión pódese expandir ao campo dos números reais tomando a parte real da fórmula explícita (ecuación ()) 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}$ 

Unha sucesión de Fibonacci xeneralizada é 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 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}}$ .

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

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

Por exemplo, a ecuación () 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.

Sucesión de Lucas

 

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=2,3,4,5,\ldots }$ 

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 es

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

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

 

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 (), 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}}$ .

 

Un algoritmo aínda máis rápido conséguese partindo da ecuación (). 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 secuencia de Fibonacci atópase en múltiples configuracións biolóxicas, onde aparecen números consecutivos da sucesión, como na distribución das pólas das árbores, a distribución das follas nun tallo, os froitos do ananás, as flores da alcachofa, nas piñas das coníferas, ou na "árbore xenealóxica" das abellas melíferas. 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.

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

 

Un modelo do padrón da distribución das sementes do xirasol foi proposto por H. Vogel en 1979. 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).

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.

• 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
• 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
• Se k é un número composto diferente de 4, entón o número k-ésimo de Fibonacci é composto. 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.

Wiki 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)