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:

Historie

Fibonacciho posloupnost byla poprvé popsána italským matematikem Leonardem Pisano (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.

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) = 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í

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,62. 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) ≈ φⁿ / √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 v 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í.

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.

Vlastnosti

• F(n+1) = 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.

Další posloupnosti

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

  Tribonacciho čísla

Tribonacciho číslo je definováno jako součet tří předchozích členů posloupnosti. Začátek posloupnosti:

1, 1, 2, 4, 7, 13, 24, 44, 81, …

  Tetranacciho čísla

Tetranacciho číslo 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 Fibonnaci-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ř. číslo 47 je repfigit, neboť 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, …