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, … (čí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. Rekurzivní definice Fibonacciho posloupnosti tedy je:

HistorieEditovat

 
Počet párů králíků podle Fibonacciho posloupnosti.

Fibonacciho posloupnost byla poprvé popsána italským matematikem Leonardem Pisánským (Leonardo z Pisy), známým také jako Fibonacci (cca 11751250), 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íEditovat

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á Lucasova čísla.

Explicitní vyjádřeníEditovat

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čtuEditovat

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

VlastnostiEditovat

 
Fibonacciho čísla jsou součty „mělkých úhlopříček“ Pascalova trojúhelníku. (č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   je Fibonacciho číslo, pokud výraz   nebo   je celé číslo.

VýznamEditovat

 
Zlatý řez.
Podrobnější informace naleznete v článku logaritmická spirála.

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.
Související informace naleznete také v článku Zlatý řez#Zlatý řez v přírodě.

Další posloupnostiEditovat

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

Sekvence vyšších řádůEditovat

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

 

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

Tribonacciho číslaEditovat

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 číslaEditovat

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

RepfigityEditovat

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

OdkazyEditovat

ReferenceEditovat

  1. 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.
  2. Lengyel T., Marques D.: The 2-adic Order of Some Generalized Fibonacci Numbers, INTEGERS, Volume 17 (2017) (anglicky)
  3. KEITH, Mike. Keith Numbers [online]. [cit. 2021-06-08]. Dostupné online. 

Související článkyEditovat

Externí odkazyEditovat