Nombre de Fibonacci

En matemàtiques, els nombres de Fibonacci, sovint denotats F_n, formen una sèrie, anomenada successió de Fibonacci, tal que cada nombre de la sèrie és la suma dels dos nombres anteriors, prenent com a valors inicials de la sèrie 0 i 1. És a dir,^[1] $${\displaystyle F_{0}=0,\quad F_{1}=1,}$$ i $${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$ per n > 1.

La seqüència comença:^[2] $${\displaystyle 0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots }$$

Si se segueixen definicions més antigues, el valor ${\displaystyle F_{0}=0}$ és omès. Així doncs, la seqüència comença amb ${\displaystyle F_{1}=F_{2}=1,}$ i la relació de recurrència ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ és vàlida per n > 2.^[3][4] En la seva definició original, Fibonacci començava la seqüència amb ${\displaystyle F_{1}=1,F_{2}=2}$^[5]

Els nombres de Fibonacci estan estretament relacionats amb la secció àuria: la fórmula de Binet expressa l'nèssim nombre de Fibonacci en termes de n i la secció àuria, i implica que la raó de dos nombres consecutius de Fibonacci tendeix a la secció àuria a mesura que n augmenta.

Els nombres de Fibonacci duen el nom del matemàtic italià Leonardo de Pisa, posteriorment conegut com Fibonacci. En el seu llibre de 1202 Liber Abaci, Fibonacci va introduir la sèrie a les matemàtiques europees occidentals,^[6] tot i que la seqüència ja havia estat descrita prèviament a l'Índia,^[7][8][9] al voltant de l'any 200 abans de Crist en una obra de Pingala quan enumerava possibles patrons en la poesia en sànscrit formats per síl·labes de dues longituds diferents.

Els nombres de Fibonacci apareixen de forma inesperada en les matemàtiques, fins a tal punt que hi ha un revista sencera dedicada al seu estudi, la Fibonacci Quarterly. Les aplicacions dels nombres de Fibonacci inclouen algorismes computacionals com la tècnica de cerca de Fibonacci i l'estructura de dades del monticle de Fibonacci, i grafs anomenats cubs de Fibonacci, que serveixen per interconnectar sistemes paral·lels i distribuïts.

També apareixen en patrons de la natura, com ara en el brancatge dels arbres, la distribució de les fulles del tronc, els brots de fruits en les pinyes, la floració de les carxoferes, l'obertura de les falgueres, i la distribució de les bràctees de les pinyes.

Els nombres de Fibonacci també estan molt relacionats amb els nombres de Lucas ${\displaystyle L_{n}}$, en el sentit que els nombres de Fibonacci i els de Lucas formen una parella completa de sèries de Lucas: ${\displaystyle U_{n}(1,-1)=F_{n}}$ and ${\displaystyle V_{n}(1,-1)=L_{n}}$.

La sèrie de Fibonacci apareix en les matemàtiques a l'Índia en relació al prosòdia en sànscrit, tal com va assenyalar Parmanand Singh l'any 1986.^[8][10][11] En la tradició poètica en sànscrit, era interessant enumerar tots els patrons de síl·labes llarges (L) de 2 unitats de duració, juxtaposades amb les síl·labes curtes (C) d'1 unitat de durada. El recompte dels diferents patrons d'L i d'S successius d'una durada total fixa dona lloc als nombres de Fibonacci: el nombre de patrons de durada m unitats és F_{m + 1}.^[9]

Hi ha consciència per primer cop del coneixement de la sèrie de Fibonacci en l'obra de Pingala (circa  450 –200 aC). Singh va citar la críptica fórmula de Pingala coneguda com misrau cha ("les dues es barregen") i els acadèmics van interpretar-ho en aquest context com: el nombre de patrons d'm blocs (F_m+1) s'obté afegint una [C] als F_m casos i una [L] als F_m−1 casos.^[12] Bharata Muni també va demostrar conèixer la sèrie a Natya Shastra (c. 100 aC–c. 350 dC).^[13][7] Tanmateix, l'exposició més clara de la seqüència es troba en l'obra de Virahanka (c. 700 dC), l'obra del qual es va perdre però es pot trobar en una citació de Gopala (c. 1135):^[11]

Variacions de dos metres anteriors [és la variació]... Per exemple, per [un metre de longitud] quatre, variacions de metres de dos [i] tres són sumats, apareix el cinc. [calcula els exemples de 8, 13, 21]... D'aquesta manera, s'hauria de seguir el procés en totes les mātrā-vṛttas [combinacions prosòdiques].^[a]

Hemachandra (al voltant de  1150) és també considerat sabedor de la seqüència,^[7] ne escriure que "la suma entre l'anterior i el d'abans és el nombre ... del següent mātrā-vṛtta."^[15][16]

Fora de l'Índia, la seqüència de Fibonacci va aparèixer per primer cop al Liber Abaci (El Llibre del Càlcul, 1202) de Fibonacci^[6][17] on s'utilitzava per calcular el creixement en la població de conills.^[18][19] Fibonacci va considerar el creixement d'una població de conills ideal (biològicament poc realista), assumint que: una parella de cries de conill nounada es posen en un camp; cada parella de cries s'aparella a l'edat d'un mes, i al final del segon mes sempre produeixen una altra parella de conills; i els conills mai no moren, sinó que continuen criant per sempre. Fibonacci va proposar aquest enigma: quantes parelles hi haurà en un any?

• Al final del primer mes, s'aparellen, però hi segueix havent només una parella.
• Al final del segon mes produeixen una nova parella, així doncs hi ha 2 parelles en el camp.
• Al final del tercer mes, la parella original produeix una segona parella, però la segona parella simplement s'aparellen sense criar, així doncs hi ha 3 parelles en total.
• Al final del quart mes, la parella original ha produït una altra parella, i la parella que va néixer fa dos mesos produeixen la seva primera parella, fent-ne un total de cinc.

Al final del mes n-èssim, el nombre de parelles de conills és igual al nombre de parelles madures (és a dir, el nombre de parelles en el mes n – 2) més el nombre de parelles vives el mes anterior (el mes n – 1). El nombre en el mes n-èssim és l'n-èssim nombre de Fibonacci.^[20]

El terme "seqüència de Fibonacci" va ser utilitzat per primer cop pel teòric de nombres del segle xix Édouard Lucas.^[21]

Els primers 21 nombres de Fibonacci F_n són:^[2]

F0	F1	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F9	F10	F11	F₁₂	F13	F14	F15	F16	F17	F18	F19	F20
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765

La sèrie pot ser estesa a índexos negatius n utilitzant la relació de recurrència reordenada

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

que dona lloc a la sèrie de nombres "negafibonacci" ^[22] que satisfan $${\displaystyle F_{-n}=(-1)^{n+1}F_{n}.}$$

Així doncs, la sèrie bidireccional queda

F−8

F−7

F−6

F−5

F−4

F−3

F−2

F−1

F0

F1

F₂

F₃

F₄

F₅

F₆

F₇

F₈

−21

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8

13

21

Com tota seqüència definida a partir d'una recurrència lineal amb coeficients constants, els nombres de Fibonacci tenen una expressió en forma tancada. Ha estat coneguda com la fórmula de Binet, pel matemàtic francès Jacques Philippe Marie Binet, tot i que ja era coneguda per Abraham de Moivre i Daniel Bernoulli:^[23]

$${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}},}$$ on $${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\ldots }$$ és la secció àuria (successió A001622 a l'OEIS), i^[24] $${\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\ldots .}$$

Com que ${\displaystyle \psi =-\varphi ^{-1}}$, aquesta fórmula també pot ser escrita com $${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}.}$$ Per veure-ho,^[25] noti's quw φ i ψ són totes dues solucions de les equacions $${\displaystyle x^{2}=x+1\quad {\text{and}}\quad x^{n}=x^{n-1}+x^{n-2},}$$ així doncs, les potències de φ i ψ satisfan la recursió de Fibonacci. En altres paraules, $${\displaystyle \varphi ^{n}=\varphi ^{n-1}+\varphi ^{n-2}}$$ i $${\displaystyle \psi ^{n}=\psi ^{n-1}+\psi ^{n-2}.}$$

