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:
Historie
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/FibonacciRabbit.svg/220px-FibonacciRabbit.svg.png)
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:[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.
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. 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. 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:
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:
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/PascalTriangleFibanacci.svg/360px-PascalTriangleFibanacci.svg.png)
- 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 je Fibonacciho číslo, pokud výraz nebo je celé číslo.
Význam
![](http://upload.wikimedia.org/wikipedia/commons/f/f1/Rechteck_GoldenerSchnitt.gif)
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ř.:
- 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.
-
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:[2]
(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. 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.[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, …
Odkazy
Reference
- ↑ KNOTT, Ron. The first 300 Fibonacci numbers, factored [online]. UK: Surrey, rev. 3rd April 2011 [cit. 2019-03-23]. Kapitola Fib table. Dostupné online. (anglicky) Surrey má prvních 300 Fn faktorovaných na prvočísla a odkazuje na podrobnější tabulky.
- ↑ Lengyel T., Marques D.: The 2-adic Order of Some Generalized Fibonacci Numbers, INTEGERS, Volume 17 (2017) (anglicky)
- ↑ KEITH, Mike. Keith Numbers [online]. [cit. 2021-06-08]. Dostupné online.
Související články
Externí odkazy
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)