Fibonacciho posloupnost

Historie

Počet párů králíků podle Fibonacciho posloupnosti. +more 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 Fn pro n = 0, 1, 2, . , 20: Surrey má prvních 300 Fn faktorovaných na prvočísla a odkazuje na podrobnější tabulky. +more :

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

Zobecnění

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. +more 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.

Explicitní vyjádření

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. +more 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: :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) ≈ φ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.

Algoritmy výpočtu

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: :\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í.

Vlastnosti

Pascalova trojúhelníku. +more (červeně zvýrazněných) * 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 x je Fibonacciho číslo, pokud výraz \sqrt{5x^2+4} nebo \sqrt{5x^2-4} je celé číslo.

Význam

Zlatý řez.

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

Fibonacciho posloupnost je „manifestována“ přírodou, a to jak v říši živočišné tak rostlinné. Objevuje se např. +more: * 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.

Soubor:Helianthus_whorl. jpg|Uspořádání řad semínek v květu slunečnice. +more Soubor:Fibonacci_spiral_34. svg|Fibonacciho „zlatá“ spirála, připomínající ulitu. Soubor:Valvata_sincera_shell_basal. jpg|Ulita Valvata sincera. Soubor:Schraubenziege_-_Markhor. jpg|koza šrouborohá.

Další posloupnosti

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

Sekvence vyšších řádů

Fibonacciho sekvence vyšších (k-tých) řádů lze definovat jako: :T_{n}(k) = T_{n-1} + T_{n-2} + \ldots + T_{n-k}

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

Tribonacciho čísla

Tribonacciho číslo (Fibonacciho sekvence 3. řádu) je definováno jako součet tří předchozích členů posloupnosti. +more 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 čísla

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, …

Repfigity

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. Např. +more čí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, ….

Odkazy

Reference

Související články

Rekurze * Fibonacciho slovo * Fibonoriál

Externí odkazy

[url=http://mathworld. wolfram. +morecom/FibonacciNumber. html]Fibonacciho posloupnost v encyklopedii Mathworld[/url] (anglicky) * [url=http://www. research. att. com/cgi-bin/access. cgi/as/njas/sequences/eisA. cgi. Anum=A007629]Repfigity v katalogu celočíselných posloupností (A007629)[/url] * OEIS - On-Line Encyclopedia of Integer Sequences: ** [url=http://oeis. org/A000045]A000045[/url] - Fibonacci numbers ** [url=http://oeis. org/A000073]A000073[/url] - Tribonacci numbers ** [url=http://oeis. org/A000078]A000078[/url] - Tetranacci numbers ** [url=http://oeis. org/A007629]A007629[/url] - Repfigit (REPetitive FIbonacci-like diGIT) numbers (or Keith numbers). (Formerly M4922).

Kategorie:Celočíselné posloupnosti