Segueix que per valors qualssevol de a i de b, la seqüència definida per $${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$ satisfà la mateixa recurrència. $${\displaystyle U_{n-1}+U_{n-2}=a\varphi ^{n-1}+b\psi ^{n-1}+a\varphi ^{n-2}+b\psi ^{n-2}=a\varphi ^{n-1}+a\varphi ^{n-2}+b\psi ^{n-1}+b\psi ^{n-2}=U_{n}}$$

Si a i b són triats tals que U₀ = 0 i U₁ = 1 llavors la seqüència resultant U_n ha de ser una seqüència de Fibonacci. Això és el mateix que imposar que a i b satisfacin el sistema d'equacions: $${\displaystyle \left\{{\begin{array}{l}a+b=0\\\varphi a+\psi b=1\end{array}}\right.}$$ amb solució $${\displaystyle a={\frac {1}{\varphi -\psi }}={\frac {1}{\sqrt {5}}},\quad b=-a,}$$ que produeix la fórmula imposada.

Prenent com a valors inicials U₀ i U₁ constants arbitràries, una solució més general és: $${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$ on $${\displaystyle a={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}}}$$ $${\displaystyle b={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.}$$

Com que $${\displaystyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$$

per tot n ≥ 0, el nombre F_n és l'enter més proper a ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$. Per tant, es pot trobar arrodoniment, utilitzant la funció de l'enter més proper: $${\displaystyle F_{n}=\left[{\frac {\varphi ^{n}}{\sqrt {5}}}\right],\ n\geq 0.}$$

De fet, l'error d'arrodoniment és molt petit, menys de 0.1 per n ≥ 4, i més de 0.01 per n ≥ 8.

També es poden calcular els nombres de Fibonacci mitjançant el truncament, en termes de la funció terra: $${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor ,\ n\geq 0.}$$

Com que la funció terra és monòtona, es pot invertir aquesta darrera fórmula per trobar l'índex n(F) del major nombre de Fibonacci que no és més gran que un nombre real F > 1: $${\displaystyle n(F)=\left\lfloor \log _{\varphi }\left(F\cdot {\sqrt {5}}+{\frac {1}{2}}\right)\right\rfloor ,}$$ on ${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi ).}$

Johannes Kepler va observar que la raó entre nombres consecutius de Fibonacci convergeix. Va escriure que "el que 5 és a 8 és, pràcticament, el que 8 és a 13, i el que 8 és a 13, és el que 13 és a 21 gairebé", i va concloure que aquestes raons tendeixen a la secció àuria ${\displaystyle \varphi \colon }$^[26][27] $${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$$

Aquesta convergència funciona independentment dels valors inicials, exceptuant el cas trivial de 0,0, o qualsevol parella en la secció àuria conjugada, ${\displaystyle -1/\varphi .}$ Això es pot verificar usant la fórmula de Binet. Per exemple, els valors inicials de 3 i 2 generen la seqüència 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... La raó de termes consecutius en aquesta seqüència mostra la mateixa convergència cap a la secció àuria.

Com que la secció àuria satisfà l'equació $${\displaystyle \varphi ^{2}=\varphi +1,}$$

es pot utilitzar aquesta expressió per descompondre potències més elevades ${\displaystyle \varphi ^{n}}$ com a funció lineal de potència més baixes, que alhora poden ser descomposades successivament fins a obtenir una combinació lineal de ${\displaystyle \varphi }$ i 1. La relació de recurrència resultant acaben tenint nombres de Fibonacci com a coeficinets lineals: $${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$ Es pot demostrar aquesta equació mitjançant inducció en n.

Aquesta expressió és també vàlida per n < 1 si s'esté la seqüència de Fibonacci F_n als enters negatius, utilitzant la relació de Fibonacci ${\displaystyle F_{n}=F_{n-1}+F_{n-2}.}$

Un sistema de dues dimensions d'equacions de diferència que descriu la seqüència de Fibonacci és

$${\displaystyle {F_{k+2} \choose F_{k+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{k+1} \choose F_{k}}}$$ denotat, alternativament, com $${\displaystyle {\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},}$$

que implica ${\displaystyle {\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}}$. Els valors propis de la matriu A són ${\displaystyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$ i ${\displaystyle -\varphi ^{-1}={\frac {1}{2}}(1-{\sqrt {5}})}$ que corresponen als vectors propis $${\displaystyle {\vec {\mu }}={\varphi \choose 1}}$$ i $${\displaystyle {\vec {\nu }}={-\varphi ^{-1} \choose 1}.}$$ Com que els valors inicials són $${\displaystyle {\vec {F}}_{0}={1 \choose 0}={\frac {1}{\sqrt {5}}}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}{\vec {\nu }},}$$ es té que el terme n-èssim és $${\displaystyle {\begin{aligned}{\vec {F}}_{n}&={\frac {1}{\sqrt {5}}}A^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}A^{n}{\vec {\nu }}\\&={\frac {1}{\sqrt {5}}}\varphi ^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}(-\varphi )^{-n}{\vec {\nu }}~\\&={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{n}{\varphi \choose 1}-{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{n}{-\varphi ^{-1} \choose 1},\end{aligned}}}$$ D'aquesta expressió, es pot concloure que l'element n-èssim de la sèrie de Fibonacci pot ser obtingut de manera directa a partir de l'expressió en forma tancada: $${\displaystyle F_{n}={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{n}-{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{n}.}$$

De manera equivalent, es pot fer el mateix càlcul diagonalitzant A a partir de l'ús de la seva descomposició en valors propis: $${\displaystyle {\begin{aligned}A&=S\Lambda S^{-1},\\A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}}$$ on ${\displaystyle \Lambda ={\begin{pmatrix}\varphi &0\\0&-\varphi ^{-1}\end{pmatrix}}}$ i ${\displaystyle S={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}.}$ L'expressió en forma tancada de l'element n-èssim de la sèrie de Fibonacci ve, doncs, donat per

$${\displaystyle {\begin{aligned}{F_{n+1} \choose F_{n}}&=A^{n}{F_{1} \choose F_{0}}\\&=S\Lambda ^{n}S^{-1}{F_{1} \choose F_{0}}\\&=S{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}S^{-1}{F_{1} \choose F_{0}}\\&={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}{\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&\varphi ^{-1}\\-1&\varphi \end{pmatrix}}{1 \choose 0},\end{aligned}}}$$

que implica, com abans, $${\displaystyle F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.}$$

La matriu A té determinant de −1, i per tant és una matriu unimodular 2×2.

Es pot entendre aquesta propietat en termes de la representació en fracció contínua de la secció àuria:

$${\displaystyle \varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\ddots }}}}}}.}$$

