Fibonaĉi-nombro

[eta|La fibonaĉi-nombroj sur fumtubo en [Unna, Germanio]]
La **nombroj de Fibonacci** aŭ **fibonaĉi-nombroj**, estas elementoj de entjerosinsekvo

: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (),

en kiu la du unuaj elementoq estas aŭ 1 kaj 1, aŭ 0 kaj 1. Ili estis nomitaj honore de la itala matematikisto **Leonardo Pisano**, konata kiel Fibonaĉi. Pli formale tiun ĉi sinsekvon \left\{F_n\right\} oni difinas per rikura formulo:

: F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in \Z.

aŭ

:
  F_n := F(n):=
  \begin{cases}
    0             & \mbox{se } n = 0; \\
    1             & \mbox{se } n = 1; \\
    F(n-1)+F(n-2) & \mbox{se } n > 1. \\
   \end{cases}
 

Oni povas ĝeneraligi fibonaĉi-nombroj por negativaj n. Por trovi elementojn ĉe negativaj n oni uzu la renversitan formulon F_n=F_{n+2}-F_{n+1}:

Oni povas facile rimarki ke F_{-n} = (-1)^{n+1}F_n.

eta|400 px|La kvanto da kuniklaj paroj formas la sinsekvon de Fibonaĉi

## Historio 
La sinsekvo estis konata ĉe barataj matematikistoj multe pli antaŭe ol la tempo de Fibonaĉi.

Ekster Barato la sinsekvo aperis en la libro Liber Abaci (1202) fare de Fibonaĉi. Li esploris la kreskadon de ideala (biologie neebla) populacio de kunikloj. En ĉiu paro de tiuj kunikloj ino ekde la dua monato de sia vivo naskas unu plian paron ĉiumonate kaj kunikloj neniam mortas. Do se komence estas unu paro ĵus naskitaj kunikloj, post monato estas ankaŭ unu paro, post du monatoj estas 2 paroj (la unua paro komencas naski), post tri monatoj — 3 paroj, post kvar monatoj — 5 paroj (naskas du paroj) k.t.p. Post *n*-a monato la kvanto da paroj egalas sumon de la kvanto post *(n-1)*-a monato (tiuj paroj jam estis kaj restis plu) kaj la kvanto post *(n-2)*-a monato (tiom da paroj estis naskitaj ĉi-monate).

La nomon “fibonaĉi-nombroj” unuafoje uzis en 19-a jarcento la franca matematikisto Édouard Lucas.

## Rekta (ne rikura) formulo 
Ekzistas formulo por kalkuli nur la n-an Fibonaĉi-nombron ne kalkulante ĉiujn antaŭajn. Oni konas ĝin kiel la **formulo de Binet**, kvankam ĝin pli frue konas Abraham de Moivre:

:f(n) = \frac1{\sqrt 5} \left[ \left(\frac{1+\sqrt 5}2\right)^n - \left(\frac{1-\sqrt 5}2\right)^n \right].

## Ligo kun la triangulo de Pascal 
[eta|360px|La fibonaĉi-nombroj estas la sumoj de elementoj laŭ la ruĝaj strekoj en la [triangulo de Pascal]]
La fibonaĉi-nombroj aperas en la triangulo de Pascal kiel sumoj de ĝiaj elementoj laŭ strekoj, indikitaj sur la bildo dekstre. La sumojn oni povas esprimi tiel:

:F_{n}=\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \tbinom {n-k-1} k

## Ligo kun la Ora proporcio 
Laŭ la formulo de Binet:

: F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}

::\frac{1 + \sqrt{5}}{2} = \varphi \approx 1.6180339887\dots ()

::\frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} = (-\varphi)^{-1} \approx -0.6180339887\cdots;

\varphi estas la ora proporcio; \varphi kaj (-\varphi)^{-1} estas solvoj de la kvadrata ekvacio x^2-x-1=0.

F_n = \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5} = \frac{\varphi^n - (-\varphi )^{-n}}{\varphi - (-\varphi )^{-1}} = \frac{\varphi^n-(-\varphi)^{-n}}{2 \varphi - 1}

### Rondiga kalkulado 
Ĉar \left|\frac{(-\varphi)^{-n}}{\sqrt 5}\right|  por ĉiu n>0, do \frac{\varphi^n}{\sqrt 5} estas la plej proksima entjero por F_n:

:F_n=\left[\frac{\varphi^n}{\sqrt 5}\right],\ n \geq 0,

aŭ, uzante la plankan funkcion:

:F_n=\left\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\right\rfloor,\ n \geq 0.

Sciante, ke F estas fibonaĉi-nombro oni povas trovi ĝian numeron:

:n(F) = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2}\right) \bigg\rfloor

[dekstra|eta|La spiralo de Fibonaĉi proksimumas al la [ora spiralo]]

### Limeso de kvociento de fibonaĉi-nombroj 
Johano Keplero trovis, ke ekzistas limeso de kvociento de (n+1)-a fibonaĉi-nombro per la n-a, kaj tiu limeso estas \varphi.

:\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi

Eblas ĝeneraligi tiun ĉi formulon:

:\lim_{n\to\infty}\frac{F_{n+\alpha}}{F_n}=\varphi^\alpha

### Potencoj de la ora proporcio 
Estas vera la sekva egalaĵo:

:\varphi^2 = \varphi + 1,

