Fibonacciho sekvence

V matematiky je Fibonacci sekvence je sekvence z celých čísel , ve které každý termín je součtem dvou podmínek, které ji předcházejí. Začíná to podmínkami 0 a 1, pokud začínáme od indexu 0, nebo 1 a 1, pokud začínáme od indexu 1.

Je třeba si uvědomit , že je tedy definováno pro a pro . (Fne){\ displaystyle (F_ {n})}F0=0,F1=1{\ displaystyle F_ {0} = 0, \ quad F_ {1} = 1}Fne=Fne-1+Fne-2{\ displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}ne⩾2{\ displaystyle n \ geqslant 2}

Podmínky této sekvence se nazývají Fibonacciho čísla a vzniklé z A000045 z OEIS  :

F0{\ displaystyle F_ {0}}	F1{\ displaystyle F_ {1}}	F2{\ displaystyle F_ {2}}	F3{\ displaystyle F_ {3}}	F4{\ displaystyle F_ {4}}	F5{\ displaystyle F_ {5}}	F6{\ displaystyle F_ {6}}	F7{\ displaystyle F_ {7}}	F8{\ displaystyle F_ {8}}	F9{\ displaystyle F_ {9}}	F10{\ displaystyle F_ {10}}	F11{\ displaystyle F_ {11}}	F12{\ displaystyle F_ {12}}	F13{\ displaystyle F_ {13}}	F14{\ displaystyle F_ {14}}	F15{\ displaystyle F_ {15}}	F16{\ displaystyle F_ {16}}	...	Fne{\ displaystyle F_ {n}}
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	...	Fne-1+Fne-2{\ displaystyle F_ {n-1} + F_ {n-2}}

Tato sekvence je spojena s zlaté číslo , (fí): Toto číslo zasahuje do exprese obecný termín sekvence. Naopak, Fibonacciho sekvence zasahuje do psaní redukcí exprese jako pokračující frakce  : kvocienty dvou po sobě jdoucích termínů Fibonacciho sekvence jsou nejlepšími aproximacemi zlatého řezu. φ{\ displaystyle \ varphi}φ{\ displaystyle \ varphi}

Dějiny

V Indii

V oboru matematiky kombinatoriky se indičtí matematici zajímají o lexikografické a metrické problémy. Arya metr  (v), se skládá z slabik může být krátká (délka A Matra), nebo dlouhé (dvě baňky délka). Otázkou je, jak se může střídat krátký (C) a dlouhý (L) ve verši od n mātrās. Tento problém se v Indii objevuje velmi brzy, pod jménem maatraameru (hora kadence), v díle sanskrtského gramatika Pingala , Chhandah-shastra (umění prozódie), 450 nebo 200 před naším letopočtem. INZERÁT). Indický matematik Virahanka  (in) dala jasná pravidla, aby VIII th  století . Indický filozof Acharya Hemachandra (asi 1150) (a také Gopala, asi 1135) se k problému vrátil znovu.

Pokud je dlouhá samohláska dvakrát tak krátká, řešení jsou, v závislosti na celkové délce kadence:

1 C → 1 2 CC, L → 2 3 CCC, CL, LC → 3 4 CCCC, CCL, CLC, LCC, LL → 5 5 CCCCC, CCCL, CCLC, CLCC, LCCC, CLL, LCL, LLC → 8

Počet kadencí ukazuje podmínky Fibonacciho posloupnosti. Ve skutečnosti lze rychlost délky n vytvořit přidáním C k rychlosti délky n - 1 nebo L k rychlosti délky n - 2. Počet rychlostí délky n je tedy součtem dvou předchozích čísel pokračování.

Pokud označíme S n , počet způsobů střídání krátkého a dlouhého ve verši n mātrās, vede tato poznámka přirozeně k následující relaci opakování Sne=Sne-1+Sne-2{\ displaystyle S_ {n} = S_ {n-1} + S_ {n-2}} Vzorec výslovně uveden ve Virahankově díle.

Populace králíka

Za své pokračování vděčí Leonardo Fibonacci, který v rekreačním problému představovaném v knize Liber abaci vydané v roce 1202 popisuje růst populace králíků:

„Někdo uložil pár králíků na určité místo, uzavřené ze všech stran, aby zjistil, kolik párů by z toho páru za rok přišlo, protože je v jejich povaze vygenerovat další pár za jediný měsíc,“ a to rodí druhý měsíc po narození. "

Fibonacciho problém spočívá v počátku sekvence, jejíž n-tý člen odpovídá počtu párů králíků v devátém měsíci. U této ideální populace předpokládáme, že:

• na počátku prvního měsíce, tam je jen pár baby králíků;
• králíci se mohou rozmnožovat až po dvou měsících existence;
• každý začátek měsíce generuje jakýkoli pár, který se pravděpodobně bude plodit, přesně jeden nový pár mladých králíků;
• králíci nikdy neumírají (takže Fibonacciho sekvence se zvyšuje).

Poznamenejte si počet párů králíků na začátku měsíce n . Do konce druhého měsíce je počet obyvatel omezen na pár (což si všimneme :) . Fne{\ displaystyle F_ {n}}F1=F2=1{\ displaystyle F_ {1} = F_ {2} = 1}

Od začátku třetího měsíce jsou dvojici králíků dva měsíce a produkují další pár králíků; pak si všimneme . F3=2{\ displaystyle F_ {3} = 2}

Položme se nyní na měsíc n a pokusme se vyjádřit, co to bude o dva měsíce později, tj. Měsíc n + 2  : páry králíků jsou tvořeny z párů z předchozího měsíce a z nově vytvořených párů. Fne+2{\ displaystyle F_ {n + 2}}Fne+1{\ displaystyle F_ {n + 1}}

V měsíci n + 2 se však produkují pouze pubertální páry, to znamená ty, které existují před dvěma měsíci, což je mnoho . Proto máme pro každé přísně kladné celé číslo n : Fne{\ displaystyle F_ {n}}

Fne+2=Fne+1+Fne{\ displaystyle F_ {n + 2} = F_ {n + 1} + F_ {n}}

Poté se rozhodneme pózovat , aby byl tento vztah stále ověřen pro n = 0 . F0=0{\ displaystyle F_ {0} = 0}

Získáváme tedy rekurentní formu Fibonacciho posloupnosti: každý člen této posloupnosti je součtem dvou předcházejících členů  ; k získání každého z těchto dvou výrazů je nutné sečíst součet jejich předchozích výrazů… a tak dále, dokud tyto dva výrazy nejsou dvěma počátečními výrazy, a , které jsou známé. F1{\ displaystyle F_ {1}}F0{\ displaystyle F_ {0}}

Funkční výraz

Výpočet n- tého členu Fibonacciho posloupnosti pomocí vzorce opakování vyžaduje výpočet předcházejících členů. Naopak, funkční výraz Fibonacciho posloupnosti je výrazem, kde výpočet n- tého výrazu nepředpokládá znalost předchozích výrazů. Binet znovu objevil recept v roce 1843, který již získal de Moivre v roce 1718 a Euler v roce 1765. Tento funkční výraz se nazývá Binetův vzorec  :