Els nombres de Fibonacci apareixen a mesura que la raó de convergents successius de la fracció contínua de φ, i la matriu formada a partir del convergents successius de qualsevol fracció contínua té un determinant de +1 o −1. La representació matricial dona la següent expressió en forma tancada dels nombres de Fibonacci:

$${\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}$$

Prenent el determinant en ambdós costats de l'equació, s'obté la identitat de Cassini, $${\displaystyle (-1)^{n}=F_{n+1}F_{n-1}-F_{n}^{2}.}$$

A més, com que Aⁿ A^m = A^n+m per qualsevol matriu quadrada A, es poden derivar les següents identitats (s'obtenen a partir de dos coeficients diferents del producte matricial, i es pot deduir fàcilment la segona a partir de la primera canviant n per n + 1), $${\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.\end{aligned}}}$$

En particular, amb m = n, $${\displaystyle {\begin{aligned}F_{2n-1}&=F_{n}^{2}+F_{n-1}^{2}\\F_{2n}&=(F_{n-1}+F_{n+1})F_{n}\\&=(2F_{n-1}+F_{n})F_{n}\\&=(2F_{n+1}-F_{n})F_{n}.\end{aligned}}}$$

Aquestes últimes dues identitats proporcionen un mètode per calcular els nombres de Fibonacci recursivament en O(log(n)) operacions aritmètiques i en temps O(M(n) log(n)), on M(n) és el temps que es triga a multiplicar dos nombres d'n dígits. Això coincideix amb el temps de calcular l'n-éssim nombre de Fibonacci a partir de la fórmula matricial en forma tancada, però amb menys passos redundants si s'evita tornar a calcular un nombre de Fibonacci que ja s'havia calculat (recursió amb memoització).^[28]

Hom es pot preguntar si un enter positiux és un nombre de Fibonacci. Això és veritat si i només si almenys un dels dos nombres ${\displaystyle 5x^{2}+4}$ i ${\displaystyle 5x^{2}-4}$ és un quadrat perfecte.^[29] Això és perquè es pot reordenar la fórmula de Binet de més amunt fins a tenir

$${\displaystyle n=\log _{\varphi }\left({\frac {F_{n}{\sqrt {5}}+{\sqrt {5F_{n}^{2}\pm 4}}}{2}}\right),}$$

que permet trobar la posició en la seqüència d'un nombre de Fibonacci.

Aquesta fórmula ha de tornar un enter per tot n, així que l'expressió radical ha de ser un enter (altrament, el logaritme ni tan sols retorn un nombre racional).

La majoria de les identitats relacionades amb els nombres de Fibonacci poden ser demostrades a partir d'arguments basats en combinatòria que utilitzen el fet que es pot interpretar F_n com el nombre de seqüències d'1s i 2s que sumen n − 1. Això es pot rendre com la definició de F_n, amb el conveni que F₀ = 0, en el sentit que no hi ha cap suma que dongui −1, i que F₁ = 1, en el sentit que la suma buida "suma" 0. Aquí, l'ordre dels sumands importa. Per exemple, 1 + 2 i 2 + 1 es consideren sumes diferents.

Per exemple, la relació recursiva

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

o, en altres paraules, el nombre de Fibonacci n-èssim és la suma dels dos nombres de Fibonacci previs, es pot mostrar dividint les F_n sumes d'1s i 2s que sumen n − 1 en dos grups que no se solapen. Un dels grups conté les sumes el primer terme dels quals és 1 i l'altre conté les sumes que tenen el 2 com a primer terme. En el primer grup, la resta de termes sumen n − 2, així que hi ha F_n-1 sumes, i en el segon grup la resta de termes sumen n − 3, així doncs hi ha F_n−2 sumes. Així doncs, hi ha un total de F_n−1 + F_n−2 sumes en total, que és igual a F_n.

De manera similar, es pot demostrar que la suma dels primers nombres de Fibonacci fins al terme n-èssim és igual al nombre de Fibonacci (n + 2)-èssim menys u.^[30] En símbols: $${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$$

Això es fa dividint les sumes que donguin n + 1 d'una forma diferent, aquest cop a partir de la ubicació del primer 2. Específicament, el primer grup consisteix en aquelles sumes que comencen amb un 2, el segon grup és el de les sumes que comencen per un 1 + 2, el tercer és 1 + 1 + 2, i així successivament, fins a l'últim grup, que consisteix en l'única suma en què només hi ha 1s. El nombre de sumes en el primer grup és F(n), F(n − 1) en el segon grup, i així successivament, amb 1 suma en l'últim grup. Així doncs, el nombre total de sumes és F(n) + F(n − 1) + ... + F(1) + 1 i per tant aquesta quantitat és igual a F(n + 2).

Un argument similar, agrupant les sumes a partir de la posició del primer 1 enlloc de la posició del primer 2, dona dues més identitats: $${\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}$$ i $${\displaystyle \sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}$$ En paraules, la suma dels primers nombres de Fibonacci d'índex senar fins a F_2n−1 és el nombre de Fibonacci (2n)-èssim, i la suma dels primers nombres de Fibonacci d'índex parell fins a F_2n és el nombre de Fibonacci (2n + 1)-èssim menys  1.^[31]

Es pot utilitzar un truc diferent per demostrar $${\displaystyle \sum _{i=1}^{n}{F_{i}}^{2}=F_{n}F_{n+1},}$$ o en paraules, la suma dels quadrats dels primers nombres de Fibonacci fins a F_n és el producte dels nombres de Fibonacci n-èssim i (n + 1)-èssim. En aquest cas, es pot descompondre un rectangle de Fibonacci de costats F_n i F(n + 1) en quadrats de mida F_n, F_n−1, i així successivament fins a F₁ = 1, pel qual la identitat segueix a partir de comparar les àrees (vegi's la primera figura a dalt de tot de l'article).

També es considera la seqüència ${\displaystyle (F_{n})_{n\in \mathbb {N} }}$ utilitzant el mètode simbòlic.^[32] Més precisament, aquesta seqüència correspon a una classe combinatòria especificable. L'especificació d'aquesta seqüència és ${\displaystyle \operatorname {Seq} ({\mathcal {Z+Z^{2}}})}$. En efecte, com s'ha afrimat més amunt, el nombre de Fibonacci ${\displaystyle n}$-èssim és igual al nombre de composició combinatòria de ${\displaystyle n-1}$ utilitzant els termes 1 i 2.

Segueix que la funció generadora ordinària de la seqüència de Fibonacci, és a dir ${\displaystyle \sum _{i=0}^{\infty }F_{i}z^{i}}$, és la funció complexa ${\displaystyle {\frac {z}{1-z-z^{2}}}}$.

Sovint es poden demostrar fàcilment les identitats de Fibonacci utilitzant la inducció matemàtica.

Per exemple, reconsideri's

${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$

Sumant ${\displaystyle F_{n+1}}$ a tots dos costats de la igualtat

${\displaystyle \sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1}$

es té la fórmula per ${\displaystyle n+1}$

${\displaystyle \sum _{i=1}^{n+1}F_{i}=F_{n+3}-1}$

De manera similar, si se suma ${\displaystyle F_{n+1}^{2}}$ a tots dos costats de la igualtat

${\displaystyle \sum _{i=1}^{n}{F_{i}}^{2}=F_{n}F_{n+1}}$

s'obté

${\displaystyle \sum _{i=1}^{n}{F_{i}}^{2}+F_{n+1}^{2}=F_{n+1}\left(F_{n}+F_{n+1}\right)}$

${\displaystyle \sum _{i=1}^{n+1}{F_{i}}^{2}=F_{n+1}F_{n+2}}$

La fórmula de Binet és

${\displaystyle {\sqrt {5}}F_{n}=\phi ^{n}-\psi ^{n}}$

Això es pot utilitzar per demostrar les identitats de Fibonacci.

Per exemple, per demostrar que ${\displaystyle \textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$

noti's que el costat esquerre de la igualtat multiplicat per ${\displaystyle {\sqrt {5}}}$ es converteix en

${\displaystyle 1+\phi +\phi ^{2}+\dots +\phi ^{n}-\left(1+\psi +\psi ^{2}+\dots +\psi ^{n}\right)}$

${\displaystyle ={\frac {\phi ^{n+1}-1}{\phi -1}}-{\frac {\psi ^{n+1}-1}{\psi -1}}}$

${\displaystyle ={\frac {\phi ^{n+1}-1}{-\psi }}-{\frac {\psi ^{n+1}-1}{-\phi }}}$

${\displaystyle ={\frac {-\phi ^{n+2}+\phi +\psi ^{n+2}-\psi }{\phi \psi }}}$

Com que ${\displaystyle \textstyle \phi \psi =-1}$ i ${\displaystyle \textstyle \phi -\psi ={\sqrt {5}}}$, es té que

${\displaystyle =\phi ^{n+2}-\psi ^{n+2}-(\phi -\psi )}$

${\displaystyle ={\sqrt {5}}(F_{n+2}-1)}$

com es volia.

Es poden derivar diverses altres identitats utilitzant diferents mètodes. Aquí hi ha algunes d'elles:^[33]

La identitat de Cassini afirma que

${\displaystyle F_{n}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}}$

La identitat de Catalan n'és una generalització:

${\displaystyle F_{n}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}F_{r}^{2}}$

Les identitats de d'Ocagne són les següents

${\displaystyle F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}}$

${\displaystyle F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}}$

