Ver o código fonte de «Sucesión de Fibonacci»

[[Ficheiro:First members of Fibonacci sequence.svg|miniatura|280px|[[Gráfica dunha función|Gráfica]] da sucesión de Fibonacci ata <math>f_{7}</math>]]
En [[matemáticas]], a '''sucesión de Fibonacci''' é a [[Sucesión matemática|sucesión]] de [[Número natural|números naturais]]:
:<math display="inline">0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597
\ldots \,</math> {{OEIS|id=A000045}}
[[Ficheiro:Fibonacci spiral 34.svg|right|miniatura|280px|A espiral de Fibonacci: unha aproximación da [[espiral dourada|espiral áurea]] xerada debuxando arcos circulares conectando as esquinas opostas dos cadrados axustados aos valores da sucesión;<ref>{{Cita libro | url = http://books.google.com/books?id=CDEEAwAAQBAJ&pg=PA81| title = Exploring the Wold of Mathematics: From Ancient Record Keeping to the Latest Advances in Computers | author = John Hudson Tiner | publisher = Master Books división de New Leaf Publishing Group | year = 2004 | isbn = 9781614581550}}</ref> 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,<ref>A lenda que motivou esta sucesión "comezou cunha parella de coellos". Vorobiov: Números de Fibonacci</ref> 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 [[filotaxe|disposición das follas no talo]], nas flores das [[alcachofa]]s e [[xirasol|xirasois]], nas inflorescencias do brócoli [[romanesco]] e na configuración das [[cono (botánica)|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 [[lingua sánscrita|sánscrita]].<ref name = "HistoriaMathematica">{{cita publicación periódica|first=Parmanand|last=Singh|title= The So-called Fibonacci numbers in ancient and medieval India|journal=Historia Mathematica|volume=12|issue=3|pages=229–44|year=1985|doi = 10.1016/0315-0860(85)90021-7}}</ref><ref name=knuth-v1>{{cita libro|title=The Art of Computer Programming | volume = 1 | first = Donald | last = Knuth | author-link =Donald Knuth |publisher=Addison Wesley |year=1968 | isbn = 81-7758-754-4 |url = http://books.google.com/?id=MooMkK6ERuYC&pg=PA100&dq=knuth+gopala+fibonacci#v=onepage& | quote = Antes de que Fibonacci escribise o seu tratado, a secuencia F<sub>n</sub> 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)...}}</ref>

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)".<ref name="GlobalScience">{{cita libro|title =Toward a Global Science | first = Susantha | last = Goonatilake |publisher = Indiana University Press |year = 1998 |page = 126 |isbn = 978-0-253-33388-9 |url =http://books.google.com/?id=SI5ip95BbgEC&pg=PA126&dq=Virahanka+Fibonacci}}</ref> Parmanand Singh cita a Pingala (cara a 450) como precursor no descubrimento da secuencia.<ref>{{cita libro| last = Agrawala | first = VS | year = 1969 | title = ''Pāṇinikālīna Bhāratavarṣa'' (Hn.). Varanasi-I: Tfeitowkhamba Vidyabhawan}}</ref>

A sucesión foi descrita e dada a coñecer en occidente por [[Leonardo Fibonacci|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».<ref name="Liberabaci">Laurence Sigler, Fibonacci's Liber Abaci, página 404</ref>

{| class="wikitable"
|-
! 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.
[[Ficheiro:Liber abbaci magliab f124r.jpg|miniatura|220px|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.<ref name="Handbook">Handbook of discrete and combinatorial mathematics, sección 3.1.2</ref>

Tamén [[Johannes Kepler|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 <math>f_{n+1}/f_n</math> se achega á relación [[Número áureo|áurea]] ''fi'' (<math>\phi</math>) 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:
{{Ecuación|<math>f_n = f_{n-1} + f_{n-2}\,</math>|3}}
partindo de dous primeiros valores predeterminados:
:<math>f_0 = 0\,</math>
:<math>f_1 = 1\,</math>
obtéñense os seguintes números:
* <math>f_2 = 1\,</math>
* <math>f_3 = 2\,</math>
* <math>f_4 = 3\,</math>
* <math>f_5 = 5\,</math>
* <math>f_6 = 8\,</math>
* <math>f_7 = 13\,</math>
* <math>f_8 = 21\,</math>
para <math>n = 2,3,4,5,\ldots</math>

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

É importante definir <math>f_0 = 0\,</math> para que se poida cumprir a importante propiedade de que:

<math>f_n</math> divide a <math>f_{m*n}</math>, para calquera <math> m, n >= 1 </math>.

== 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 <math>a_0,a_1,a_2,\dots</math> é a función <math>f(x) = a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+\cdots</math>, é 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
{{Ecuación|<math>f\left(x\right)=\frac{x}{1-x-x^2}</math>|4}}

Cando esta función se expande en potencias de <math>x\,</math>, os coeficientes resultan ser a sucesión de Fibonacci:
:<math>\frac{x}{1-x-x^2}=0x^0+1x^1+1x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots</math>

=== Fórmula explícita ===
A definición da sucesión de Fibonacci é [[Relación de recorrencia|recorrente]]; é dicir que se necesitan calcular varios termos anteriores para poder calcular un termo específico. Pódese obter unha [[forma pechada|fórmula explícita]] da sucesión de Fibonacci (que non require calcular termos anteriores) notando que as ecuacións {{Eqnref|1}}, {{Eqnref|2}} e {{Eqnref|3}} definen a relación de recorrencia
:<math>f_{n+2}-f_{n+1}-f_n=0\,</math>
coas condicións iniciais
:<math>f_0=0\,</math> e <math>f_1=1\,</math>

O [[polinomio característico]] desta relación de recorrencia é <math>t^2-t-1=0</math>, e as súas raíces son
:<math>t=\frac{1\pm\sqrt 5}{2}</math>
Desta maneira, a fórmula explícita da sucesión de Fibonacci terá a forma
:<math>f_n=b\left(\frac{1+\sqrt5}2\right)^n+d\left(\frac{1-\sqrt5}2\right)^n</math>.

Se se teñen en conta as condicións iniciais, entón as constantes <math>b</math> e <math>d</math> satisfán a ecuación anterior cando <math>n = 0</math> e <math>n = 1</math>, é dicir que satisfán o sistema de ecuacións
:<math>\left.\begin{array}{rcl}b+d & = & 0 \\ b\left(\frac{1+\sqrt5}2\right)+d\left(\frac{1-\sqrt5}2\right)&=&1\end{array}\right\}</math>

Ao resolver este sistema de ecuacións obtense
:<math>b=\frac1{\sqrt5},d=-\frac1{\sqrt5}</math>

Polo tanto, cada número da sucesión de Fibonacci pode ser expresado como
{{Ecuación|<math>f_n=\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^n-\frac1{\sqrt5}\left(\frac{1-\sqrt5}2\right)^n</math>|5}}

Para simplificar aínda máis é necesario considerar o [[número áureo]]
:<math>\varphi=\frac{1+\sqrt5}2</math>

de maneira que a ecuación {{Eqnref|5}} se reduce a
{{Ecuación|<math>f_n=\frac{\varphi^n-\left(1-\varphi\right)^{n}}{\sqrt5}</math>|6}}

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]] <math>\varphi\,</math> ([[fi]]). De feito, a relación con este número é estreita. Este tipo de fórmulas pechadas para obter o elemento {{Mvar|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]]
:<math>\left . \begin{array}{rcl}
 f_{n} &=& f_{n} \\
f_{n-1} + f_{n} &=& f_{n+1}
\end{array} \right \}</math>
Este sistema pode representarse mediante a súa notación matricial como
:<math>\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}</math>
Coñecendo a <math>f_0=0</math> e <math>f_1=1</math>, ao aplicar a fórmula anterior <math>n</math> veces obtense
{{Ecuación|<math>\begin{bmatrix}0&1\\1&1\end{bmatrix}^n\begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix}f_{n}\\f_{n+1}\end{bmatrix}</math>|7}} 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
{{Ecuación|<math>\begin{bmatrix}0&1\\1&1\end{bmatrix}^n=\begin{bmatrix}f_{n-1}&f_n\\f_n&f_{n+1}\end{bmatrix}</math>|8}}
Estas igualdades poden probarse mediante indución matemática.

== Propiedades da sucesión ==
[[Ficheiro:FibonacciBlocks.svg|miniatura|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 <math>n</math> que non teñen ceros consecutivos e nunha vasta cantidade de contextos diferentes. De feito, existe unha publicación especializada chamada ''Fibonacci Quartely''<ref>[http://www.fq.math.ca/ Fibonacci Quartely]</ref> 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:
{{ecuación|<math>\lim_{n\to\infty}\frac{f_{n+1}}{f_n}=\varphi</math>}}
: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 [[asíntota|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, <math>17=13+3+1</math>, <math>65=55+8+2</math>.
* Tan só un termo de cada tres é par, un de cada catro é [[divisor|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 [[Aritmética modular|congruencias]] módulo <math>m</math>, para calquera <math>m</math>.
* A sucesión pode expresarse mediante outra fórmula explícita chamada ''forma de Binet'' (de [[Jacques Philippe Marie Binet|Jacques Binet]]). Se <math>\textstyle\alpha = \frac{1+\sqrt 5}{2}</math> e <math>\textstyle\beta = \frac{1-\sqrt 5}{2}</math>, entón
:<math>f_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}</math> e <math>f_n\approx\frac{\alpha^n}{\sqrt 5}\,</math>
* 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
:<math>f_n=\frac{f_{n-2}+f_{n+1}}2</math>
* 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.
:<math>f_{n+1}= f_{n} * 2 - f_{n-2}</math>
* A suma dos <math>n</math> primeiros números é igual ao número que ocupa a posición <math>n+2</math> menos un. É dicir
:<math>f_0+f_1+f_2+\cdots+f_n=f_{n+2}-1</math>
* Outras identidades interesantes inclúen as seguintes:
:<math>f_0-f_1+f_2-\cdots+(-1)^nf_n=(-1)^nf_{n-1}-1</math>
:<math>f_1+f_3+f_5+\cdots+f_{2n-1}=f_{2n}</math>
:<math>f_0+f_2+f_4+\cdots+f_{2n}=f_{2n+1}-1</math>
:<math>f_0^2+f_1^2+f_2^2+\cdots+f_n^2=f_nf_{n+1}</math>
:<math>f_1f_2+f_2f_3+f_3f_4+\cdots+f_{2n-1}f_{2n}=f_{2n}^2</math>
:<math>f_1f_2+f_2f_3+f_3f_4+\cdots+f_{2n}f_{2n+1}=f_{2n+1}^2-1</math>
:Se <math>k\geq1</math>, entón <math>f_{n+k}=f_kf_{n+1}+f_{k-1}f_n\,</math> para calquera <math>n\geq0</math>
:<math>f_{n+1}f_{n-1}-f_n^2=(-1)^n</math> (''Identidade de [[Giovanni Cassini|Cassini]]'')
:<math>f_{n+1}^2+f_n^2=f_{2n+1}</math>
:<math>f_{n+2}^2-f_{n+1}^2=f_nf_{n+3}</math>
[[Ficheiro:Fibonacci phi.JPG|miniatura|Phi forma parte dunha expresión da sucesión de Fibonacci.]]
<br>
:<math>f_{n+2}^2-f_n^2=f_{2n+2}</math>
:<math>f_{n+2}^3+f_{n+1}^3-f_n^3=f_{3n+3}</math>
:<math>f_{n}=\varphi ^{n+1}-(f_{n+1})\varphi</math> (''con φ = número áureo'') ou despexando f(n+1) e aplicando 1/φ = φ-1:
:<math>f_{n+1}=\varphi ^{n}+(1-\varphi)f_{n}</math>

* O [[máximo común divisor]] de dous números de Fibonacci é outro número de Fibonacci. Máis especificamente
:<math>\mathrm{mcd}\left(f_n,f_m\right)=f_{\mathrm{mcd}\left(n,m\right)}</math>
:Isto significa que <math>f_n\,</math> e <math>f_{n+1}\,</math> son [[Números primos entre si|primos relativos]] e que <math>f_k\,</math> [[Divisibilidade|divide exactamente]] a <math>f_{nk}\,</math>
* Os números de Fibonacci aparecen ao sumar as diagonais do [[triángulo de Pascal]]. É dicir que para calquera <math>n\geq0</math>,
[[Ficheiro:PascalTriangleFibanacci.svg|miniatura|right|360px|Os números de Fibonacci son a suma das diagonais (marcadas en vermello) do [[triángulo de Pascal]].]]
:<math>f_{n+1}=\sum_{j=0}^{\left\lfloor\frac n 2\right\rfloor}\begin{pmatrix}n-j\\j\end{pmatrix}</math>
:e máis aínda
:<math>f_{3n}=\sum_{j=0}^n\begin{pmatrix}n\\j\end{pmatrix}2^jf_j</math>
* Se <math>f_p = a</math>, tal que <math>a</math> é un [[número primo]], entón <math>p</math> tamén é un número primo, cunha única excepción, <math>f_4=3</math>; 3 é un número primo, pero 4 non o é.
* A suma infinita dos termos da sucesión <math>\textstyle\frac{f_n}{10^n}</math> é exactamente <math>\textstyle\frac{10}{89}</math>.
* 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 <math>15\times10^{n-1}</math> números.

== Xeneralizacións ==
=== Expansión a índices negativos ===
[[Ficheiro:Fibonacci continuous.png|miniatura|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úmero enteiro|números enteiros]] como <math>\ldots,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,\ldots</math> 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 <math>f_{n-2}\,</math> da ecuación {{Eqnref|3}} de onde se obten
:<math>f_{n-2}=f_n-f_{n-1}\,</math>
Desta maneira, <math>f_{-n}=f_n\,</math> se <math>n</math> é impar e <math>f_{-n}=-f_n\,</math> se <math>n</math> é par.

=== Expansión ao campo de números reais ===
A sucesión pódese expandir ao campo dos [[Número real|números reais]] tomando a parte real da fórmula explícita (ecuación {{Eqnref|6}}) cando <math>n</math> é calquera número real. A función resultante
:<math>f(x)=\frac{\varphi^x-\cos(\pi x)\varphi^{-x}}{\sqrt 5}</math>
ten as mesmas características que a sucesión de Fibonacci:
* <math>f(0)=0~</math>
* <math>f(1)=1~</math>
* <math>f(x)=f(x-1)+f(x-2)~</math> para calquera número real <math>x</math>

=== Números '''Gibonacci'''=== 
Unha '''sucesión de Fibonacci xeneralizada''' (ou números Gibonacci<ref name="koshygao">{{Cita libro|title=Polynomial Extensions of a Diminnie Delight|first=Thomas|last=Koshy|first2=Zhenguang |last2=Gao|publisher=The Fibonacci Quarterly|ano=2017|volume=55|páxinas=13-21|url=https://www.fq.math.ca/Papers1/55-1/KoshyGao10272016.pdf}}</ref>), é unha sucesión <math>g_0,g_1,g_2,\ldots</math> onde
{{Ecuación|<math>g_n=g_{n-1}+g_{n-2}\,</math> para <math>n=2,3,4,5,\ldots</math>|9}}
É 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 <math>g_0,g_1,g_2,\ldots</math> é unha sucesión de Fibonacci xeneralizada, entón
:{{Ecuación|<math>g_n=f_{n-1}g_0+f_ng_1~</math>|10}}

Por exemplo, a ecuación {{Eqnref|7}} pode xeneralizarse a
:<math>\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}</math>
Isto significa que calquera cálculo sobre unha sucesión de Fibonacci xeneralizada se pode efectuar usando números de Fibonacci.

=== Potencias de <math> \varphi </math>===
Unha sucesión de Fibonacci xeneralizada moi importante, é a formada polas potencias do número áureo.
:<math> \varphi^n=\varphi^{n-1}+\varphi^{n-2}</math>.

A importancia desta sucesión reside no feito de que se pode expandir directamente ao conxunto dos números reais.
:<math> \varphi^x=\varphi^{x-1}+\varphi^{x-2}</math>.
...e ao dos complexos.
:<math> \varphi^z=\varphi^{z-1}+\varphi^{z-2}</math>.

=== Sucesión de Lucas ===
[[Ficheiro:Lucas continuous.png|miniatura|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
* <math>l_0=2~</math>
* <math>l_1=1~</math>
* <math>l_n=l_{n-1}+l_{n-2}~</math> para <math>n \ge 2</math>
:<math display="inline">2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571,
\ldots \,</math> {{OEIS|id=A000032}}
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
:<math>\lim_{n\to\infty}\frac{l_{n+1}}{l_n}=\varphi</math>
* A fórmula explícita para a sucesión de Lucas é
:<math>l_n=\varphi^n+(-\varphi)^{-n}</math>
* A suma dos primeiros <math>n</math> números de Lucas é o número que se atopa na posición <math>n+2</math> menos un. É dicir
:<math>l_0+l_1+l_2+\cdots+l_n=l_{n+2}-1</math>
* Calquera fórmula que conteña un número de Lucas pode expresarse en termos de números de Fibonacci mediante a igualdade
:<math>l_n=f_{n-1}+f_{n+1}~</math>
: e usando a ecuación {{Eqnref|10}} dos números Gibonacci temos tamén
:<math>l_n=2f_{n-1}+f_{n}~</math>
* Calquera fórmula que conteña un número de Fibonacci pode expresarse en termos de números de Lucas mediante a igualdade
:<math>f_n=\frac{l_{n-1}+l_{n+1}}{5}</math>

=== Polinomios de Fibonacci ===
Hai varios tipos de polinomios de Fibonacci, os máis frecuentes están definidos como<ref>{{Cita web|title=Fibonacci Polynomial|publisher=Wolfram Mathworld|url=https://mathworld.wolfram.com/FibonacciPolynomial.html}}</ref><ref name="koshygao"/>
: <math> f_{n+1}(x) = x  f_{n}(x) + f_{n-1}(x) </math> 
Unha pequena lista dos primeiros polinomios é:

<math>f_1(x)=1</math>

<math>f_2(x)=x</math>

<math>f_3(x)=x^2 + 1</math>

<math>f_4(x)=x^3 + 2x</math>

<math>f_5(x)=x^4 + 3x + 1</math>

Están relacionados de varias formas moi simples cos [[Polinomios de Chebyshev]], por exemplo,<ref name="koshygao"/> <math>f_n(2x)</math> son <math>U_{n-1}(x)</math> sen alternancia de signo. 

Unha segunda definición menos frecuente ten a recurrencia multiplicada por {{Mvar|x}} no segundo termo<ref>{{Cita web|title=Fibonacci Polynomials|publisher=[[On-Line_Encyclopedia_of_Integer_Sequences|Oeis]]|url=https://oeis.org/wiki/Fibonacci_polynomials#cite_note-1}}</ref> 

: <math> f_{n+1}(x) = f_{n}(x) + xf_{n-1}(x) </math>

== Algoritmos de cálculo ==
[[Ficheiro:FibbonacciRecurisive.png|miniatura|Cálculo de <math>f_7</math> usando o algoritmo recursivo.]]
Para calcular o <math>n</math>-ésimo elemento da sucesión de Fibonacci existen varios [[algoritmo]]s. A definición mesma pode empregarse como un, que en [[pseudocódigo]] resulta:

'''función''' <math>{\it fib}(n)\,</math>
:'''se''' <math>n<2\,</math> '''entón'''
::'''devolve''' <math>n\,</math>
:'''noutro caso'''
::'''devolve''' <math>{\it fib}(n-1) + {\it fib}(n-2)\,</math>

Empregando técnicas de [[análise dos algoritmos]] é posible demostrar que, a pesar da súa simplicidade, o algoritmo require efectuar <math>f_{n+1}-1</math> sumas para poder atopar o resultado. Dado que a sucesión <math>f_n</math> [[Cota axustada asintótica|crece tan rápido]] como <math>\varphi^n</math>, entón o algoritmo está na orde de <math>\varphi^n</math>. É dicir, que este algoritmo é moi lento. Por exemplo, para calcular <math>f_{50}</math> este algoritmo require efectuar 20&nbsp;365&nbsp;011&nbsp;073 sumas.

Para evitar facer tantas contas, é común recorrer a unha calculadora e utilizar a ecuación {{Eqnref|6}}, non obstante, dado que <math>\varphi</math> é un [[número irracional]], a única maneira de utilizar esta fórmula é utilizando unha aproximación de <math>\varphi</math> 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 <math>f_{50}=1.258626903\times10^{10}</math> aínda cando o resultado correcto é <math>f_{50}=12586269025</math>. Este erro faise cada vez máis grande conforme crece <math>n</math>.

Un método máis práctico evitaría calcular as mesmas sumas máis dunha vez. Considerando un par <math>(i,j)\,</math> de números consecutivos da sucesión de Fibonacci, o seguinte par da sucesión é <math>(j,i+j)\,</math>, 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''' <math>{\it fib}(n)\,</math>
:<math>i\gets 1</math>
:<math>j\gets 0</math>
:'''para''' <math>k\,</math> dende <math>0\,</math> ata <math>n-1\,</math> '''facer'''
::<math>t\gets i+j</math>
::<math>j\gets i</math>
::<math>i\gets t</math>
:'''devolve''' <math>j\,</math>

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

[[Ficheiro:FibDC Example.png|miniatura|Cálculo de <math>f_{100}</math> usando o algoritmo “divide e vencerás”.]]
Un algoritmo aínda máis rápido conséguese partindo da ecuación {{Eqnref|8}}. Utilizando as propiedades dos expoñentes é posible calcular <math>x^n</math> como

:<math>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}</math>

Desta maneira aparece o algoritmo de tipo “divide e vencerás” onde só se requiriría facer, aproximadamente, <math>\log_2(n)</math> [[Produto de matrices|multiplicacións matriciais]]. Non obstante, non é necesario almacenar os catro valores de cada matriz dado que cada unha ten a forma
:<math>\begin{bmatrix} a & b \\ b & a+b \end{bmatrix}</math>
Desta maneira, cada matriz queda completamente representada polos valores <math>a</math> e <math>b</math>, e o seu cadrado pódese calcular como
:<math>\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}</math>
Polo tanto o algoritmo queda como segue:

'''función''' <math>{\it fib}(n)\,</math>
:'''se''' <math>n\leq0</math> '''entón'''
::'''devolve''' <math>0\,</math>
:<math>i\gets n-1</math>
:<math>auxOne\gets 0</math>
:<math>auxTwo\gets 1</math>
:<math>(a,b) \gets (auxTwo,auxOne)</math>
:<math>(c,d) \gets (auxOne,auxTwo)</math>
:'''mentres''' <math>i > 0\,</math> '''facer'''
::'''se''' <math>i\,</math> é impar '''entón'''
:::<math>auxOne\gets (db + ca)</math>
:::<math>auxTwo\gets (d(b + a) + cb))</math>
:::<math>(a,b) \gets (auxOne, auxTwo)</math>
::<math>auxOne\gets (c^2 + d^2)</math>
::<math>auxTwo\gets (d(2c + d))</math>
::<math>(c,d) \gets (auxOne, auxTwo)</math>
::<math>i\gets i\div 2</math>
:'''devolve''' <math>a+b\,</math>

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 <math>f_{100}</math>, en vez de facer as 573&nbsp;147&nbsp;844&nbsp;013&nbsp;817&nbsp;084&nbsp;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 ==
[[Ficheiro:FibonacciChamomile.PNG|miniatura|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,<ref name="S. Douady and Y. Couder 1996 255–274">{{cita publicación periódica |first1=S |last1=Douady |first2=e |last2=Couder |title=Phyllotaxis as a Dynamical Self Organizing Process |journal=Journal of Theoretical Biology |year=1996 |issue=178 |pages=255–74 |url=http://www.math.ntnu.no/~jalet/Douady96.pdf |doi=10.1006/jtbi.1996.0026 |volume=178 |format=PDF }}{{Ligazón morta|data=setembro de 2018 }}</ref> onde aparecen números consecutivos da sucesión, como na distribución das pólas das árbores, a [[Filotaxe|distribución das follas nun talo]], os froitos do [[ananás]],<ref name="Jóns 2006 544">{{cita libro| first1 =Judy |last1 =Jóns | first2 =William | last2 = Wilson |title=An Incomplete Education | url =https://archive.org/details/incompleteeducat00jone_950 |publisher = Ballantine Books |year=2006 |isbn= 978-0-7394-7582-9 |page= [https://archive.org/details/incompleteeducat00jone_950/page/n563 544] |chapter = Science}}</ref> as flores da [[alcachofa]], nas [[piña (coníferas)|piñas das coníferas]],<ref name = "A. Brousseau 1969 525–532">{{cita publicación periódica| first = A | last = Brousseau |title= Fibonacci Statistics in Conifers | journal = [[Fibonacci Quartely]] |year=1969 |issue=7 |pages= 525–32}}</ref> ou na "[[árbore xenealóxica]]" das abellas melíferas.<ref>{{Cita web|url = http://www.cs4fn.org/maths/bee-davinci.php |work = Maths | publisher = Computer Science For Fun: CS4FN |title = Marks for the da Vinci Code: B–}}</ref> 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.<ref>{{Cita web | url = http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm | title = Fibonacci Flim-Flam | first = D | last = Simanek | publisher = LHUP | data-acceso = 03 de xullo de 2016 | urlarquivo = https://www.webcitation.org/5nDtkyeKW?url=http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm | dataarquivo = 01 de febreiro de 2010 | urlmorta = yes }}</ref>

[[Przemysław Prusinkiewicz]] avanzou a idea de considerar a sucesión de Fibonacci na natureza como un [[grupo libre]].<ref>{{cita libro|first1 = Przemyslaw |last1 = Prusinkiewicz | first2 = James | last2 = Hanan| title = Lindenmayer Systems, Fractals, and Plants (Lecture Notes in Biomathematics) |publisher= [[Springer Science+Business Media|Springer-Velag]] |year=1989 |isbn=0-387-97092-4}}</ref>
[[Ficheiro:SunflowerModel.svg|miniatura|left|Ilustración do modelo de Vogel para ''n''=1&nbsp;... 500]]

Un modelo do padrón da distribución das sementes do [[xirasol]] foi proposto por H. Vogel en 1979.<ref>{{cita publicación periódica| last =Vogel | first =H | title =A better way to construct the sunflower head | journal = Mathematical Biosciences | issue =44 | pages = 179–89 | year = 1979 | doi = 10.1016/0025-5564(79)90080-4 | volume = 44}}</ref> Presenta a forma

:<math>\theta = \frac{2\pi}{\phi^2} n,\ r = c \sqrt{n}</math>

onde ''n'' é o índice da flor e ''c'' é un factor de escala; entón as sementes alíñanse segundo [[espiral de Fermat|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''&nbsp;+&nbsp;1), os veciños máis próximos ao número de sementes ''n'' están todos en ''n''&nbsp;±&nbsp;''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).<ref>{{cita libro| last1 =Prusinkiewicz | first1 = Przemyslaw | author1-link = Przemyslaw Prusinkiewicz | author2-link = Aristid Lindenmayer| last2 = Lindenmayer | first2 = Aristid | title = The Algorithmic Beauty of Plants | publisher =Springer-Velag | year= 1990 | pages =101–7 | url = http://algorithmicbotany.org/papers/#webdocs | isbn = 978-0-387-97297-8}}</ref>

=== 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.<ref>{{cita publicación periódica|nome=T. C.|apelidos=Scott|nome2=P.|apelidos2=Marketos| url =http://www-history.mcs.st-andrews.ac.uk/Publications/fibonacci.pdf |título=On the Origin of the Fibonacci Sequence | revista=MacTutor History of Mathematics archive|editorial=University of St Andrews|data=2014|lingua=en}}</ref>

== 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<ref>Vorobiov: Números de Fibonacci, Editorial Mir, Moscú. Esta sección esixe que a sucesión comece con 1 e con 0 (1974)</ref>
* Calquera que sexa o enteiro ''m'', entre os <math>m^2 - 1</math> 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<ref>Vorobiov: Ibídem</ref>
* Se ''k'' é un [[número composto]] diferente de 4, entón o número k-ésimo de Fibonacci é composto.<ref>Vorobiov: Op. cit</ref> 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 ==
{{listaref}}

== Véxase tamén ==
{{Commonscat}}
=== Bibliografía ===
* {{cita libro|apelidos=Kolman|nome=Bernard|apelidos2=Hill|nome2= David R.|título=Álgebra Lineal|ano=2006|editorial=México: PEARSON EDUCACIÓN|id=ISBN 970-26-0696-9}}
* {{cita libro|apelidos=Johnsonbaugh|nome=Richard|título=Matemáticas Discretas|ano=2005|editorial=México: PEARSON EDUCACIÓN|id=ISBN 970-26-0637-3}}
* {{cita libro|apelidos=Brassard|nome=G|apelidos2=Bratley|nome2= P.|título=Fundamentos de Algoritmia|ano=1997|editorial=Madrid: PRETINCE HALL|id=ISBN 84-89660-00-X}}
* {{cita libro|nome=Kenneth H.|apelidos= Rosen|título=Discrete mathematics and its applications|url=https://archive.org/details/discretemathemat0005rose|ano=2003|editorial=McGraw Hill|id=ISBN 0-07-123374-1}}
* {{cita libro|nome=Kenneth H.|apelidos= Rosen|nome2=John G. |apelidos2= Michaels|título=Handbook of discrete and combinatorial mathematics|ano=1999|editorial=CRC|id=ISBN 0-8493-0149-1}}
* {{cita libro|nome=N. N.|apelidos= Vorobiov|título=Números de Fibonacci|ano=1974|editorial=Editorial Mir|lugar= Moscova}}
* {{cita libro|nome=A. I.|apelidos= Markushevich|título=Sucesiones recurrentes|ano=1974; 1981|editorial=Editorial Mir|lugar= Moscova}}
* {{cita libro|apelidos=Pacioli|nome=Luca|título=La Divina Proporción|ano=1946|editorial=Editorial Losada|lugar=Buenos Aires}}
* 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 ===
* [http://books.google.co.ve/books?id=PilhoGJeKBUC&printsec=frontcover&hl=es#v=onepage&q&f=false Fibonacci's Liber Abaci] vista previa en Google Books {{en}}
* [http://www.youtube.com/watch?v=P0tLbl5LrJ8 The Fibonacci Sequence] {{en}}
* [https://www.fq.math.ca/list-of-issues.html The Fibonacci Quarterly]. Publicación trimestral, poden lerse gratuítos todos os números anteriores aos últimos 4 anos.

{{Control de autoridades}}

[[Categoría:Números]]