Fne=15(φne-φ′ne),sφ=1+52aφ′=1-52=-1φ{\ displaystyle F_ {n} = {\ frac {1} {\ sqrt {5}}} (\ varphi ^ {n} - \ varphi '^ {n}), \ qquad {\ text {with}} \ qquad \ varphi = {\ frac {1 + {\ sqrt {5}}} {2}} \ qquad {\ text {et}} \ qquad \ varphi '= {\ frac {1 - {\ sqrt {5}}} {2}} = - {\ frac {1} {\ varphi}}}. Demonstrace

Jako sekvence Fibonacci je lineárně recidivující řádu 2 , jeho charakteristická rovnice je kvadratická rovnice  :

X2-X-1=0{\ displaystyle x ^ {2} -x-1 = 0},

jehož dvě řešení jsou:

φ=1+52aφ′=-1φ=1-52{\ displaystyle \ varphi = {\ frac {1 + {\ sqrt {5}}} {2}} \ qquad {\ text {et}} \ qquad \ varphi '= - {\ frac {1} {\ varphi} } = {\ frac {1 - {\ sqrt {5}}} {2}}},

kde φ je zlatý řez . Sekvence ( φ n ) a ( φ ' n ) poté generují vektorový prostor sekvencí splňující u n + 2 = u n + 1 + u n . Z toho vyplývá, že :

Fne=αφne+βφ′ne{\ displaystyle F_ {n} = \ alpha {} \ varphi ^ {n} + \ beta \ varphi '^ {n}}kde α a β jsou konstanty, které se stanoví z a .F0{\ displaystyle F_ {0}}F1{\ displaystyle F_ {1}}

Počáteční podmínky a vedou k následujícím systému: F0=0{\ displaystyle F_ {0} = 0}F1=1{\ displaystyle F_ {1} = 1}

{α+β=0α-β=25{\ displaystyle \ left \ {{\ begin {matrix} \ alpha + \ beta = 0 \\\ alpha - \ beta = {\ frac {2} {\ sqrt {5}}} \ end {matrix}} \ vpravo .}

Poté získáme:

α=15aβ=-15{\ displaystyle \ alpha = {\ frac {1} {\ sqrt {5}}} \ qquad {\ text {et}} \ qquad \ beta = - {\ frac {1} {\ sqrt {5}}}}.

Nakonec získáme požadovaný funkční výraz.

 

(Tyto výpočty zůstávají platné pro n záporné celé číslo, pokud je posloupnost prodloužena, jak je uvedeno níže.)

Když n jde na + ∞ , je ekvivalentní s . Přesněji řečeno, φ n má sklon k nekonečnu a φ ' n má sklon k nule, protože . Fne{\ displaystyle F_ {n}}φne5{\ displaystyle {\ frac {\ varphi ^ {n}} {\ sqrt {5}}}}|φ′|<1<φ{\ displaystyle | \ varphi '| <1 <\ varphi}

Ve skutečnosti, z hodnosti n = 1 , je druhý člen dostatečně malý na to, aby čísla Fibonacci mohla být získána pouze z prvního členu: φ′ne5{\ displaystyle {\ varphi '^ {n} \ nad {\ sqrt {5}}}}

Fne{\ displaystyle F_ {n}}je celé číslo nejblíže k (a je větší nebo menší než to, v závislosti na paritě n ).φne5{\ displaystyle {\ frac {\ varphi ^ {n}} {\ sqrt {5}}}}

Existují další důkazy o Binetově vzorci, jako je transformace do Z a technika generování funkcí .

Všimněte si, že jakmile bude tento vzorec objeven, může být také prokázán indukcí (včetně n záporného celého čísla).

Rozšíření na záporné indexy

Následující text je rozšířen na záporné indexy a Knuth hovoří o negafibonacciho číslech . Vzorec opakování je také definuje krok za krokem:Fne=Fne+2-Fne+1{\ displaystyle F_ {n} = F_ {n + 2} -F_ {n + 1}}Takže kolem 0 je sekvence:

F-6{\ displaystyle F _ {- 6}}	F-5{\ displaystyle F _ {- 5}}	F-4{\ displaystyle F _ {- 4}}	F-3{\ displaystyle F _ {- 3}}	F-2{\ displaystyle F _ {- 2}}	F-1{\ displaystyle F _ {- 1}}	F0{\ displaystyle F_ {0}}	F1{\ displaystyle F_ {1}}	F2{\ displaystyle F_ {2}}	F3{\ displaystyle F_ {3}}	F4{\ displaystyle F_ {4}}	F5{\ displaystyle F_ {5}}	F6{\ displaystyle F_ {6}}
-8	5	-3	2	-1	1	0	1	1	2	3	5	8

Na těchto prvních hodnotách si toho všimneme

• pokud n je i tehdyF-ne=-Fne{\ displaystyle F _ {- n} = - F_ {n}}
• pokud n je liché, pakF-ne=Fne{\ displaystyle F _ {- n} = F_ {n}}

nebo více synteticky:

F-ne=(-1)ne+1Fne{\ displaystyle F _ {- n} = (- 1) ^ {n + 1} F_ {n}}.

Můžeme to dokázat pro jakékoli celé číslo n , Binetovým vzorcem výše nebo přímo indukcí.

Maticový výraz

Ze zřejmého vztahu odvodíme a ; to umožňuje napsat maticový formulář:[FneFne-1]=[1110][Fne-1Fne-2]{\ displaystyle {\ begin {bmatrix} F_ {n} \\ F_ {n-1} \ end {bmatrix}} = {\ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix}} {\ začátek {bmatrix} F_ {n-1} \\ F_ {n-2} \ konec {bmatrix}}}[FneFne-1]=[1110]ne[01]{\ displaystyle {\ begin {bmatrix} F_ {n} \\ F_ {n-1} \ end {bmatrix}} = {\ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix}} ^ { n} {\ begin {bmatrix} 0 \\ 1 \ end {bmatrix}}}[Fne+1Fne]=[1110]ne[10]{\ displaystyle {\ begin {bmatrix} F_ {n + 1} \\ F_ {n} \ end {bmatrix}} = {\ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix}} ^ { n} {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}}}

[1110]ne=[Fne+1FneFneFne-1]{\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix}} ^ {n} = {\ begin {bmatrix} F_ {n + 1} & F_ {n} \\ F_ {n } & F_ {n- 1} \ end {bmatrix}}}

Použitím rozhodujícího se jednoduše získá vztah (viz níže) . Fne+1Fne-1-Fne2=(-1)ne{\ displaystyle F_ {n + 1} F_ {n-1} -F_ {n} ^ {2} = (- 1) ^ {n}}

A výpočet ve dvou směrech , dostaneme: . [1110]ne+m{\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix}} ^ {n + m}}FneFm+1+Fne-1Fm=Fne+m{\ displaystyle F_ {n} F_ {m + 1} + F_ {n-1} F_ {m} = F_ {n + m}}

Vyjádření determinantem řádu n - 1

Rozšířením vzhledem k prvnímu sloupci determinantu řádu n : , získáme  ; stejně jako v případě , dostaneme: odkud pro  :Dne=|1b00⋯000na1b0⋯0000na1b⋯000⋮⋮⋮⋮⋱⋮⋮⋮0000⋯na1b0000⋯0na1|{\ displaystyle D_ {n} = {\ begin {vmatrix} 1 & b & 0 & 0 & \ cdots & 0 & 0 & 0 \\ a & 1 & b & 0 & \ cdots & 0 & 0 & 0 \\ 0 & a & 1 & b & \ cdots & 0 & 0 & 0 \\\ vdots & \ vdots & \ vdots & d \ d vdots & vdots & vdots & vdots & vdots & vdots & vdots & vdots \ vdots & \ vdots \\ 0 & 0 & 0 & 0 & \ cdots & a & 1 & b \\ 0 & 0 & 0 & 0 & \ cdots & 0 & a & 1 \\\ end {vmatrix}}}Dne=Dne-1-nabDne-2{\ displaystyle D_ {n} = D_ {n-1} -abD_ {n-2}}D1=1,D2=1-nab{\ displaystyle D_ {1} = 1, D_ {2} = 1-ab}nab=-1{\ displaystyle ab = -1}Dne=Fne+1{\ displaystyle D_ {n} = F_ {n + 1}}ne⩾2{\ displaystyle n \ geqslant 2}

Fne=|1-100⋯00011-10⋯000011-1⋯000⋮⋮⋮⋮⋱⋮⋮⋮0000⋯11-10000⋯011|(ne-1)×(ne-1)=|1i00⋯000i1i0⋯0000i1i⋯000⋮⋮⋮⋮⋱⋮⋮⋮0000⋯i1i0000⋯0i1|(ne-1)×(ne-1){\ displaystyle F_ {n} = {\ begin {vmatrix} 1 & -1 & 0 & 0 & \ cdots & 0 & 0 & 0 \\ 1 & 1 & -1 & 0 & \ cdots & 0 & 0 & 0 \\ 0 & 1 & 1 & -1 & \ cdots & 0 & 0 & 0 \\\ vdots & \ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ vdots & \ vdots \\ 0 & 0 & 0 & 0 & \ cdots & 1 & 1 & -1 \\ 0 & 0 & 0 & 0 & \ cdots & 0 & 1 & 1 \\\ end {vmatrix}} _ {(n-1) \ times {( n-1)}} = {\ begin {vmatrix} 1 & i & 0 & 0 & \ cdots & 0 & 0 & 0 \\ i & 1 & i & 0 & \ cdots & 0 & 0 & 0 \\ 0 & i & 1 & i & \ cdots & 0 & 0 & 0 \\\ vdots & \ vdots & \ vdots & \ vdots & \ ddots & \ vdots & vdots & vdots & \ vdots & vdots 0 & 0 & 0 & 0 & \ cdots & i & 1 & i \\ 0 & 0 & 0 & 0 & \ cdots & 0 & i & 1 \\\ end {vmatrix}} _ {(n-1) \ times {(n-1) }}}

Limit podílu

Jak si již všiml Johannes Kepler , tempo růstu Fibonacciho čísel, to znamená , konverguje ke zlatému poměru φ . Fne+1Fne{\ displaystyle {\ frac {F_ {n + 1}} {F_ {n}}}}

Ve skutečnosti, protože sekvence je ekvivalentní k (viz výše, oddíl funkční expresi ), sekvence je ekvivalentní , což je proto jeho omezení. Fne{\ displaystyle F_ {n}}φne5{\ displaystyle {\ frac {\ varphi ^ {n}} {\ sqrt {5}}}}Fne+1Fne{\ displaystyle {\ frac {F_ {n + 1}} {F_ {n}}}}φne+15φne5=φ{\ displaystyle {\ frac {\ frac {\ varphi ^ {n + 1}} {\ sqrt {5}}} {\ frac {\ varphi ^ {n}} {\ sqrt {5}}}} = \ varphi }