on L_n és l'n-èssim nombre de Lucas. La segona és una identitat relacionada amb el terme 2n de la successió; altres identitats d'aquest tipus són

${\displaystyle F_{3n}=2F_{n}^{3}+3F_{n}F_{n+1}F_{n-1}=5F_{n}^{3}+3(-1)^{n}F_{n}}$

mitjançant la identitat de Cassini.

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

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

${\displaystyle F_{4n}=4F_{n}F_{n+1}\left(F_{n+1}^{2}+2F_{n}^{2}\right)-3F_{n}^{2}\left(F_{n}^{2}+2F_{n+1}^{2}\right)}$

Aquestes es poden obtenir experimentalment utilitzant reducció de reticle, i són útils per establir un crivell especial del cos de nombres per factoritzar un nombre de Fibonacci.

Més generalment,^[33]

${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c-i}F_{n}^{i}F_{n+1}^{k-i}.}$

o, alternativament,

${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c+i}F_{n}^{i}F_{n-1}^{k-i}.}$

Si es fixa k = 2 en aquesta fórmula, es tornen a obtenir les fórmules del final de la secció de més amunt Forma matricial.

La funció generatriu de la seqüència de Fibonacci és la sèrie de potències

${\displaystyle s(x)=\sum _{k=0}^{\infty }F_{k}x^{k}=\sum _{k=1}^{\infty }F_{k}x^{k}=0+x+x^{2}+2x^{3}+3x^{4}+\dots .}$

