Fibonacciho posloupnost

Jako Fibonacciho posloupnost je v matematice označována nekonečná posloupnost přirozených čísel, začínající 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … (čísla nacházející se ve Fibonacciho posloupnosti jsou někdy nazývána Fibonacciho čísla), kde každé číslo je součtem dvou předchozích. Rekurentní definice Fibonacciho posloupnosti tedy je:

${\displaystyle F_{n}=\left\{{\begin{matrix}0\,,\qquad \qquad \qquad \quad \,\ \ \,&&{\mbox{pro }}n=0\,;\ \ \\1,\qquad \qquad \qquad \qquad \,&&{\mbox{pro }}n=1;\ \ \,\\F_{n-1}+F_{n-2}&&{\mbox{jinak.}}\end{matrix}}\right.}$

Fibonacciho posloupnost byla poprvé popsána italským matematikem Leonardem Pisánským (Leonardo z Pisy), známým také jako Fibonacci (cca 1175–1250), k popsání růstu populace králíků (za poněkud idealizovaných podmínek). Číslo F(n) popisuje velikost populace po n měsících, pokud předpokládáme, že

• První měsíc se narodí jediný pár.
• Nově narozené páry jsou produktivní od druhého měsíce svého života.
• Každý měsíc zplodí každý produktivní pár jeden další pár.
• Králíci nikdy neumírají, nejsou nemocní atd.

Prvních 21 Fibonacciho čísel F_n pro n = 0, 1, 2, ..., 20:^[1]

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	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

Posloupnost lze obdobně definovat i pro záporná čísla.

Termín Fibonacciho posloupnost je někdy používán i pro jiné posloupnosti, ve kterých platí, že f(n+2) = f(n) + f(n+1). Libovolnou takovou posloupnost lze zapsat jako f(n+2) = aF(n) + bF(n+1), pro nějaké koeficienty a, b, tzn. tyto posloupnosti tvoří vektorový prostor s posloupnostmi F(n) a F(n+1)) jako bází.

Speciální případ takové obecné Fibonacciho posloupnosti s f(1) = 1 a f(2) = 3 se nazývá Lucasovo číslo.

Jak zjistil už Johannes Kepler, rychlost růstu Fibonacciho posloupnosti, tzn. podíl dvou po sobě jdoucích členů F(n+1) / F(n), konverguje k hodnotě zlatého řezu φ = (1+√5) / 2 ≈ 1,618. Pomocí tohoto faktu, techniky generujících funkcí, nebo pomocí řešení rekurentních rovnic lze dospět k následujícímu explicitnímu (nerekurzivnímu) vztahu pro n-tý člen Fibonacciho posloupnosti:

${\displaystyle F\left(n\right)={\varphi ^{n} \over {\sqrt {5}}}-{(1-\varphi )^{n} \over {\sqrt {5}}}}$

Druhý člen této rovnice se s rostoucím n blíží nule, takže asymptotické chování Fibonacciho posloupnosti je dáno prvním členem, takže F(n) ≈ φⁿ / √5, z čehož je zřejmá již zmíněná rychlost růstu. Ve skutečnosti je druhý člen tak malý i pro malá n, že ho lze zcela zanedbat a Fibonacciho čísla získávat prostým zaokrouhlením prvního členu na nejbližší celé číslo.

Výpočet n-tého Fibonacciho čísla přímým dosazením do výše uvedeného explicitního vzorce je sice rychlá metoda, avšak kvůli hromadícím se nepřesnostem při výpočtu za použití čísel s plovoucí řádovou čárkou je pro větší n nepoužitelná.

Přímočará implementace výpočtu podle definice, rekurzivním algoritmem, je extrémně neefektivní. Technicky exponenciální v n.

Nejčastějším způsobem výpočtu je tedy postupný výpočet, ve kterém se začíná s hodnotami F(0) a F(1) a postupně se počítají další členy posloupnosti, přičemž v paměti stačí udržovat hodnotu dvou posledních členů.

Pro velmi vysoké hodnoty n je možno použít následující vzorec, využívající maticové operace:

${\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F\left(n+1\right)&F\left(n\right)\\F\left(n\right)&F\left(n-1\right)\end{bmatrix}}}$

Při použití vhodného algoritmu pro výpočet mocnin se jedná o relativně rychlý postup. Potřebuje logaritmický počet maticových a celočíselných operací.

• F(n+2) = F(n) + F(n+1)
• F(0) + F(1) + … + F(n) = F(n+2) − 1
• F(1) + 2F(2) + 3F(3) + … + nF(n) = nF(n+2) − F(n+3) + 2
• F(n) vyjadřuje počet způsobů, kterým lze vyrobit číslo n−1 jako součet čísel 1 a 2.
• Číslo ${\displaystyle x}$ je Fibonacciho číslo, pokud výraz ${\displaystyle {\sqrt {5x^{2}+4}}}$ nebo ${\displaystyle {\sqrt {5x^{2}-4}}}$ je celé číslo.