Obecněji řečeno, všechny sekvence splňující stejnou relaci opakování jako Fibonacciho sekvence (viz níže, část Obecné Fibonacciho sekvence ) splňují tuto vlastnost, kromě těch, které začínají a a a ' .

Série inverzí termínů Fibonacciho posloupnosti

• Řada z inverzí non nulových Fibonacci čísel je konvergentní  ; R. André-Jeannin prokázala v roce 1989, že její součet je nerozumný , viz pokračování A079586 na OEIS .∑ne=1∞1Fne=3,35988566 ....{\ displaystyle \ sum _ {n = 1} ^ {\ infty} {\ frac {1} {F_ {n}}} = 3,35988566 ....}
• Máme také rovnost ∑k=0∞1F2k=7-52{\ displaystyle \ sum _ {k = 0} ^ {\ infty} {\ frac {1} {F_ {2 ^ {k}}}} = {\ frac {7 - {\ sqrt {5}}} {2 }}}
• Číslo je také iracionální .∑k=0∞1F2k+1{\ displaystyle \ sum _ {k = 0} ^ {\ infty} {\ frac {1} {F_ {2 ^ {k} +1}}}}

Báze a vektorové prostory

• Název „následující všeobecný Fibonacci“ je přičítán obecně jakoukoliv sekvenci nastavena na ℕ kontrolu po celou dobu přirozené n , . Tyto apartmány jsou právě ty, pro které jsou čísla a b tak, že pro všechny přirozené číslo n , . Sada Fibonacciho sekvencí je tedy vektorovým podprostorem těchto sekvencí a tvoří jejich základ .(Gne){\ displaystyle (G_ {n})}Gne+2=Gne+1+Gne{\ displaystyle G_ {n + 2} = G_ {n + 1} + G_ {n}}Gne=naFne+bFne+1{\ displaystyle G_ {n} = aF_ {n} + bF_ {n + 1}}RNE{\ displaystyle \ mathbb {R} ^ {\ mathbb {N}}}(Fne){\ displaystyle (F_ {n})}(Fne+1){\ displaystyle (F_ {n + 1})}
• Zlatý řez je kladný kořen polynomu X 2 - X - 1 , takže φ 2 = φ + 1 . Pokud vynásobíme obě strany φ n , dostaneme φ n + 2 = φ n + 1 + φ n , takže sekvence je Fibonacciho sekvence. Záporný kořen polynomu, φ ' = 1 - φ , má stejné vlastnosti a dvě lineárně nezávislé sekvence a tvoří další základ vektorového prostoru.(φne){\ displaystyle (\ varphi ^ {n})}(φne){\ displaystyle (\ varphi ^ {n})}(φ′ne){\ displaystyle (\ varphi '^ {n})}

Algoritmy pro výpočet Fibonacciho čísel

Výpočet Fibonacciho čísel je často uveden jako příklad pro zavedení pojmů algoritmů, jako v kapitole 0 knihy Algorithms od Dasgupty et al. nebo v úloze 31.3 ponechané v cvičení v Úvod do algoritmu Cormen et al. .

S Binetovým vzorcem

Výpočet Fibonacciho čísel ze zlatého řezu je velmi praktická možnost. Přesnost výpočtu druhé odmocniny však generuje chyby zaokrouhlování pro dostatečně velké hodnoty v závislosti na použitém systému. Obecně jsou správné hodnoty získány až do = 308 061 521 170 129, na počítači nebo na kalkulačce. F71{\ displaystyle F_ {71}}

Poznámka , že kromě , výpočty překročit možnosti výpočtu v celé soustavě, a potom jsou zastoupeny ve vědecké notaci. První významné číslice jsou pak opět dobře reprezentovány tímto vzorcem. F79{\ displaystyle F_ {79}}

Detail příkladu proveditelné aplikace pomocí kalkulačky  : výpočet . F50{\ displaystyle F_ {50}}

Zlatý číslo je hodnota a v souladu se Binet formule , je celé číslo nejblíže ke skutečnému , který je sotva překračuje. Vezmeme-li v úvahu řád této reálnosti, věta o konečných přírůstcích umožňuje zajistit, aby pro její výpočet ve výchozím nastavení byla 1,61803398874989 dostatečná aproximace φ . φ=1+52≈1,618{\ displaystyle \ varphi = {\ frac {1 + {\ sqrt {5}}} {2}} \ přibližně 1 {,} 618}F50{\ displaystyle F_ {50}}φ505{\ displaystyle {\ frac {\ varphi ^ {50}} {\ sqrt {5}}}}

Zjistili jsme, že skutečná (1.61803398874989) 50 / √ 5 je sotva menší než celé číslo 12 586 269 025, tedy

F50≈φ505≈12586269025{\ displaystyle F_ {50} \ přibližně {\ frac {\ varphi ^ {50}} {\ sqrt {5}}} \ přibližně 12586269025},

aby

F50=12586269025{\ displaystyle F_ {50} = 12586269025}.

Naivní rekurzivní algoritmus

Zde je naivní rekurzivní implementace, která následuje po definici Fibonacciho posloupnosti.

// entrée : un nombre entier n // sortie : le terme de rang n de la suite de Fibonacci fonction fibo(n) si n = 0 alors renvoyer 0 sinon si n = 1 alors renvoyer 1 sinon renvoyer fibo(n - 1) + fibo(n - 2)

To však není dobrý způsob pro výpočet Fibonacciho posloupnosti, protože stejné hodnoty se počítají mnohokrát. Doba výpočtu je exponenciální v n , pokud není memoization se používá technika .

Polynomiální algoritmus

Vypočítáme n-tý člen Fibonacciho posloupnosti zapamatováním dvou po sobě jdoucích členů posloupnosti. Začneme s prvními dvěma hodnotami i = 0 a j = 1 , poté první číslo opakovaně nahradíme druhým a druhé číslo součtem dvou.

fonction fibo(n) (i, j) := (0, 1) pour k = 1 à n (i, j) = (j, i+j) retourner i

Algoritmus provádí n sčítání. Můžeme ukázat, že n- tý člen Fibonacciho posloupnosti je zapsán O ( n ) bity. Protože přidání dvou čísel přes n bitů je lineární v n , je algoritmus v O ( n 2 ) . Způsobem ekvivalentním výše uvedenému algoritmu můžeme napsat terminální rekurzivní funkci , to znamená, kde poslední operací provedenou funkcí je rekurzivní volání. Zde je terminální rekurzivní algoritmus pro výpočet Fibonacciho posloupnosti.

fonction fibonacci(n, a, b) si n = 0 alors retourner a sinon si n = 1 alors retourner b sinon retourner fibonacci(n-1, b, a+b)

Volání fibonacci (n, 0, 1) zahájí výpočet pro ndatovou hodnotu . Parametry a a b jsou akumulátory: hodnota a je F n a hodnota b je F n +1 . Čas výpočtu je vždy úměrný n Na druhé straně obsazený paměťový prostor již a priori není konstantní. U jazyků, které provádějí optimalizaci eliminace rekurze terminálu , je obsazená paměť konstantní.

Korzivní algoritmus

V Haskellu můžeme definovat Fibonacciho sekvenci jako proud (nekonečný seznam, který je líně vyhodnocen ).

fibs = 0:1:zipWith (+) fibs (tail fibs)

Výpočet n-tého členu se provádí pomocí:

fibs !! n

Algoritmus s maticovým výrazem

Jak je vidět výše, napíšeme algoritmus, který k výpočtu používá rychlou umocnění , aby bylo možné odvodit n- tý člen . Pokud vezmeme v úvahu sčítání a násobení čísel jako základní operace, při stálých nákladech je algoritmus logaritmický v n . Účtováním složitosti sčítání a násobení můžeme ukázat, že složitost tohoto algoritmu je v O (M ( n ) log n ), a dokonce i v O (M ( n )), kde M ( n ) je složitost Algoritmus použitý k vynásobení dvou čísel na n bitů (viz cvičení 0.4 v). [1110]ne=[Fne+1FneFneFne-1]{\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix}} ^ {n} = {\ begin {bmatrix} F_ {n + 1} & F_ {n} \\ F_ {n } & F_ {n- 1} \ end {bmatrix}}}[1110]ne{\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix}} ^ {n}}

Algoritmická zvědavost

Program FRACTRAN definovaný v seznamu frakcí [23/95, 57/23, 17/39, 130/17, 11/14, 35/11, 19/13, 1/19, 35/2, 13/7, 7] a aplikováno na celé číslo 3 generuje sekvenci, která obsahuje všechny členy ve tvaru 2 a 3 b , kde a a b jsou dva po sobě jdoucí členy Fibonacciho posloupnosti.

Řada generátorů