Aquesta sèrie és convergent per ${\displaystyle |x|<{\frac {1}{\varphi }},}$ i la seva suma té una forma tancada simple:^[34]

${\displaystyle s(x)={\frac {x}{1-x-x^{2}}}}$

Això es pot demostrar utilitzant la recurrència de Fibonacci expandint cada coeficient en una suma infinita: $${\displaystyle {\begin{aligned}s(x)&=\sum _{k=0}^{\infty }F_{k}x^{k}\\&=F_{0}+F_{1}x+\sum _{k=2}^{\infty }F_{k}x^{k}\\&=F_{0}+F_{1}x+\sum _{k=2}^{\infty }\left(F_{k-1}+F_{k-2}\right)x^{k}\\&=x+\sum _{k=2}^{\infty }F_{k-1}x^{k}+\sum _{k=2}^{\infty }F_{k-2}x^{k}\\&=x+x\sum _{k=2}^{\infty }F_{k-1}x^{k-1}+x^{2}\sum _{k=2}^{\infty }F_{k-2}x^{k-2}\\&=x+x\sum _{k=1}^{\infty }F_{k}x^{k}+x^{2}\sum _{k=0}^{\infty }F_{k}x^{k}\\&=x+xs(x)+x^{2}s(x).\end{aligned}}}$$