Uzante ĝin kiel la bazon por indukto oni povas pruvi, ke

:\varphi^n = F_n\varphi + F_{n-1}.

Vidu la sekvantan demonstron por *n* ≥ 1:
:\varphi^{n+1} = (F_n\varphi + F_{n-1})\varphi = F_n\varphi^2 + F_{n-1}\varphi = F_n(\varphi+1) + F_{n-1}\varphi = (F_n + F_{n-1})\varphi + F_n = F_{n+1}\varphi + F_n.

## Identaĵoj 
**1).** \sum_{k=1}^n F_k = F_{n+2}-1.

{{Kaŝskatolo
 |titolo=Pruvo
 |enteno=Ni pruvu laŭ indukto:

**La bazo de la indukto**

:\sum_{k=1}^1 F_k = F_1 = 1= 2-1 = F_{1+2}-1.

**La paso de la indukto**

Se estas vere ke:

:\sum_{k=1}^{n-1} F_k = F_{n+1}-1,

Do

:\sum_{k=1}^n F_k = \sum_{k=1}^{n-1} F_k + F_n = F_{n+1}-1 + F_n = F_{n+2}-1.

}}

Same per indukto oni povas facile pruvi la tri sekvajn identaĵojn:

**2).** \sum_{k=1}^n F_{2k-1} = F_{2n};

eta|300px|dekstra|Ilustraĵo de la formulo **4**

**3).** \sum_{k=1}^n F_{2k} = F_{2n+1}-1;

**4).** \sum_{k=1}^n F_k^2 = F_{n+1}F_n.

La lastan identaĵon oni povas ilustri, tranĉante la ortangulon kun lateroj je F_n kaj F_{n+1} en kvadratojn kun lateroj je F_n, F_{n+1}, \cdots , F_1 (vidu la bildon dekstre).

### La identaĵoj de Cassini kaj de Catalan 
La identaĵo de Cassini deklaras ke:

**5.)** F_n^2 - F_{n+1}F_{n-1} = (-1)^{n-1}

Ĝia ĝeneraligo estas identaĵo de Catalan:

**6.)** F_n^2 - F_{n+r}F_{n-r} = (-1)^{n-r}F_r^2

### Aliaj 
**7).** F_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n}

**8).** F_{2n} = F_{n+1}^2 - F_{n-1}^2 = F_n \left (F_{n+1}+F_{n-1} \right )

**9).** F_{3n+1} = F_{n+1}^3 + 3 F_{n+1}F_n^2 - F_n^3

**10).** F_{3n+2} = F_{n+1}^3 + 3 F_{n+1}^2F_n + F_n^3

**11).** F_{4n} = 4F_nF_{n+1} \left (F_{n+1}^2 + 2F_n^2 \right ) - 3F_n^2 \left (F_n^2 + 2F_{n+1}^2 \right )

Pli ĝenerala:

**12).** F_{kn+c} = \sum_{i=0}^k {k\choose i} F_{c-i} F_n^i F_{n+1}^{k-i}.
----
**13).** \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n   & F_{n-1} \end{pmatrix}

Se oni kalkulos la determinantojn do oni ricevos la identaĵon de Cassini.
----
**14).** F_{n+1}=\frac {F_n+\sqrt{5F_n^2+4(-1)^n}}{2}

## Ĝeneraligoj 
Ekzistas multaj ĝeneraligoj de fibonaĉi-nombroj:

* Por negativaj n — “negafibonaĉi”.
* Ĝeneraligoj por reeloj kaj kompleksaj nombroj. Por tio oni uzas oran proporcion kaj modifitan formulon de Binet.
* Starto de aliaj entjeroj. Ekzemple, la nombroj de Lucas (): L_0= 2, L_1=1, L_n=L_{n-1}+L_{n-2}.
* La sekvantan nombron oni kalkulas el du antaŭaj per iu lineara formulo. Ekzemple, nombroj de Pell (): P_0=0, P_1=1, P_n=2P_{n-1}+P_{n-2}.
* Por kalkuli la sekvantan nombron oni adicias nombrojn ne tuj antaŭajn. Ekzemple, la sinsekvo de Padovan (): P(0)= P(1)=P(2)=1, P(n)=P(n-2)+P(n-3).
* Por kalkuli la sekvantan nombron oni adicias la 3 antaŭajn nombrojn (tribonaĉi-nombroj: ), la 4 antaŭajn nombrojn k.t.p.
* Oni konsideras sinsekvon de iuj objektoj (ne entjeroj), kiu formiĝas per reguloj similaj al fobonaĉaj. Ekzemple, fibonaĉi-polinomoj:
:F_n(x)=\left\{\begin{matrix}
1,\qquad\qquad\qquad\qquad&\mbox{se }n=1;\\
x,\qquad\qquad\qquad\qquad&\mbox{se }n=2;\\
x \cdot F_{n-1}(x)+F_{n-2}(x),&\mbox{se }n\ge3.
\end{matrix}\right.

## Vidu ankaŭ 
* Teoremo de Carmichael pri primaj faktoroj.
* Fibonaĉi-poemo
* Fibonaĉi-polinomoj
* Logaritma spiralo
* Penrosa kahelaro
* Sistemo L

## Eksteraj ligiloj 
* Listo de 300 unuaj fibonaĉi-nombroj (angle).

## Referencoj 
Kategorio:Entjeraj vicoj
Kategorio:Teoria biologio
Nombro