Sucesión de Fibonacci

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

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; acaroando sucesivamente cadrados de lado 0, 1, 1, 2, 3, 5, 8, 13, 21 e 34.

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.

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.

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

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.

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 $f_{n+1}/f_{n}$ se achega á relación áurea fi ($\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) $f_{n}=f_{n-1}+f_{n-2}\,$

partindo de dous primeiros valores predeterminados:

$f_{0}=0\,$

$f_{1}=1\,$

obtéñense os seguintes números:

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

para $n=2,3,4,5,\ldots$

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

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

$f_{n}$ divide a $f_{m*n}$, para calquera $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 $a_{0},a_{1},a_{2},\dots$ é a función $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) $f\left(x\right)={\frac {x}{1-x-x^{2}}}$

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

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

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

coas condicións iniciais

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

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

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

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

$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 $b$ e $d$ satisfán a ecuación anterior cando $n=0$ e $n=1$, é dicir que satisfán o sistema de ecuacións

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

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

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

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

(6) $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 $\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

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

${\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 $f_{0}=0$ e $f_{1}=1$, ao aplicar a fórmula anterior $n$ veces obtense

(7) ${\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) ${\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 $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:

$\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, $17=13+3+1$, $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 $m$, para calquera $m$.
• A sucesión pode expresarse mediante outra fórmula explícita chamada forma de Binet (de Jacques Binet). Se $\textstyle \alpha ={\frac {1+{\sqrt {5}}}{2}}$ e $\textstyle \beta ={\frac {1-{\sqrt {5}}}{2}}$, entón

$f_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}$ e $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

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

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

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

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

• Outras identidades interesantes inclúen as seguintes:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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

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

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

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

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

$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

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

• Se $f_{p}=a$, tal que $a$ é un número primo, entón $p$ tamén é un número primo, cunha única excepción, $f_{4}=3$; 3 é un número primo, pero 4 non o é.
• A suma infinita dos termos da sucesión $\textstyle {\frac {f_{n}}{10^{n}}}$ é exactamente $\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 $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 $\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 $f_{n-2}\,$ da ecuación (3) de onde se obten

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

Desta maneira, $f_{-n}=f_{n}\,$ se $n$ é impar e $f_{-n}=-f_{n}\,$ se $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 $n$ é calquera número real. A función resultante

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

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

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

Números Gibonacci

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

(9) $g_{n}=g_{n-1}+g_{n-2}\,$ para $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 $g_{0},g_{1},g_{2},\ldots$ é unha sucesión de Fibonacci xeneralizada, entón

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

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

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

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

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

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

...e ao dos complexos.

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

• $l_{0}=2~$
• $l_{1}=1~$
• $l_{n}=l_{n-1}+l_{n-2}~$ para $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

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

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

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

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

$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

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

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

$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

$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

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

Unha pequena lista dos primeiros polinomios é:

$f_{1}(x)=1$

$f_{2}(x)=x$

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

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

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

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

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

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

Algoritmos de cálculo

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

Para calcular o $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 ${\it {fib}}(n)\,$

se $n<2\,$ entón

devolve $n\,$

noutro caso

devolve ${\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 $f_{n+1}-1$ sumas para poder atopar o resultado. Dado que a sucesión $f_{n}$ crece tan rápido como $\varphi ^{n}$, entón o algoritmo está na orde de $\varphi ^{n}$. É dicir, que este algoritmo é moi lento. Por exemplo, para calcular $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 $\varphi$ é un número irracional, a única maneira de utilizar esta fórmula é utilizando unha aproximación de $\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 $f_{50}=1.258626903\times 10^{10}$ aínda cando o resultado correcto é $f_{50}=12586269025$. Este erro faise cada vez máis grande conforme crece $n$.

Un método máis práctico evitaría calcular as mesmas sumas máis dunha vez. Considerando un par $(i,j)\,$ de números consecutivos da sucesión de Fibonacci, o seguinte par da sucesión é $(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 ${\it {fib}}(n)\,$

$i\gets 1$

$j\gets 0$

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

$t\gets i+j$

$j\gets i$

$i\gets t$

devolve $j\,$

Esta versión require efectuar só $n$ sumas para calcular $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 $f_{50}$.

Cálculo de $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 $x^{n}$ como

$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, $\log _{2}(n)$ multiplicacións matriciais. Non obstante, non é necesario almacenar os catro valores de cada matriz dado que cada unha ten a forma

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

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

${\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 ${\it {fib}}(n)\,$

se $n\leq 0$ entón

devolve $0\,$

$i\gets n-1$

$auxOne\gets 0$

$auxTwo\gets 1$

$(a,b)\gets (auxTwo,auxOne)$

$(c,d)\gets (auxOne,auxTwo)$

mentres $i>0\,$ facer

se $i\,$ é impar entón

$auxOne\gets (db+ca)$

$auxTwo\gets (d(b+a)+cb))$

$(a,b)\gets (auxOne,auxTwo)$

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

$auxTwo\gets (d(2c+d))$

$(c,d)\gets (auxOne,auxTwo)$

$i\gets i\div 2$

devolve $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 $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, 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, 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.

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. Presenta a forma

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

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
• Calquera que sexa o enteiro m, entre os $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.

Véxase tamén

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.