Nombre de Fibonacci

Una tessel·lació de quadrats amb longitud de costat igual als nombres de la successió de Fibonacci: 1, 1, 2, 3, 5, 8, 13 i 21.

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]

L'espiral de Fibonacci: una aproximació de l'espiral àuria creada en dibuixar arcs circulars que connecten els vèrtexs oposats de quadrats que segueixen la tessel·lació de Fibonacci; (vegeu la imatge superior)

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

Història

Article principal: Secció àuria § Història

Tretze (F₇) maneres d'ordenar síl·labes llargues (mostrades com blocs vermells) i curtes (representades amb quadrats grisos) en una cadència de longitud sis. Cinc (F₅) acaben amb una síl·laba llarga i vuit (F₆) ho fan amb una síl·laba curta.

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]

Una pàgina del llibre de Liber Abaci de Fibonacci de la Biblioteca Nacional Central de Florència que mostra (en un requadre vermell) la seqüència de Fibonacci amb la posició en la sèrie etiquetada en nombres llatins i romans i el valor en nombres aràbics.

El nombre de parelles de conills de la seqüència de Fibonacci

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]

Propietats de la seqüència

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

Relació amb la secció àuria

Article principal: Secció àuria

Expressió en forma tancada

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

Càlcul per arrodoniment

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

Límit de quocients consecutius

Tessel·lacions successives del pla i una gràfica de les aproximacions de la secció àuria calculades dividint cada nombre de Fibonacci per l'anterior

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.

Descomposició en potències

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

Forma matricial

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^n 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]

Identificació

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

Identitats combinatòries

Demostracions combinatòries

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

Mètode simbòlic

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

Demostracions per inducció

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

Demostracions de la fórmula de Binet

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.

Altres identitats

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

Identitats de Cassini i Catalan

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

Identitats de d'Ocagne

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.

Funció generatriu

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.

Vegeu també

• Constant d'Embree-Trefethen
• Nombres de Lucas

Notes

1. "Pel quart, variacions de metres del segon [i] del tercer són sumades, dona el cinc. Pel cinquè, variacions dels dos anteriors – el tercer [i] el quart són sumats, s'obté el vuit. D'aquesta manera, pel sis, [variacions] del quatre [i] del cinc són barrejades, donant lloc al tretze. I d'aquesta manera, les variacions de dos metres anteriors que es barregen, set mores [és] trenta-u. Així, s'hauria de seguir aquest procés en totes les mātrā-vṛttas" [14]

Referències