Limita poměru dvou následujících čísel Fibonacciho posloupnosti je rovna zlatému řezu.

${\displaystyle \lim _{n\to \infty }{\frac {F(n+1)}{F(n)}}=\varphi }$

Fibonacciho posloupnost je „manifestována“ přírodou, a to jak v říši živočišné, tak rostlinné. Objevuje se např.:

• V semenících slunečnice, kde lze pozorovat jednotlivá semínka uspořádaná do spirál o dvou po sobě jdoucích číslech posloupnosti (na obrázku je to 34 a 55, tedy F(9) a F(10)).
• Zdřevnatělé lístky plodu artyčoku jsou uspořádány do spirál vedoucích dvěma směry, jejichž počet kolem stonku opět tvoří dvě po sobě jdoucí čísla Fibonacciho posloupnosti (typicky 5 a 8, tedy F(5) a F(6)). Obdobně se tato vlastnost objevuje u šišek některých jehličnatých stromů, tam většinou počet spirál tvoří vyšší členy Fibonacciho posloupnosti.
• Fibonacciho posloupnost popisuje genealogii včel, stejně jako složení jejich pohlaví.
• Taktéž velikost sousedních vrstev listů zelí zachovává poměr dvou po sobě jdoucích čísel Fibonacciho posloupnosti.
• Poměr velikostí dvou po sobě jdoucích komůrek ulity některých plžů odpovídá poměru dvou po sobě jdoucích čísel Fibonacciho posloupnosti.
• Obdobný tvar lze najít u rohů některých druhů čeledi turovitých (Bovidae).
• Fibonacciho posloupnost lze najít u celé řady vyšších rostlin, např. v poměru velikostí jejich listů, nebo úhlu, kterým ze stonku vyrůstají.
• Jak v případě ulit mlžů, rohů čeledi turovitých i listů vyšších rostlin pro tento typ růstu platí, že v každém okamžiku růstu je těžiště (v limitním případě) stejné a daná rostlina nebo živočich se změně těžiště nemusí přizpůsobovat.
• U tzv. zlaté spirály, která se taktéž vyskytuje v přírodě, převážně v živočišné říši, platí invariance vůči velikosti (tedy pohled do středu spirály zůstává týž při jakémkoli přiblížení či zvětšení).
• Tyto projevy a zákonitosti Fibonacciho posloupnosti byly známy již starověkým Egypťanům.

• 
  Uspořádání řad semínek v květu slunečnice.
• 
  Fibonacciho „zlatá“ spirála, připomínající ulitu.
• 
  Ulita Valvata sincera.
• 
  koza šrouborohá

V některých oborech se objevují čísla či posloupnosti nějak příbuzná s Fibonacciho posloupností.

Fibonacciho sekvence vyšších (k-tých) řádů lze definovat jako:^[2]

${\displaystyle T_{n}(k)=T_{n-1}+T_{n-2}+\ldots +T_{n-k}}$

(Základní Fibonacciho sekvence je druhého řádu.)

Tribonacciho číslo (Fibonacciho sekvence 3. řádu) je definováno jako součet tří předchozích členů posloupnosti. Začátek posloupnosti:

1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, ...

Tetranacciho číslo (Fibonacciho sekvence 4. řádu) je definováno jako součet čtyř předchozích členů posloupnosti. Začátek posloupnosti:

1, 1, 2, 4, 8, 15, 29, 56, 108, …

Repfigit (repeated Fibonacci-like digit, též Keithovo číslo) je takové celé číslo, které se objevuje v zobecněné Fibonacciho posloupnosti, která začíná jednotlivými číslicemi tohoto čísla.^[3] Např. číslo 47 je repfigit, neboť zobecněná Fibonacciho posloupnost 4, 7, 11, 18, 29, 47, … obsahuje toto číslo. Pro trojciferná čísla se uvažuje Tribonacciho posloupnost atd. Posloupnost Keithových čísel začíná:

14, 19, 28, 47, 61, 75, 197, …

• Rekurze
• Fibonacciho slovo
• Fibonoriál

• Obrázky, zvuky či videa k tématu Fibonacciho posloupnost na Wikimedia Commons
• Fibonacciho posloupnost v encyklopedii Mathworld (anglicky)
• Repfigity v katalogu celočíselných posloupností (A007629)
• OEIS – On-Line Encyclopedia of Integer Sequences:
  • A000045 – Fibonacci numbers (anglicky)
  • A000073 – Tribonacci numbers (anglicky)
  • A000078 – Tetranacci numbers (anglicky)
  • A007629 – Repfigit (REPetitive FIbonacci-like diGIT) numbers (or Keith numbers). (Formerly M4922) (anglicky)