Série generování sekvence Fibonacci dává celé číslo série , jejíž poloměr konvergence je 1 / φ (podle věty Cauchyova-Hadamardova nebo jednodušeji, d'pravidlo Alembertova ). Pro jakékoliv složité Z z modulu striktně nižší než 1 / φ se odpovídající řady ( absolutně konvergentní ) je rovna ∑ne∈NEFnezne=z1-z-z2{\ displaystyle \ sum _ {n \ in \ mathbb {N}} F_ {n} z ^ {n} = {\ frac {z} {1-zz ^ {2}}}} (tedy na , kde jsou binomické koeficienty nulové pro k > m ). z∑m∈NE(z+z2)m=∑m,k∈NE(mk)z1+m+k{\ displaystyle z \ sum _ {m \ in \ mathbb {N}} (z + z ^ {2}) ^ {m} = \ sum _ {m, k \ in \ mathbb {N}} {m \ zvolit k} z ^ {1 + m + k}} (mk){\ displaystyle m \ zvolit k}

Demonstrace

Poznámka s(z)=∑ne∈NEFnezne{\ displaystyle s (z) = \ součet _ {n \ in \ mathbb {N}} F_ {n} z ^ {n}}. Vynásobením dvou členů relace rekurence z n +2 a součtem všech přirozených čísel n získáme: s(z)-F0-F1z=z(s(z)-F0)+z2s(z){\ displaystyle s (z) -F_ {0} -F_ {1} z = z \ vlevo (s (z) -F_ {0} \ vpravo) + z ^ {2} s (z)}, to znamená, že s přihlédnutím i  : F0=0{\ displaystyle F_ {0} = 0}F1=1{\ displaystyle F_ {1} = 1}s(z)-z=zs(z)+z2s(z){\ displaystyle s (z) -z = zs (z) + z ^ {2} s (z)}, nebo (1-z-z2)s(z)=z{\ displaystyle (1-zz ^ {2}) s (z) = z}. Můžeme rozdělit dva členy na 1 - z - z 2, protože z se liší od dvou kořenů - φ a 1 / φ .

Zejména pro jakékoli skutečné k > φ , 1k2-k-1=∑ne=1∞Fne×k-(ne+1){\ displaystyle {\ frac {1} {k ^ {2} -k-1}} = \ součet _ {n = 1} ^ {\ infty} F_ {n} \ krát k ^ {- (n + 1) }}.

Vlastnosti Fibonacciho sekvence

Fibonacciho sekvence má pozoruhodné vlastnosti. Zde jsou některé z nich, nejčastěji demonstrované z Binetova vzorce nebo indukcí (pro některé lze použít i maticový výpočet a identity uvedené v odstavci „logaritmický algoritmus“ ). Také dát některé vlastnosti pojiv Fibonacci sekvence a sekvence čísel Lucas definovanou stejným vztahu, ale s recidivou pro inicializaci a , a přičemž analogem vzorce Binet je: . Lne{\ displaystyle L_ {n}}L0=2{\ displaystyle L_ {0} = 2}L1=1{\ displaystyle L_ {1} = 1}Lne=φne+φ′ne{\ displaystyle L_ {n} = \ varphi ^ {n} + \ varphi '^ {n}}

Pomocí okamžité obnovení na , se rovná počtu konečných sekvencí celých čísel rovno 1 nebo 2, jejichž součet je roven n . (Tak to může být interpretováno jako počet různých způsobů, připravily se 2 x N obdélník s 2 x 1 domino ). ne∈NE{\ displaystyle n \ in \ mathbb {N}}Fne+1{\ displaystyle F_ {n + 1}}

Vlastnost 1  : nebo: . ∀(p,q,r)∈Z3,FpFq+r-(-1)rFp-rFq=Fp+qFr{\ displaystyle \ forall (p, q, r) \ v \ mathbb {Z} ^ {3}, F_ {p} F_ {q + r} - (- 1) ^ {r} F_ {pr} F_ {q } = F_ {p + q} F_ {r}}FpFq+r-FrFp+q=(-1)rFp-rFq{\ displaystyle F_ {p} F_ {q + r} -F_ {r} F_ {p + q} = (- 1) ^ {r} F_ {pr} F_ {q}}

Toto je konkrétní případ pozoruhodných identit ověřených lineárními rekurentními sekvencemi řádu 2 .

Vlastnost 2  : . ∀(p,q)∈Z2,FpFq+1+Fp-1Fq=Fp+q{\ displaystyle \ forall (p, q) \ in \ mathbb {Z} ^ {2}, F_ {p} F_ {q + 1} + F_ {p-1} F_ {q} = F_ {p + q} }

To je případ r = 1 vlastnosti 1.

Vlastnost 3  : . ∀p∈Z,F2p-1=Fp-12+Fp2{\ displaystyle \ forall p \ in \ mathbb {Z}, F_ {2p-1} = F_ {p-1} ^ {2} + F_ {p} ^ {2}}

To je případ q = p –1 vlastnosti 2.

Vlastnost 4  : . ∀(p,r)∈Z2,FpFr+1-FrFp+1=(-1)rFp-r{\ displaystyle \ forall (p, r) \ in \ mathbb {Z} ^ {2}, F_ {p} F_ {r + 1} -F_ {r} F_ {p + 1} = (- 1) ^ { r} F_ {pr}}

To je případ q = 1 vlastnosti 1.

Majetek 5  : (totožnost Katalánce ) a (totožnost Cassini ). ∀(p,q)∈Z2,Fp2-Fp-qFp+q=(-1)p-qFq2{\ displaystyle \ forall (p, q) \ in \ mathbb {Z} ^ {2}, F_ {p} ^ {2} -F_ {pq} F_ {p + q} = (- 1) ^ {pq} F_ {q} ^ {2}}Fp+1Fp-1-Fp2=(-1)p{\ displaystyle F_ {p + 1} F_ {p-1} -F_ {p} ^ {2} = (- 1) ^ {p}}

Totožnost katalánštiny je případ r = p - q vlastnosti 1. Totožnost Cassini je případ q = 1 katalánštiny (je to tedy také případ r = p - 1 vlastnosti 4). Důsledek 1  : .∀p∈Z,Fp=Fp-1+5Fp-12-4(-1)p2 a 5Fp2+4(-1)p∈NE{\ displaystyle \ forall p \ in \ mathbb {Z}, F_ {p} = {\ frac {F_ {p-1} + {\ sqrt {5F_ {p-1} ^ {2} -4 (-1) ^ {p}}}} {2}} ~ {\ text {a}} ~ {\ sqrt {5F_ {p} ^ {2} +4 (-1) ^ {p}}} \ v \ mathbb {N }} Demonstrace

K prokázání první vlastnosti stačí vzít v úvahu identitu Cassini a vyřešit získanou kvadratickou rovnici neznámého , viz . (Fp+Fp-1)Fp-1-Fp2=(-1)p{\ displaystyle (F_ {p} + F_ {p-1}) F_ {p-1} -F_ {p} ^ {2} = (- 1) ^ {p}}Fp{\ displaystyle F_ {p}}Fp2-Fp-1Fp-Fp-12+(-1)p=0{\ displaystyle F_ {p} ^ {2} -F_ {p-1} F_ {p} -F_ {p-1} ^ {2} + (- 1) ^ {p} = 0}

Fibonacciho sekvence se také jeví jako opakující se sekvence prvního řádu, ale ne lineární.

Abychom odvodili konec důsledku, provedeme v předchozím vzorci malý posun indexu s tím, že podmínky Fibonacciho posloupnosti jsou celé.

Důsledek 2  : .∀p∈Z,Fp+2Fp+1Fp-1Fp-2-Fp4+1=0{\ displaystyle \ forall p \ in \ mathbb {Z}, F_ {p + 2} F_ {p + 1} F_ {p-1} F_ {p-2} -F_ {p} ^ {4} + 1 = 0} Demonstrace

Fp+1Fp-1Fp+2Fp-2=(Fp2-(-1)p-1F12)(Fp2-(-1)p-2F22)=(Fp2±1)(Fp2∓1)=Fp4-1.{\ displaystyle {\ begin {zarovnáno} F_ {p + 1} F_ {p-1} F_ {p + 2} F_ {p-2} & = (F_ {p} ^ {2} - (- 1) ^ {p-1} F_ {1} ^ {2}) (F_ {p} ^ {2} - (- 1) ^ {p-2} F_ {2} ^ {2}) \\ & = (F_ { p} ^ {2} \ pm 1) (F_ {p} ^ {2} \ mp 1) \\ & = F_ {p} ^ {4} -1. \ end {zarovnáno}}}

Vlastnost 6  : Fibonacci sekvence je nízká dělitelnost  : . ∀(k,ne)∈Z2Fne∣Fnek{\ displaystyle \ forall (k, n) \ in \ mathbb {Z} ^ {2} \ quad F_ {n} \ mid F_ {nk}}

To vyplývá okamžitě z vlastnosti 2 nebo 4 (indukcí na | k | ), nebo z explicitního výpočtu podílu (zejména ). Obecněji (jednou nebo druhou metodou) má jakákoli Lucasova sekvence U ( P , Q ) nízkou dělitelnost . Vlastnost 6 je také - není-li použita jako lemma - důsledkem majetku 8 níže.F2ne=FneLne{\ displaystyle F_ {2n} = F_ {n} L_ {n}}

Vlastnost 7  : Pro jakékoli přirozené číslo n jiné než 4, pokud je prvočíslo , pak n je prvočíslo. Fne{\ displaystyle F_ {n}}

Nebo kontraposem  : pokud n je sloučenina, pak také. Ve skutečnosti předpokládejme, že n = mk s celými čísly m a k striktně většími než 1. Protože n má být odlišné od 4, alespoň jeden ze dvou faktorů je striktně větší než 2: například m > 2 . Vlastností 6 je tedy vlastní dělitel , který tedy není prvočíslem.Fne{\ displaystyle F_ {n}}Fm{\ displaystyle F_ {m}}Fne{\ displaystyle F_ {n}} Opak je falešný, protože 2 je prvočíslo, zatímco není; méně triviální způsob .F2{\ displaystyle F_ {2}}F19=4181=37×113{\ displaystyle F_ {19} = 4181 = 37 \ krát 113}

Vlastnost 8  : Fibonacciho posloupnost je vysoká dělitelnost  : kde ∧ označuje GCD číselných celých čísel . ∀(na,b)∈Z×Z∗, Fna∧Fb=Fna∧b{\ displaystyle \ forall (a, b) \ in \ mathbb {Z} \ krát \ mathbb {Z} ^ {*}, ~ F_ {a} \ land F_ {b} = F_ {a \ land b}}

Zejména, tj. že a jsou prime mezi sebou .∀ne∈Z,Fne∧Fne+1=1{\ displaystyle \ forall n \ in \ mathbb {Z}, F_ {n} \ land F_ {n + 1} = 1}Fne{\ displaystyle F_ {n}}Fne+1{\ displaystyle F_ {n + 1}} Bez použití, že kruh ℤ je Bézout (ani vlastnost 6), obecněji ukážeme, že v jakémkoli kruhu integrálním s GCD má Lucasova sekvence U ( P , Q ) silnou dělitelnost, pokud (a pouze pokud) jeho parametry P a Q jsou mezi nimi hlavní. Důkaz pomocí Bézoutovy věty (a vlastnosti 6)

Dovolit a (které jsou kladné nebo nulové). d=na∧b{\ displaystyle d = a \ land b}D=Fna∧Fb{\ displaystyle D = F_ {a} \ land F_ {b}}

• Podle majetku 6, a proto .Fd | Fna{\ displaystyle F_ {d} ~ | ~ F_ {a}}Fd | Fb{\ displaystyle F_ {d} ~ | ~ F_ {b}}Fd|D{\ displaystyle F_ {d} {} | {} D}
• Podle Bézoutovy věty existují dvě celá čísla x a y taková, že d = ax + by . Nastavme pak p = ax a q = by . Jak D dělí a , dělí také a podle vlastnosti 6, tedy také podle vlastnosti 2, jinými slovy .Fna{\ displaystyle F_ {a}}Fb{\ displaystyle F_ {b}}Fp{\ displaystyle F_ {p}}Fq{\ displaystyle F_ {q}}Fp+q{\ displaystyle F_ {p + q}}D | Fd{\ displaystyle D ~ | ~ F_ {d}}
• Tak, se rovná nebo je na rozdíl od D . Protože je kladná nebo nulová (protože d je), dospějeme k závěru, že .Fd{\ displaystyle F_ {d}}Fd=D{\ displaystyle F_ {d} = D}

Vlastnost 9  : . Zejména : ∀(p,r)∈Z2,Fp+r-(-1)rFp-r=FrLp{\ displaystyle \ forall (p, r) \ in \ mathbb {Z} ^ {2}, F_ {p + r} - (- 1) ^ {r} F_ {pr} = F_ {r} L_ {p} }

Fp+1+Fp-1=Lp,Fp+2-Fp-2=Lp,Fp+3+Fp-3=2Lp{\ displaystyle F_ {p + 1} + F_ {p-1} = L_ {p}, \ quad F_ {p + 2} -F_ {p-2} = L_ {p}, \ quad F_ {p + 3 } + F_ {p-3} = 2L_ {p}}. Rovnost je okamžitá, pokud p = 0 . Pro p ≠ 0 se jedná o speciální případ q = p vlastnosti 1.

10 Typ nemovitosti  : . ∀ne∈Z,φne=Fneφ+Fne-1 a φ′ne=Fneφ′+Fne-1{\ displaystyle \ forall n \ in \ mathbb {Z}, \ varphi ^ {n} = F_ {n} \ varphi + F_ {n-1} ~ {\ text {a}} ~ \ varphi '^ {n} = F_ {n} \ varphi '+ F_ {n-1}}

Demonstrace

Součtem a rozdílem je to stejné, aby se to prokázalo

Lne=FneL1+2Fne-1 a Fne=FneF1{\ displaystyle L_ {n} = F_ {n} L_ {1} + 2F_ {n-1} ~ {\ text {and}} ~ F_ {n} = F_ {n} F_ {1}}.

Druhá rovnost je okamžitá a první vyplývá z vlastnosti 9:

Lne=Fne+1+Fne-1=(Fne+Fne-1)+Fne-1{\ displaystyle L_ {n} = F_ {n + 1} + F_ {n-1} = (F_ {n} + F_ {n-1}) + F_ {n-1}}.

11 Typ nemovitosti  : . ∀ne∈NE∑0≤i<neF2i+1=F2ne,1+∑0≤i<neF2i=F2ne-1a1+∑0≤i<neFi=Fne+1{\ displaystyle \ forall n \ in \ mathbb {N} \ quad \ sum _ {0 \ leq i <n} F_ {2i + 1} = F_ {2n}, \ quad 1+ \ sum _ {0 \ leq i <n} F_ {2i} = F_ {2n-1} \ quad {\ text {a}} \ quad 1+ \ sum _ {0 \ leq i <n} F_ {i} = F_ {n + 1}}

Vlastnost 12  : (konečný součet, protože binomické koeficienty jsou nulové, pokud k <0 nebo k > n - 1 - k ). ∀ne∈NE, Fne=∑k∈Z(ne-1-kk){\ displaystyle \ forall n \ in \ mathbb {N}, ~ F_ {n} = \ sum _ {k \ in \ mathbb {Z}} {n-1-k \ zvolte k}} (ne-1-kk){\ displaystyle {n-1-k \ vyberte k}}

Tuto vlastnost lze okamžitě odvodit z výrazu generující řady ( viz výše ). Můžeme to dokázat také opakováním řádu 2 na n  :

Demonstrace

• Inicializace

( n = 0): a∑k(-1-kk)=0{\ displaystyle \ sum _ {k} {- 1-k \ vyberte k} = 0}F0=0{\ displaystyle {\ mathcal {F}} _ {0} = 0} ( n = 1): a∑k(-kk)=1{\ displaystyle \ sum _ {k} {- k \ vyberte k} = 1}F1=1{\ displaystyle {\ mathcal {F}} _ {1} = 1}

• Předpoklady opakování:

v řadě n ,Fne=∑k(ne-1-kk){\ displaystyle {\ mathcal {F}} _ {n} = \ součet _ {k} {n-1-k \ vybrat k}} v řádku n + 1,Fne+1=∑k(ne-kk){\ displaystyle {\ mathcal {F}} _ {n + 1} = \ součet _ {k} {nk \ zvolit k}}

• Dědičnost (pořadí n + 2):

∑k(ne+1-kk)=∑k((ne-kk)+(ne-kk-1)){\ displaystyle \ sum _ {k} {n + 1-k \ vybrat k} = \ sum _ {k} \ doleva ({nk \ vybrat k} + {nk \ vybrat k-1} \ doprava)} (Pascalův trojúhelníkový vzorec) =Fne+1+∑m(ne-1-mm){\ displaystyle = {\ mathcal {F}} _ {n + 1} + \ součet _ {m} {n-1-m \ vyberte m}}(indukční hypotéza, změna proměnné m = k - 1 ) =Fne+1+Fne{\ displaystyle = {\ mathcal {F}} _ {n + 1} + {\ mathcal {F}} _ {n}} (indukční hypotéza) =Fne+2{\ displaystyle = {\ mathcal {F}} _ {n + 2}} (definice Fibonacciho sekvence). To znamená, že v Pascalově trojúhelníku se čísla Fibonacciho získají sečtením členů umístěných na úhlopříčce (zdola doprava). Podmínky těchto úhlopříček jsou navíc koeficienty Fibonacciho polynomů  ; tedy a .F6(X)=X5+4X3+3X{\ displaystyle F_ {6} (x) = x ^ {5} + 4x ^ {3} + 3x}F9(X)=X8+7X6+15X4+10X2+1{\ displaystyle F_ {9} (x) = x ^ {8} + 7x ^ {6} + 15x ^ {4} + 10x ^ {2} +1}

13 Typ nemovitosti  : . ∀ne∈NE, 2ne-1Fne=∑0≤k≤ne/2(ne2k+1)5k{\ displaystyle \ forall n \ in \ mathbb {N}, ~ 2 ^ {n-1} F_ {n} = \ sum _ {0 \ leq k \ leq n / 2} {n \ zvolit 2k + 1} 5 ^ {k}}

Tato vlastnost vyplývá z binomické expanze Binetova vzorce; byl také podobný vzorec pro číslo Lucas  : . ∀ne∈NE, 2ne-1Lne=∑0≤k≤ne/2(ne2k)5k{\ displaystyle \ forall n \ in \ mathbb {N}, ~ 2 ^ {n-1} L_ {n} = \ sum _ {0 \ leq k \ leq n / 2} {n \ vyberte 2k} 5 ^ { k}}

Vlastnost 14  : Pořadí definované šeky(une)ne∈NE∗{\ displaystyle (u_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}une=Fne+1/Fne{\ displaystyle u_ {n} = F_ {n + 1} / F_ ​​{n}}une+1=1+1/une a une2-une-1=(-1)ne/Fne2{\ displaystyle u_ {n + 1} = 1 + 1 / u_ {n} {\ text {and}} u_ {n} ^ {2} -u_ {n} -1 = (- 1) ^ {n} / F_ {n} ^ {2}}(podle relace opakování na a identitě Cassini viděné v majetku 5). Fne{\ displaystyle F_ {n}}

Vlastnost 15  : Faktorizace Fibonacciho polynomů umožňuje jejich vyjádření (pro n ≥ 1 ) ve formě trigonometrických produktů:Fne{\ displaystyle {F} _ {n}}Fne=∏1≤k≤(ne-1)/23+2cos⁡(2kπne){\ displaystyle {F} _ {n} = \ prod _ {1 \ leq k \ leq (n-1) / 2} 3 + 2 \ cos \ left ({\ frac {2k \ pi} {n}} \ že jo)}.

Dělitelnost Fibonacciho čísel

První přístup k otázce dělitelnosti celým číslem a spočívá ve studiu posloupnosti zbytků modulo a  : tato posloupnost ( r n ) splňuje (v Z / a Z ) stejnou recidivu ( r n +2 = r n 1 + R n ) , a proto je periodická s periodou nejvýše 2 (délky období jako funkce v podobě sekvence? z období Pisano , sekvence A001175 z OEIS ); odvodíme, že pro všechna A , existuje n méně než nebo rovno 2 tak, že (a proto ) je dělitelné . Přesněji řečeno, studium této recidivy v poli Z / p Z (kde p je prvočíslo) vede k vzorcům analogickým s Binetovým vzorcem, ze kterých nakonec odvodíme (v závislosti na tom, zda 5 je nebo n 'není modulo p čtverec  ; viz zákon o kvadratické vzájemnosti ), který je dělitelný 5, a že pokud p je prvočíslo jiné než 5, je dělitelné p, pokud p má tvar 5 m + 1 nebo 5 m + 4 a je dělitelné p jinak . Lze také dosáhnout přesnějších výsledků; v prvním případě je tedy dělitelný p, pokud ( p - 1) / 2 je sudé. Nakonec, pokud p > 2 je prvočíslo a dělí , p k dělí a 2 k +1 dělí  ; tyto poslední výsledky jsou důsledky Henselova lemmatu  ; stejné metody umožňují získat analogické výsledky pro Lucasova čísla . Fne{\ displaystyle F_ {n}}Fne{\ displaystyle F_ {n}} Fne{\ displaystyle F_ {n}}Fkne{\ displaystyle F_ {kn}}F5ne{\ displaystyle F_ {5n}}F(p-1)ne{\ displaystyle F _ {(p-1) n}}F(p+1)ne{\ displaystyle F _ {(p + 1) n}}F(p-1)/2{\ displaystyle F _ {(p-1) / 2}}Fne{\ displaystyle F_ {n}}Fpk-1ne{\ displaystyle F_ {p ^ {k-1} n}}F3.2k-1{\ displaystyle F_ {3,2 ^ {k-1}}}

Primalita Fibonacciho čísel

V průběhu let objevujeme stále větší primární čísla Fibonacciho, ale stále nevíme, zda je existuje nekonečno.

Rozklad celého čísla na součet Fibonacciho čísel

Jakékoli kladné celé číslo se jednoznačně rozloží na součet Fibonacciho čísel s indexem větším nebo rovným 2, přičemž po sobě jdoucí indexy těchto čísel mají rozdíl větší nebo rovný 2, pokud jsou uspořádány v pořadí.

Příklad 25=21+3+1=F8+F4+F2{\ displaystyle 25 = 21 + 3 + 1 = F_ {8} + F_ {4} + F_ {2}}.

Aplikace

• V poezii, fib je malá báseň, jakési haiku , ve kterém počet stop prvních řádků odpovídá prvním číslům sekvence (1, 1, 2, 3, 5, 8).
• Fibonacciho sekvence se objevuje v mnoha problémech s počítáním. Například termín indexu n (pro n větší nebo rovný 2) Fibonacciho posloupnosti umožňuje spočítat počet způsobů procházení dráhy délky n-1 provedením kroků 1 nebo 2. Tento problém je také ekvivalentní problému balení kontejnerů pro n článků o délce 1 nebo 2, jak je uvedeno například v The Art of Computer Programming od Donalda Knutha .
• Fibonacciho čísla se používají při studiu provádění Euklidova algoritmu, který určuje největšího společného dělitele dvou celých čísel.
• Jsou nástrojem (díky vlastnosti 8 a faktorizaciF19{\ displaystyle F_ {19}} ) originálního důkazu Euklidovy věty o prvočíslech .
• Yuri Matiassevich ukázal, že Fibonacciho čísla lze definovat pomocí diofantické rovnice , což vedlo k řešení desátého problému Hilberta . V roce 1975 Jones odvodil, že pro kladné nebo nulové celé číslo x a y byly kladné hodnoty polynomu přesně Fibonacciho čísla. Tyto kladné hodnoty se také získají přiřazením dvou hodnot Fibonacciho číslům x a y jako hodnot .2Xy4+X2y3-2X3y2-y5-X4y+2y{\ displaystyle 2xy ^ {4} + x ^ {2} y ^ {3} -2x ^ {3} y ^ {2} -y ^ {5} -x ^ {4} y + 2y}
• Fibonacciho čísla se objevují ve vzorci úhlopříček trojúhelníku Pascala (viz Vlastnosti , Vlastnost 12 ).

• Dobrá aproximace zlatého obdélníku může být vytvořena pomocí čtverců, jejichž strany se rovnají číslům Fibonacci.

• K logaritmické spirále lze přistupovat následovně: začneme od počátku karteziánského souřadného systému, posuneme jednotky doprava, potom jednotky nahoru, jednotky vlevo, potom jednotky dolů, pak jednotky vpravo atd. Vypadá to jako konstrukce uvedená v článku o zlatém řezu .F1{\ displaystyle F_ {1}}F2{\ displaystyle F_ {2}}F3{\ displaystyle F_ {3}}F4{\ displaystyle F_ {4}}F5{\ displaystyle F_ {5}}
• Fibonacciho čísla se v přírodě často objevují, když jsou logaritmické spirály konstruovány z diskrétní jednotky, například ve slunečnicích nebo v šiškách. Počet okvětních lístků sedmikrásky (a dalších složených květů, jako je slunečnice) patří do sekvence Fibonacci: často 34, 55 nebo 89. To je vysvětleno mechanismem vývoje rostliny (viz odstavec „Phyllotaxis článku o zlatý řez ).
• Většina pohlaví žijících bytostí pochází od dvou rodičů, takže jejich předci v n -é generaci, údajně odlišní, jsou v počtu 2 n . Ale blanokřídlí jsou takoví, že ženy pocházejí ze dvou rodičů a muži jsou pouze z jedné matky. Výsledkem je, že jejich předkové v n-té generaci sestávají z:pro ženy, muže a ženy,Fne{\ displaystyle F_ {n}}Fne+1{\ displaystyle F_ {n + 1}}pro muže, muže a ženy.Fne-1{\ displaystyle F_ {n-1}}Fne{\ displaystyle F_ {n}}Tato forma nepohlavního rozmnožování přesně popisuje rozmnožování včel. Nedávno matematická a historická analýza kontextu Fibonacciho a jeho blízkosti k městu Béjaïa , v té době velkému zdroji vosku (francouzská verze názvu tohoto města je Bougie ), naznačuje, že to byli ve skutečnosti včelaři z Béjaïa a znalosti chovu včel, které skutečně inspirovaly spíše Fibonacciho čísla než chov králíků.

Zobecnění

Existuje několik zevšeobecnění Fibonacciho posloupnosti: úprava počátečních hodnot, úprava koeficientů relace opakování nebo změna počtu členů (nebo pořadí ) relace opakování. Pokud upravíme vše současně (inicializace, opakování, pořadí), dostaneme se k obecné sadě sekvencí s lineární opakováním . Dobrý počet vlastností je zobecněn v případě, že minimální polynom lineární opakující se sekvence definuje Pisotovo číslo . Tyto vlastnosti byly studovány v souvislosti s teorií konečných automatů (o konečných slovech a nekonečných slovech) ve státní tezi Christiane Frougny o reprezentaci celých čísel a realit v Pisotově základně, na návrh Marcela Paula Schützenbergera .

Zobecněné Fibonacciho sekvence

Zobecněnou Fibonacciho sekvenci nazýváme jakoukoli sekvenci definovanou stejným relací opakování jako Fibonacciho sekvence, jejíž počáteční termíny se však liší od 0 a 1. Na modelu důkazu uvedeného výše (viz část Funkční výraz ) je taková sekvence u n ) má stále tvar αφ n + βφ ' n, kde φ je zlaté číslo a . Proto je ekvivalentní k αφ n , s výjimkou případů, α = 0 (která se vyskytuje jen v případě ), tak, že (jako sekvence podílů sekvence Fibonacci ) sekvence konverguje k cp . φ′=-1/φ{\ displaystyle \ varphi '= -1 / \ varphi}u1=φ′u0{\ displaystyle u_ {1} = \ varphi 'u_ {0}}une+1une{\ displaystyle {\ frac {u_ {n + 1}} {u_ {n}}}}

Z těchto řad čísel je nutné uvést Lucasova čísla získaná výběrem jako inicializace: a . To dává následující 2, 1, 3, 4, 7, 11, 18, 29, ... jsou někdy nalezeny inicializace a které se jednoduše posunou po řádku. Tato čísla se používají při řešení diofantických rovnic . Úzce souvisí s Fibonacciho posloupností podle následujícího vztahu: pro jakékoli celé číslo n > 0 (viz Vlastnosti , Vlastnost 9 ). L0=2{\ displaystyle L_ {0} = 2}L1=1{\ displaystyle L_ {1} = 1}L0=1{\ displaystyle L_ {0} = 1}L1=3{\ displaystyle L_ {1} = 3}Lne=Fne+1+Fne-1{\ displaystyle L_ {n} = F_ {n + 1} + F_ {n-1}}

Lucas Suites

Jedná se o sekvence, kde se relace opakování změnila: stala se

Xne+2=PXne-QXne+1{\ displaystyle X_ {n + 2} = PX_ {n} -QX_ {n + 1}}.

Jsou dva typy, označenými X = U a X = V , podle toho, zda je inicializace U 0 = 0 a U 1 = 1 , nebo je V 0 = 2 a V 1 = P .

Fibonacciho sekvence a Lucasova sekvence čísel jsou Lucasovy sekvence U a V parametrů P = 1 a Q = –1 .

K-bonacci apartmá

Jedná se o sekvence, jejichž relace rekurence je řádu k . Termín je součet k výrazů, které mu předcházejí

une+k=une+une+1+une+2+⋯+une+k-1{\ displaystyle u_ {n + k} \, = \, u_ {n} + u_ {n + 1} + u_ {n + 2} + \ tečky + u_ {n + k-1}}

Mezi těmito sekvencemi rozlišujeme sekvenci Tribonacci (opakování řádu 3) a sekvenci Tetranacci (opakování řádu 4). Podle této nové klasifikace sekvencí je Fibonacciho sekvence 2-bonacciho sekvence.

V přírodě

Fibonacciho sekvence se objevuje v mnoha biologických formách, jako je větvení stromů, uspořádání listů na stonku, ovoce ananasu , kvetení artyčoku , rozvinutí listů kapradiny , uspořádání šišky , šnečí ulita a uspořádání mraků během hurikány. Pokud jde o sedmikrásky , nejčastěji mají řadu okvětních lístků ze sekvence Fibonacci.

Mezi Asteraceae , v květenstvích v kapitulátech , je poskytnutí klenotů na nádobě jako pravidelných spirál, dextrálních a sinistrálních, podle pravidel fylotaxis, ve kterých lze najít sekvenci Fibonacci.

Včely medonosné mají haplodiploidní reprodukci  : neoplodněné vajíčko dá samci a oplodněné vajíčko dělníkovi nebo královně. Muž tedy bude mít matku, zatímco dělníci a královna budou mít matku a otce. Rodokmen mužského pohlaví se proto skládá z jednoho rodiče, dvou prarodičů, tří praprarodičů, pěti praprarodičů atd. ; je to Fibonacciho sekvence.

V kultuře

Malování

Ve své malbě Parade de cirque , malované v letech 1887-1888, používá Georges Seurat první slova sekvence: ústřední postava, dvě postavy vpravo, tři hudebníci, pět bannerů nebo pět diváků vlevo dole, osm vpravo , celkem třináct.

Literatura

• Kurt Aust , Brotherhood of the Invisibles , City Edition,10. března 2010, 450  s. ( ISBN  978-2-8246-0164-9 , číst online )
• Silvia Brena a Iginio Straffi , Maya Fox 2012: The Predestined , t.  1, kapsa pro mládež ,2011
• Dan Brown , Da Vinciho kód , kapesní kniha,2014
• William Dietrich , Napoleonovy pyramidy , kapsa ,2010
• Emily Gravett , Problém s králíky , Kaleidoskop,2009
• Jacques Lacan , Le Séminaire, kniha XVI: Z jednoho do druhého , Le Seuil ,2006,, kapitola: Du pari de Pascal .
• Éric Pessan , The Bark and the Flesh , Éditions du chemin de fer,2015
• Hiroshi Yuki , Matematické dívky , Knihy Bento,2011
• V povídce sci-fi The Guardian of Knowledge požaduje robotický stráž jako heslo „magický vzorec“, kterým není nikdo jiný než Fibonacciho posloupnost, zapomenutá lidmi.

Kino

• Pi
• Číslo 23
• Trestné činy v Oxfordu
• Las Vegas 21
• Jean de Florette
• Da Vinciho kód
• L: Změňte svět
• Nymfomanka
• Nathanův svět

Televize

• Numb3rs (epizoda 6 sezóny 1; epizoda 21 sezóny 5)
• Fringe (epizoda 10 sezóny 1; epizoda 6 sezóny 4)
• Chuck (epizoda 7 sezóny 2)
• Aka
• Ztracený
• Criminal Minds (8. epizoda 4. sezóny)
• Zmizení
• Touch (TV seriál)

Hudba

• Tyto Postupná kovová skupina Tool konstrukce rytmu některých částí kusových Lateralus podle Fibonacci sekvence.
• Švýcarská dětská zpěvačka Sonia Grimm vydala na svém albu Un petit rabbit píseň s názvem The Fibonacci Rabbit . Tato píseň seznamuje děti se zlatým řezem a Fibonacciho posloupností prostřednictvím příkladu růstu populace králíků.
• Podle Ernő Lendvaï skladatel Béla Bartók ve svých dílech pravidelně používal zlatý řez a Fibonacciho sekvenci. Nejvýraznějším příkladem by byla jeho Hudba pro smyčce, perkuse a celestu . Jiní vědci z Bartóku však tento výklad kritizovali.
• Skladatel Iannis Xenakis použil sadu Fibonacci několikrát: již v roce 1952 se pokusil vytvořit „sluchový obraz“ této série, poté v několika skladbách: Zygia v roce 1952 a Le Sacrifice v roce 1953.
• Na kytaru Roberta Smitha , zpěváka The Cure , pro turné skupiny v roce 2016, je začátek sady Fibonacci.

Architektura

Le Corbusier a jeho Modulor , harmonické měřítko v lidském měřítku univerzálně použitelné pro architekturu a mechaniku.

• Architektonické ilustrace

• Tovární komín v Unně .

• Mole Antonelliana v Turíně .

Mario Merz , Fibonacci Suite , veřejná umělecká komise, 1994, Štrasburk.

Hry a videohry

V Metal Gear Solid 4: Guns of the Patriots se pokračování Fibonacciho jeví jako malý rým zpívaný malou Sunny.

Ve hře Watch Dogs je Fibonacciho sekvence zavedena do algoritmu Bellwether, který je schopen přenášet podprahovou zprávu prostřednictvím systému ctOS.

Ve hře Elite na BBC Micro použili vývojáři sekvenci Fibonacci, aby se hra vešla do 22 kB. Hra proto náhodně generuje galaxii, ale poté ji může vygenerovat přesně stejným způsobem, když je hra uložena a poté znovu načtena.

Desková hra „4.6.Suite“ (karetní hra) je založena na číselných sekvencích, zejména na Fibonacciho sekvencích

Zvědavost

Fibonacciho sekvenci lze použít k zapamatování převodů z amerických mil na kilometry. Ve skutečnosti, neboli zlatý řez, a proto můžeme použít přibližný vzorec :, případně vynásobený konstantou. 1mi=1,609km{\ displaystyle 1 \, mi = 1609 \, km} φ≈1,6{\ displaystyle \ varphi \ přibližně 1,6}Fne+1≈φFne{\ displaystyle F_ {n + 1} \ přibližně \ varphi F_ {n}}Fnemi≈Fne+1km{\ displaystyle F_ {n} \, mi \ přibližně F_ {n + 1} \, km}

Například, (ve skutečnosti 4,8 km), tak , tak i , . 3mi≈5km{\ displaystyle 3 \, mi \ přibližně 5 \, km}6mi≈10km{\ displaystyle 6 \, mi \ přibližně 10 \, km}5mi≈8km{\ displaystyle 5 \, mi \ přibližně 8 \, km}10mi≈16km{\ displaystyle 10 \, mi \ přibližně 16 \, km}50mi≈80km{\ displaystyle 50 \, mi \ přibližně 80 \, km}8mi≈13km{\ displaystyle 8 \, mi \ přibližně 13 \, km}

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „  Fibonacciho číslo  “ ( viz seznam autorů ) .

1. Susantha Goonatilake, Směrem ke globální vědě: Mining Civilizational Knowledge, Indiana University Press, 1998, s. 126
2. Jayant Shah, Historie Pingala kombinatoriky , Northeastern University, Boston, str. 38
3. Latinská verze je uvedena v tomto dokumentu str. 283-284 a pro překlad tato sbírka výtahů od Jérôme Gavina, str. 8
4. Binet, JP, „  Paměť na integraci lineárních rovnic s konečnými rozdíly, libovolného řádu s proměnnými koeficienty.  », Zápis ze zasedání Akademie věd 17 ,1843, str.  559-567 ( číst online )
5. E326 , Opera Omnia , řada 1, roč. 15, s.   50-69 .
6. Knuth, Donald (11. 12. 2008), „Negafibonacciho čísla a hyperbolická rovina“, výroční zasedání, The Fairmont Hotel, San Jose, CA: Matematická asociace Ameriky
7. (La) J. Kepler, Strena seu de nive sexangula , 1611
8. Richard André-Jeannin, „  Iracionalita součtu inverzí určitých rekurentních sekvencí  “, CR Acad. Sci. Paris , i Math., Sv.  308,1989, str.  539-541 ( číst online ).
9. Pohled (in) Eric W. Weisstein , „  Reciproční Fibonacciho konstanta  “ na MathWorld a A079586 ( desítková expanze ) a A079587 ( pokračující zlomek ).  
10. (en) Catalin Badea , „  Věta o iracionalitě nekonečných řad a aplikací  “ , Acta Arithmetica , sv.  63,1993, str.  313-323
11. (en) Sanjoy Dasgupta, Christos Papadimitriou a Umesh Vazirani, Algorithms , McGraw-Hill,2008.
12. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein, Úvod do algoritmiky , 1176  s. , Oddíl 31.2
13. Viz diskuse na konci cvičení 0.4 Dasgupta, Papadimitriou a Vazirani 2008 .
14. (in) „  https://www.geeksforgeeks.org/tail-recursion-fibonacci/  “ na geeksforgeeks.org .
15. Viz například podobné hodnocení faktoriálu .
16. (in) Antony JT Davie, Úvod do funkčních programovacích systémů s využitím Haskell , Cambridge University, al.  "Cambridge Computer Science Texts",1992( číst online ) , kap.  7 („Líné hodnocení“) , Oddíl 7.3: Proudy.
17. Tento příklad teorie vyvinutý v (la) Abraham de Moivre , Miscellanea analytica de seriebus et quadraturis ,1730( číst online ) , s.  26-42, je podrobně popsán (en) Johnem Stillwellem , Matematika a její historie [ detail vydání ]( str. 192-194 v Knihách Google ) jako nástroj pro druhý důkaz vzorce „de Binet“ , nezávislý na prvním, publikovaný Danielem Bernoulli před dvěma lety.
18. (in) Werman a D. Zeilberger , „  Bijektivní důkaz Cassiniho identity Fibonacci  “ , Diskrétní matematika. , sv.  58, n o  1,1986, str.  109 ( DOI  10.1016 / 0012-365X (86) 90194-9 , Math Reviews  0820846 ).
19. Pro kombinatorický důkaz viz (in) Arthur T. Benjamin a Jennifer J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof , MAA ,2003( číst online ) , s.  4.
20. Kombinatorický důkaz viz Benjamin a Quinn 2003 , s.  8.
21. Kombinatorický důkaz viz Benjamin a Quinn 2003 , s.  11.
22. Kombinatorický důkaz viz Benjamin a Quinn 2003 , s.  2-3. Můžeme také získat první dvě rovnosti pomocí teleskopického součtu a třetí odvodit jejich přidáním jiným způsobem podle parity n  : viz například toto opravené cvičení na Wikiversity .
23. Pohled (in) Steven Vajda  (in) , Fibonacci a Lucas Numbers a Zlatý řez , Dover ,2008( 1 st  ed. 1989) ( číst on-line ) , str.  68-69.
24. (in) Bala Sury, „  Trigonometrické výrazy pro Fibonacciho a Lucase Numbers  “ , Acta Math. Univ. Comenianae , sv.  79, n O  22010, str.  199-208 ( číst online ).
25. (en) T. Lengyel, Řád čísel Fibonacciho a Lucase , Fibonacci Quarterly , 1995.
26. (in) Paulo Ribenboim , The New Book of Prime Number Records , New York, Springer, 1996 ( ISBN  0-387-94457-5 ) , str.  64 .
27. (in) Franz Lemmermeyer , Reciprocity Laws , New York, Springer, 2000 ( ISBN  3-540-66957-4 ) , např. 2,25-2,28, s.  73-74 .
28. (in) Thomas Jeffery a Rajesh Pereira Divisibility Properties of the Fibonacci, Lucas Sequences and Related , 2013.
29. (in) Victor H. Moll, Čísla a funkce: Z pohledu klasicko-experimentálního matematika , AMS ,2012( číst online ) , s.  113, reprodukováno v „  Infinitude of Primes - via Fibonacci Numbers  “ , na Cut The Knot .
30. (in) TC Scott a P. Marketos , „  O původu Fibonacciho sekvence  “ , archiv historie matematiky MacTutor , University of St Andrews ,Březen 2014( číst online )
31. (in) Mario Livio, The Golden Ratio: The Story of PHI, the World's Most Astondishing Number Paperback , Broadway Books; Dotisk vydání,23. září 2003, 294  s. ( ISBN  978-0-7679-0816-0 ).
32. (in) Yafei Zhao et al. , „  Evoluční Co-Možnost Floral meristém identity genů pro vzorování Květné podobného Asteraceae květenství  “ , Plant Physiology , vol.  172, n o  1,září 2016, str.  284-296 ( DOI  10.1104 / str. 16.00779 )
33. (in) Brousseau, A, „  Fibonacciho statistika v jehličnanech  “ , Fibonacci Quarterly , roč.  7,1969, str.  525–532 ( číst online ).
34. (in) SL Basin , „  Fibonacciho sekvence, jak se objevuje v přírodě  “ , The Fibonacci Quarterly , sv.  1, n o  1,1963, str.  53–56 ( číst online [PDF] ).
35. C. Pasquet „  Od Golden Ratio do zlatého řezu  “, Dossier de l'Art , n o  257,března 2018, str.  70-71.
36. Seligman, který sbírá heroin, je stoupencem lovu ryb, Bacha a Fibonacciho sekvence podle osvobození
37. Podrobnosti a vysvětlení v článku „Nymphomaniac“, film plný matematiky od Thomase Messiase na Slate
38. „  X + Y Review [TIFF 2014]  “ (přístup 13. června 2015 )
39. (in) Christopher DiCarlo, Rozhovor s Maynardem Jamesem Keenanem [ číst online ] .
40. Podívejte se na seznam skladeb alba v internetovém obchodě umělce.
41. (in) Ernő Lendvai, Béla Bartók: Analýza jeho hudby - s úvodem Alana Bushe , Kahna a Averilla,1971( ISBN  978-0-900707-81-0 ).
42. Například viz (in) Gareth E. Roberts, „  Bartókova kontroverze  “ ,2015.
43. Sven Sterken, „  Iannis Xenakis, inženýr a architekt. p122  » [PDF] ,2004
44. http://s1.lprs1.fr/images/2016/11/15/6332622_the-cure007.jpg

Podívejte se také

Bibliografie

• (en) Hrant Arakelian, Matematika a dějiny zlatého řezu , Logos 2014, 404 s. ( ISBN  978-5-98704-663-0 ) (rus.)
• (en) JH Halton, „  O vlastnostech dělitelnosti Fibonacciho čísel  “ , Fibonacci Quarterly , sv.  4, n o  3,1966, str.  217-240 ( číst online )
• Nikolai Vorobiev  (en) , Charakteristika dělitelnosti - Fibonacciho posloupnost , kol. Initiation to Mathematics, Mir Editions , Moskva, 1973

Související články

• Fibonacciho skupina
• Padovan Suite
• Fibonacciho slovo
• Fibonacciho kódování
• Sdružení Fibonacci

externí odkazy

• Autoritní záznamy  :
  • Francouzská národní knihovna ( údaje )
  • Knihovna Kongresu
• Dělitelnost Fibonacciho čísel
• Fibonacciho sekvence a zlatý řez v sadě Mandelbrot
• Fibonacciho posloupnost ve slovníku čísel
• J.-C. Michel, „  Zlaté číslo  “ , na gecif.net
• "  Náhodné Fibonacciho sekvence  " ,13. května 2008, konference Benoîta Rittauda ve městě vědy a průmyslu
• (en) RN Knott a tým Plus, „  Život a čísla Fibonacciho  “ , na plus.maths.org ,4. listopadu 2013