Resolent l'equació

${\displaystyle s(x)=x+xs(x)+x^{2}s(x)}$

per s(x) resulta en la forma tancada.

${\displaystyle -s(-{\frac {1}{x}})}$ dona la funció generatriu pels nombres negafibonacci, i ${\displaystyle s(x)}$ satisfà l'equació funcional

${\displaystyle s(x)=s(-{\frac {1}{x}})}$.

La descomposició en fraccions parcials ve donada per

${\displaystyle s(x)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi x}}-{\frac {1}{1-\phi x}}\right)}$

on ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ és la secció àuria i ${\displaystyle \phi ={\frac {1-{\sqrt {5}}}{2}}}$ és el seu conjugat.

• Constant d'Embree-Trefethen
• Nombres de Lucas

• Ball, Keith M. «8: Fibonacci's Rabbits Revisited». A: Strange Curves, Counting Rabbits, and Other Mathematical Explorations. Princeton University Press, 2003. ISBN 978-0-691-11321-0. .
• Beck, Matthias; Geoghegan, Ross. The Art of Proof: Basic Training for Deeper Mathematics. Springer, 2010. ISBN 978-1-4419-7022-0. .
• Bóna, Miklós. A Walk Through Combinatorics. 3rd. World Scientific, 2011. ISBN 978-981-4335-23-2. .
  • Bóna, Miklós. A Walk Through Combinatorics. 4th Revised. World Scientific, 2016. ISBN 978-981-3148-84-0. .
• Lemmermeyer, Franz. Reciprocity Laws: From Euler to Eisenstein. Springer, 2000. ISBN 978-3-540-66957-9. .
• Livio, Mario. The Golden Ratio: The Story of Phi, the World's Most Astonishing Number. First trade paperback. New York City: Broadway Books, 2003. ISBN 0-7679-0816-3. 
• Lucas, Édouard. Théorie des nombres (en francès). 1. Gauthier-Villars, 1891. Théorie des nombres a Google Books. .
• Pisano, Leonardo. Fibonacci's Liber Abaci: A Translation into Modern English of the Book of Calculation. Springer, 2002. ISBN 978-0-387-95419-6.