1. Lucas, 1891, p. 3.
2. Plantilla:Cite OEIS
3. Beck i Geoghegan, 2010.
4. Bóna, 2011, p. 180.
5. Leonardo da Pisa. File:Liber abbaci magliab f124r.jpg - Wikimedia Commons (en anglès), 1202. 
6. Pisano, 2002, p. 404–05.
7. Goonatilake, Susantha. Toward a Global Science. Indiana University Press, 1998, p. 126. ISBN 978-0-253-33388-9. 
8. Singh, Parmanand «The So-called Fibonacci numbers in ancient and medieval India». Historia Mathematica, 12, 3, 1985, p. 229–44. DOI: 10.1016/0315-0860(85)90021-7.
9. Knuth, Donald. The Art of Computer Programming. 4. Generating All Trees – History of Combinatorial Generation. Addison–Wesley, 2006, p. 50. ISBN 978-0-321-33570-8. «it was natural to consider the set of all sequences of [L] and [S] that have exactly m beats. ...there are exactly Fm+1 of them. For example the 21 sequences when m = 7 are: [gives list]. In this way Indian prosodists were led to discover the Fibonacci sequence, as we have observed in Section 1.2.8 (from v.1)» 
10. Knuth, Donald. The Art of Computer Programming. 1. Addison Wesley, 1968, p. 100. ISBN 978-81-7758-754-8. «Before Fibonacci wrote his work, the sequence Fn had already been discussed by Indian scholars, who had long been interested in rhythmic patterns... both Gopala (before 1135 AD) and Hemachandra (c. 1150) mentioned the numbers 1,2,3,5,8,13,21 explicitly [see P. Singh Historia Math 12 (1985) 229–44]" p. 100 (3d ed)...» 
11. Livio, 2003, p. 197.
12. Agrawala, VS. Pāṇinikālīna Bhāratavarṣa (Hn.). Varanasi-I: TheChowkhamba Vidyabhawan, 1969. «SadgurushiShya writes that Pingala was a younger brother of Pāṇini [Agrawala 1969, lb]. There is an alternative opinion that he was a maternal uncle of Pāṇini [Vinayasagar 1965, Preface, 121]. ... Agrawala [1969, 463–76], after a careful investigation, in which he considered the views of earlier scholars, has concluded that Pāṇini lived between 480 and 410 BC» 
13. Singh, Parmanand «The So-called Fibonacci Numbers in Ancient and Medieval India». Historia Mathematica. Academic Press, 12, 3, 1985, pàg. 232. Arxivat de l'original el 2019-07-24. DOI: 10.1016/0315-0860(85)90021-7 [Consulta: 13 juliol 2021].
14. Velankar, HD. 'Vṛttajātisamuccaya' of kavi Virahanka. Jodhpur: Rajasthan Oriental Research Institute, 1962, p. 101. 
15. Livio, 2003, p. 197–98.
16. Shah, Jayant «A History of Piṅgala's Combinatorics». Northeastern University, 1991, pàg. 41.
17. «Fibonacci's Liber Abaci (Book of Calculation)», 13-12-2009.
18. Hemenway, Priya. Divine Proportion: Phi In Art, Nature, and Science. Nova York: Sterling, 2005, p. 20–21. ISBN 1-4027-3522-7. 
19. Knott, Dr. Ron. «The Fibonacci Numbers and Golden section in Nature – 1», 25-09-2016.
20. Knott, Ron. «Fibonacci's Rabbits». University of Surrey Faculty of Engineering and Physical Sciences.
21. Gardner, Martin. Mathematical Circus. The Mathematical Association of America, 1996, p. 153. ISBN 978-0-88385-506-5. «It is ironic that Leonardo, who made valuable contributions to mathematics, is remembered today mainly because a 19th-century French number theorist, Édouard Lucas... attached the name Fibonacci to a number sequence that appears in a trivial problem in Liber abaci» 
22. Knuth, Donald. Annual meeting. The Mathematical Association of America, 2008-12-11. «Negafibonacci Numbers and the Hyperbolic Plane» 
23. Weisstein, Eric W., «Binet's Fibonacci Number Formula» a MathWorld (en anglès).
24. Ball, 2003, p. 156.
25. Ball, 2003, p. 155–6.
26. Kepler, Johannes. A New Year Gift: On Hexagonal Snow. Oxford University Press, 1966, p. 92. ISBN 978-0-19-858120-8. 
27. Strena seu de Nive Sexangula, 1611. 
28. Dijkstra, Edsger W. In honour of Fibonacci, 1978. 
29. Gessel, Ira «Fibonacci is a Square». The Fibonacci Quarterly, 10, 4, 10-1972, p. 417–19.
30. Lucas, 1891, p. 4.
31. Vorobiev, Nikolaĭ Nikolaevich; Martin, Mircea. «Chapter 1». A: Fibonacci Numbers. Birkhäuser, 2002, p. 5–6. ISBN 978-3-7643-6135-8. 
32. Flajolet, Philippe; Sedgewick, Robert. Analytic Combinatorics. Cambridge University Press, 2009, p. 42. ISBN 978-0521898065. 
33. Weisstein, Eric W., «Fibonacci Number» a MathWorld (en anglès).
34. Glaister, P «Fibonacci power series». The Mathematical Gazette, 79, 486, 1995, p. 521–25. DOI: 10.2307/3618079.

Obra citada

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