Kalkulačka Fibonacciho posloupnosti

Počínaje 1, 1 je každé následující číslo součtem předchozích dvou.

Tváří to slavnou posloupnost: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Jak Fibonacciho čísla rostou, poměr mezi po sobě jdoucími členy se blíží zlatému řezu φ ≈ 1,618.

Tento poměr se objevuje v přírodě, umění i architektuře.

Fibonacciho číslo je jakýkoli člen posloupnosti, kde každá hodnota se rovná součtu dvou předchozích, začínajících 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Pravidlo je F(n) = F(n-1) + F(n-2) s počátečními hodnotami F(1) = F(2) = 1.

Pojmenovaná po italském matematikovi 13. století Leonardu Pisánském, známém jako Fibonacci, byla posloupnost zpopularizována v jeho knize Liber Abaci z roku 1202 prostřednictvím úlohy o populaci králíků.

Jak uvádí Wolfram MathWorld, jde o jednu z nejprostudovanějších celočíselných posloupností v matematice, vedenou v OEIS jako posloupnost A000045.

Chcete-li najít n-té Fibonacciho číslo přímo bez vypisování každého předchozího členu, použijte Binetův vzorec: F(n) = (φⁿ − ψⁿ) / √5, kde φ = (1 + √5)/2 ≈ 1,6180339887 je zlatý řez a ψ = (1 − √5)/2 ≈ −0,6180339887.

Protože |ψ| je menší než 1, ψⁿ se zmenšuje k nule, takže F(n) je jednoduše nejbližší celé číslo k φⁿ/√5. Například φ¹⁰/√5 ≈ 55,004, což se zaokrouhlí na F(10) = 55.

Digitální knihovna matematických funkcí (DLMF) od NIST dokumentuje tento uzavřený tvar spolu s příbuznými identitami Lucasových čísel.

10. Fibonacciho číslo je 55, pokud je posloupnost indexována od F(1) = 1. Když budeme členy počítat za sebou, dostaneme 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, takže desátá hodnota je 55.

Na indexování záleží: některé zdroje, včetně částí katalogu OEIS, začínají u F(0) = 0, což posune každou pozici o jedna a desátá uvedená hodnota by pak byla 34.

Tato kalkulačka používá běžnou konvenci začínající jedničkou F(1) = F(2) = 1. Než začnete porovnávat výsledky, vždy si ověřte, zda zdroj počítá od F(0) nebo od F(1).

Kladné celé číslo N je Fibonacciho číslem právě tehdy, když 5N² + 4 nebo 5N² − 4 je druhou mocninou. Tento test vychází z algebraické struktury stojící za Binetovým vzorcem a umožňuje ověřit příslušnost k posloupnosti, aniž byste museli generovat všechny předchozí členy.

Vezměme si N = 13: 5 × 13² − 4 = 5 × 169 − 4 = 841 = 29², což je druhá mocnina, takže 13 je Fibonacciho číslo.

Naproti tomu N = 20 neprojde ani jedním testem (5 × 400 + 4 = 2004 a 5 × 400 − 4 = 1996 nejsou druhé mocniny), takže 20 není Fibonacciho číslo.

Khan Academy se věnuje úvahám o druhých mocninách, které tuto identitu podkládají.

Součet prvních n Fibonacciho čísel se rovná F(n+2) − 1, což je šikovná identita, která šetří sčítání členů po jednom. Pro prvních 10 čísel platí 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143, což odpovídá F(12) − 1 = 144 − 1 = 143.

Stojí za to znát i dvě související identity:

• součet prvních n členů s lichým indexem se rovná F(2n)
• součet čtverců F(1)² + … + F(n)² se rovná F(n) × F(n+1)

Wolfram MathWorld uvádí tyto vzorce pro součty mezi klasickými výsledky v uzavřeném tvaru pro tuto posloupnost.

Poměr po sobě jdoucích Fibonacciho čísel konverguje s rostoucími členy k zlatému řezu φ ≈ 1,6180339887. První poměry oscilují kolem φ: 55/34 ≈ 1,6176 a 89/55 ≈ 1,6182, přičemž s každým krokem se zpřesňují.

K tomu dochází proto, že Binetův vzorec činí z φⁿ dominantní člen. Podle Encyclopaedia Britannica splňuje φ rovnici φ² = φ + 1, takže φ ≈ 1,618 a jeho převrácená hodnota 1/φ ≈ 0.618 se liší přesně o 1.

Stejná konstanta se objevuje v úhlopříčkách pětiúhelníku a v logaritmických spirálách, což je důvod, proč se poměry Fibonacciho čísel opakují napříč geometrií a designem.

Fibonacciho čísla se objevují v mnohem větším množství oblastí než jen v učebnicích.

• V přírodě se semena slunečnic, šupiny šišek a ulity loděnky uspořádávají do spirál souvisejících s Fibonacciho čísly, které zajišťují efektivní uspořádání, což je jev zdokumentovaný v Encyclopaedia Britannica.
• V informatice slouží k benchmarkingu rekurze a dynamického programování – podobně jako to u jiné klasické rekurzivní definice dělá kalkulačka faktoriálu – a objevují se ve Fibonacciho haldách a vyhledávacích algoritmenech.
• V oblasti financí používají obchodníci úrovně Fibonacciho retracementu (23,6 %, 38,2 %, 61,8 %) odvozené z poměrů této posloupnosti.
• Agilní softwarové týmy dokonce používají stupnici ve Fibonacciho stylu (1, 2, 3, 5, 8, 13) pro odhadování náročnosti úkolů (tzv. story points), protože se v ní rostoucí mezery odrážejí ve větší nejistotě u rozsáhlejších úkolů.

Lidi často zaskočí několik běžných chyb:

• Nejčastějším omylem je zmatek v indexování: míchání konvence F(0) = 0 s konvencí F(1) = 1 posune každý člen o jednu pozici a vede k výsledkům, které jsou vedle o jeden krok.
• Druhým úskalím je spoléhání se na Binetův vzorec pro velmi velká n na běžné kalkulačce, kde zaokrouhlování s plovoucí řádovou čárkou může poskytnout špatné nejbližší celé číslo; iterativní sčítání nebo aritmetika s velkými celými čísly zůstává přesná.
• Jiní nesprávně předpokládají, že každé velké číslo je Fibonacciho, aniž by použili test s druhou mocninou 5N² ± 4, nebo zapomínají, že jednička se na začátku objevuje dvakrát.
• Nakonec pamatujte, že v tomto nástroji neexistuje žádný záporný index, který by vedl na člen pod F(1).

Fibonacciho čísla patří do širší rodiny rekurzí druhého řádu, které sdílejí pravidlo člen = předchozí + předpředchozí, ale používají jiné počáteční hodnoty.

Lucasova čísla začínají hodnotami 2, 1, 3, 4, 7, 11, 18 a jsou v katalogu OEIS vedena jako posloupnost A000032; splňují vztah L(n) = φⁿ + ψⁿ a jsou úzce spjata s Fibonacciho čísly prostřednictvím identit, jako je F(2n) = F(n) × L(n). Pellova čísla (1, 2, 5, 12, 29) se řídí jiným multiplikátorem.

Studium těchto příbuzných, jak podrobně popisuje Wolfram MathWorld, objasňuje, proč zlatý řez řídí tempo růstu celé této rodiny.