Fibonacciho číslo - Fibonacci number - Wikipedia

Obklad se čtverci, jejichž délky stran jsou po sobě jdoucími Fibonacciho čísly: 1, 1, 2, 3, 5, 8, 13 a 21.

V matematice je Fibonacciho čísla, běžně označované F_n, tvoří a sekvence, volal Fibonacciho sekvence, takže každé číslo je součtem dvou předchozích, počínaje od 0 a 1. To znamená,^[1]

${ displaystyle F_ {0} = 0, quad F_ {1} = 1,}$

a

${ displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}$

pro n > 1.

Začátek sekvence je tedy:

${ Displaystyle 0, ; 1, ; 1, ; 2, ; 3, ; 5, ; 8, ; 13, ; 21, ; 34, ; 55, ; 89, ; 144, ; ldots}$^[2]

V některých starších knihách hodnota ${ displaystyle F_ {0} = 0}$ je vynechán, takže posloupnost začíná ${ displaystyle F_ {1} = F_ {2} = 1,}$ a opakování ${ displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}$ platí pro n > 2.^[3][4]

Fibonacciho spirála: aproximace zlatá spirála vytvořeno kresbou kruhové oblouky spojení protilehlých rohů čtverců ve Fibonacciho obkladu; (viz předchozí obrázek)

Fibonacciho čísla jsou silně spojena s Zlatý řez: Binetův vzorec vyjadřuje nFibonacciho číslo z hlediska n a zlatý řez, a znamená, že poměr dvou po sobě jdoucích Fibonacciho čísel má sklon ke zlatému řezu jako n zvyšuje.

Fibonacciho čísla jsou pojmenována po italském matematikovi Leonardovi z Pisy, později známém jako Fibonacci. Ve své knize 1202 Liber Abaci, Fibonacci představil sekvenci v západoevropské matematice,^[5] ačkoli sekvence byla popsána dříve v Indická matematika,^[6][7][8] již v roce 200 př. n. l. v práci Pingala na výčtu možných vzorů sanskrtské poezie vytvořené ze slabik dvou délek.

Fibonacciho čísla se v matematice objevují nečekaně často, natolik, že jejich studiu je věnován celý časopis, Fibonacci čtvrtletně. Aplikace Fibonacciho čísel zahrnují počítačové algoritmy, jako je Fibonacciho vyhledávací technika a Fibonacciho hromada datová struktura a volané grafy Fibonacciho kostky slouží k propojení paralelních a distribuovaných systémů.

Také se objevují v biologickém prostředí, jako je větvení na stromech, uspořádání listů na stonku, ovocné klíčky a ananas, kvetení artyčok, nevrlý kapradina a uspořádání a šiška listeny.

Fibonacciho čísla také úzce souvisí Lucasova čísla ${ displaystyle L_ {n}}$v tom, že čísla Fibonacci a Lucas tvoří doplňkovou dvojici Lucasovy sekvence: ${ displaystyle U_ {n} (1, -1) = F_ {n}}$ a ${ displaystyle V_ {n} (1, -1) = L_ {n}}$.

Dějiny

Třináct (F₇) způsoby uspořádání dlouhých (znázorněných červenými dlaždicemi) a krátkých slabik (zobrazených šedými čtverci) v kadenci délky šest. Pět (F₅) končí dlouhou slabikou a osmičkou (F₆) končí krátkou slabikou.

Fibonacciho sekvence se objeví v Indická matematika ve spojení s Sanskrtská prozódie, jak zdůraznil Parmanand Singh v roce 1986.^[7][9][10] V sanskrtské básnické tradici byl zájem o výčet všech vzorců dlouhých (L) slabik o délce 2 jednotek, vedle sebe s krátkými (S) slabikami o délce 1 jednotky. Počítání různých vzorů postupných L a S s daným celkovým trváním vede k Fibonacciho číslům: počet vzorců trvání m jednotek je F_{m + 1}.^[8]

Znalost Fibonacciho sekvence byla vyjádřena již v Pingala (C. 450 př.nl - 200 př. Nl). Singh uvádí Pingalovu kryptickou formuli misrau cha ("dva jsou smíšené") a vědci, kteří to interpretují v kontextu tak, že říkají, že počet vzorů pro m beaty (F_m+1) se získá přidáním jednoho [S] do F_m případy a jeden [L] do F_m−1 případech.^[11]Bharata Muni také vyjadřuje znalost sekvence v Natya Shastra (asi 100 př. n. l. - asi 350 n. l.).^[12][6]Nejjasnější expozice posloupnosti však vyvstává v práci Virahanka (c. 700 nl), jehož vlastní práce je ztracena, ale je k dispozici v citaci Gopaly (c. 1135):^[10]

Variace dvou dřívějších metrů [je variace] ... Například pro [metr délky] čtyři, varianty metrů dvou [a] tři jsou smíšené, stane se pět. [vypracovává příklady 8, 13, 21] ... Tímto způsobem by měl být proces sledován ve všech mātrā-vṛttas [prozodické kombinace].^[A]

Hemachandra (kolem 1150) se připisuje také znalost sekvence,^[6] píše, že „součet posledního a předposledního je počet ... příští mātrā-vṛtty.“^[14][15]

Stránka z Fibonacci je Liber Abaci z Biblioteca Nazionale di Firenze zobrazující (v rámečku vpravo) Fibonacciho posloupnost s pozicí v posloupnosti označenou latinskými a římskými číslicemi a hodnotou v hindsko-arabských číslicích.

Počet králičích párů tvoří Fibonacciho sekvenci

Mimo Indii se v knize poprvé objevuje Fibonacciho sekvence Liber Abaci (1202) od Fibonacci^[5][16] kde se používá k výpočtu růstu populací králíků.^[17][18] Fibonacci považuje růst idealizovaného (biologicky nereálného) králičí populace za předpokladu, že: nově narozený chovný pár králíků je umístěn na pole; každý chovný pár se páří ve věku jednoho měsíce a na konci druhého měsíce vždy produkují další pár králíků; a králíci nikdy neumírají, ale pokračujte v chovu navždy. Fibonacci položil hádanku: kolik párů bude za jeden rok?

• Na konci prvního měsíce se páří, ale stále existuje jen 1 pár.
• Na konci druhého měsíce produkují nový pár, takže v poli jsou 2 páry.
• Na konci třetího měsíce původní pár produkuje druhý pár, ale druhý pár se páří pouze bez rozmnožování, takže jsou celkem 3 páry.
• Na konci čtvrtého měsíce původní pár vyprodukoval ještě další nový pár a pár narozený před dvěma měsíci také produkuje svůj první pár, který tvoří 5 párů.

Na konci ntého měsíce se počet párů králíků rovná počtu zralých párů (tj. počet párů v měsíci n – 2) plus počet párů naživu minulý měsíc (měsíc n – 1). Číslo v nměsíc je nFibonacciho číslo.^[19]

Název „Fibonacciho sekvence“ poprvé použil teoretik čísel z 19. století Édouard Lucas.^[20]

Aplikace

• Fibonacciho čísla jsou důležitá v výpočetní analýza běhu z Euklidův algoritmus určit největší společný dělitel dvou celých čísel: nejhorším vstupem pro tento algoritmus je dvojice po sobě jdoucích Fibonacciho čísel.^[21]
• Brasch a kol. 2012 ukazují, jak lze zobecněnou Fibonacciho sekvenci spojit také s oblastí ekonomie.^[22] Zejména je ukázáno, jak zobecněná Fibonacciho sekvence vstupuje do řídicí funkce problémů s dynamickou optimalizací konečného horizontu s jedním stavem a jednou řídicí proměnnou. Postup je ilustrován na příkladu často označovaném jako Brock – Mirmanův model ekonomického růstu.
• Jurij Matijasevič dokázal ukázat, že čísla Fibonacci lze definovat a Diophantine rovnice, což vedlo k jeho řešení Hilbertův desátý problém.^[23]
• Čísla Fibonacci jsou také příkladem a kompletní sekvence. To znamená, že každé kladné celé číslo lze zapsat jako součet Fibonacciho čísel, kde se jedno číslo použije maximálně jednou.
• Každé kladné celé číslo lze navíc zapsat jedinečným způsobem jako součet jeden nebo více odlišná čísla Fibonacci takovým způsobem, že součet nezahrnuje žádná dvě po sobě jdoucí čísla Fibonacci. Toto je známé jako Zeckendorfova věta a součet Fibonacciho čísel, který splňuje tyto podmínky, se nazývá Zeckendorfova reprezentace. K odvození čísla lze použít Zeckendorfovu reprezentaci čísla Fibonacciho kódování.
• Někteří používají čísla Fibonacci generátory pseudonáhodných čísel.
• Používají se také v plánování pokeru, což je krok v odhadu u projektů vývoje softwaru, které používají Skrumáž metodologie.
• Fibonacciho čísla se používají v polyfázové verzi Sloučit třídění algoritmus, ve kterém je netříděný seznam rozdělen na dva seznamy, jejichž délky odpovídají sekvenčním Fibonacciho číslům - rozdělením seznamu tak, aby obě části měly délky v přibližném poměru φ. Implementace páskové jednotky třífázové sloučení byl popsán v Umění počítačového programování.
• Fibonacciho čísla vznikají při analýze Fibonacciho hromada datová struktura.
• The Fibonacciho kostka je neorientovaný graf s počtem Fibonacciho uzlů, který byl navržen jako a topologie sítě pro paralelní výpočty.
• Metoda jednorozměrné optimalizace, zvaná Fibonacciho vyhledávací technika, používá Fibonacciho čísla.^[24]
• Číselná řada Fibonacci se používá pro volitelné ztrátová komprese v MFF 8SVX formát zvukového souboru použitý na Amiga počítače. Číselná řada compands původní zvuková vlna podobná logaritmickým metodám jako např μ-zákon.^[25][26]
• Protože konverze faktor 1,609344 na míle na kilometr se blíží zlatému poměru, rozklad vzdálenosti v mílích na součet čísel Fibonacci se stává téměř součtem kilometrů, když jsou čísla Fibonacci nahrazena jejich nástupci. Tato metoda činí a základ 2 číslo Registrovat v základ zlatého řezu φ být posunut. Chcete-li převést z kilometrů na míle, posuňte místo toho registr dolů po Fibonacciho posloupnosti.^[27]
• v optika, když paprsek světla svítí pod úhlem skrz dvě naskládané průhledné desky z různých materiálů různých indexy lomu, může odrážet tři povrchy: horní, střední a spodní povrch dvou desek. Počet různých drah paprsků, které mají k odrazy, pro k > 1, je ${ displaystyle k}$Fibonacciho číslo. (Nicméně kdy k = 1, existují tři odrazové dráhy, ne dvě, jedna pro každou ze tří ploch.)^[28]
• Mario Merz zahrnoval Fibonacciho sekvenci do některých svých děl od roku 1970.^[29]
• Fibonacciho retracement úrovně jsou široce používány v technická analýza pro obchodování na finančním trhu.
• Fibonacciho čísla se objevují v prstencové lemma, slouží k prokázání spojení mezi věta o kruhu a konformní mapy.^[30]

Hudba

Joseph Schillinger (1895–1943) vyvinuli a systém složení který používá Fibonacciho intervaly v některé ze svých melodií; považoval je za hudební protějšek propracované harmonie evidentní v přírodě.^[31]

Příroda

Žlutý heřmánek hlava zobrazující uspořádání ve 21 (modrých) a 13 (aqua) spirálách. Taková uspořádání zahrnující po sobě jdoucí čísla Fibonacci se objevují v široké škále rostlin.

Fibonacciho sekvence se objevují v biologickém prostředí,^[32] jako je větvení na stromech, uspořádání listů na stonku, plody a ananas,^[33] kvetení artyčok, nevázaná kapradina a uspořádání a šiška,^[34] a rodokmen včel.^[35][36] Kepler poukázal na přítomnost Fibonacciho sekvence v přírodě a použil ji k vysvětlení (Zlatý řez související s pětiúhelníkovou formou některých květů.^[37] Pole sedmikrásky nejčastěji mají lístky v počtech Fibonacciho čísel.^[38] V roce 1754 Charles Bonnet objevil, že spirální fylotaxis rostlin byla často vyjádřena v Fibonacciho číselných řadách.^[39]

Przemysław Prusinkiewicz rozšířil myšlenku, že skutečné instance lze zčásti chápat jako vyjádření určitých algebraických omezení skupiny zdarma, konkrétně jako jisté Lindenmayerovy gramatiky.^[40]

Ilustrace Vogelova modelu pro n = 1 ... 500

Model pro vzor kvítky v hlavě a slunečnice byl navržen uživatelem Helmut Vogel [de ] v roce 1979.^[41] To má formu

${ displaystyle theta = { frac {2 pi} { varphi ^ {2}}} n, r = c { sqrt {n}}}$

kde n je indexové číslo floretu a C je konstantní faktor měřítka; kvítky tak leží Fermatova spirála. Divergenční úhel, přibližně 137,51 °, je zlatý úhel, dělení kruhu ve zlatém řezu. Protože tento poměr je iracionální, žádný floret nemá souseda přesně ve stejném úhlu od středu, takže se florety balí efektivně. Protože racionální aproximace zlatého řezu mají formu F(j):F(j + 1), nejbližší sousedé čísla floretu n jsou ti v n ± F(j) pro nějaký index j, což závisí na r, vzdálenost od centra. Slunečnice a podobné květiny mají nejčastěji spirály floretů ve směru hodinových ručiček a proti směru hodinových ručiček v množství sousedních Fibonacciho čísel,^[42] obvykle se počítá podle nejvzdálenějšího rozsahu poloměrů.^[43]

Čísla Fibonacci se také objevují v rodokmenech idealizovaných včel, podle následujících pravidel:

• Pokud vejce snáší nepářená žena, vylíhne se muž nebo drone bee.
• Pokud však bylo vajíčko oplodněno mužem, vylíhla se žena.

Včela má tedy vždy jednoho rodiče a včela dvě. Pokud někdo sleduje původ jakéhokoli včelího muže (1 včela), má 1 rodiče (1 včela), 2 prarodiče, 3 praprarodiče, 5 pra-praprarodičů atd. Tato posloupnost čísel rodičů je Fibonacciho posloupnost. Počet předků na každé úrovni, F_n, je počet předků žen, což je F_n−1plus počet mužských předků, což je F_n−2.^[44] To je za nerealistického předpokladu, že předkové na každé úrovni jinak nesouvisí.

Počet možných předků na linii dědičnosti chromozomů X v dané generaci předků sleduje Fibonacciho sekvenci. (Po Hutchison, L. „Rostoucí rodokmen: Síla DNA při rekonstrukci rodinných vztahů“.)^[45])

Bylo zjištěno, že počet možných předků na člověka X chromozom dědičná čára v dané generaci předků také sleduje Fibonacciho sekvenci.^[45] Mužský jedinec má chromozom X, který dostal od své matky, a Y chromozom, kterou obdržel od svého otce. Samec se počítá jako „původ“ svého vlastního chromozomu X (${ displaystyle F_ {1} = 1}$) a na generaci jeho rodičů pocházel jeho chromozom X od jednoho rodiče (${ displaystyle F_ {2} = 1}$). Matka mužského pohlaví dostala jeden chromozom X od své matky (babička z matčiny strany syna) a jeden od svého otce (dědeček z matčiny strany syna), takže dva prarodiče přispěli do chromozomu X potomka mužského pohlaví (${ displaystyle F_ {3} = 2}$). Dědeček z matčiny strany dostal svůj X chromozom od své matky a babička z matčiny strany obdržel X chromozomy od obou svých rodičů, takže tři praprarodiče přispěli k X chromozomu mužského potomka (${ displaystyle F_ {4} = 3}$). Pět pra-pra-prarodičů přispělo k chromozomu X mužského potomka (${ displaystyle F_ {5} = 5}$) atd. (Předpokládá se, že všichni předkové daného potomka jsou nezávislí, ale pokud je nějaká genealogie vysledována dostatečně daleko v čase, začnou se předkové objevovat na více řádcích genealogie, až nakonec zakladatel populace se objeví na všech řádcích genealogie.)

Cesty tubuliny na intracelulární mikrotubuly uspořádat ve vzorcích 3, 5, 8 a 13.^[46]

Matematika

Čísla Fibonacci jsou součty "mělkých" úhlopříček (zobrazených červeně) z Pascalův trojúhelník.

Fibonacciho čísla se vyskytují v součtech „mělkých“ úhlopříček v Pascalův trojúhelník (vidět binomický koeficient ):^[47]

${ displaystyle F_ {n} = součet _ {k = 0} ^ { levý lfloor { frac {n-1} {2}} pravý rfloor} { binom {nk-1} {k} }.}$

Tato čísla také dávají řešení určitých výčtových problémů,^[48] nejběžnější z nich je počítání počtu způsobů zápisu daného čísla n jako objednaný součet 1 s a 2 s (tzv složení ); existují F_n+1 způsoby, jak to udělat. Například pokud n = 5, pak F_n+1 = F₆ = 8 počítá osm skladeb se součtem 5:

5 = 1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 = 2+2+1 = 2+1+2 = 1+2+2.

Čísla Fibonacciho lze v sadě najít různými způsoby binární struny nebo ekvivalentně mezi podmnožiny dané sady.

• Počet binárních řetězců délky n bez po sobě jdoucích 1s je Fibonacciho číslo F_n+2. Například z 16 binárních řetězců délky 4 existují F₆ = 8 bez po sobě jdoucích 1s - jsou 0000, 0001, 0010, 0100, 0101, 1000, 1001 a 1010. Ekvivalentně, F_n+2 je počet podmnožin S z {1, ..., n} bez po sobě jdoucích celých čísel, to znamená těch S pro který {i, i + 1} ⊈ S pro každého i.
• Počet binárních řetězců délky n bez lichého počtu po sobě jdoucích 1s je Fibonacciho číslo F_{n + 1}. Například z 16 binárních řetězců délky 4 existují F₅ = 5 bez lichého počtu po sobě jdoucích 1s - jsou 0000, 0011, 0110, 1100, 1111. Rovněž počet podmnožin S z {1, ..., n} bez lichého počtu po sobě jdoucích celých čísel je F_n+1.
• Počet binárních řetězců délky n bez sudého počtu po sobě jdoucích 0s nebo 1s je 2F_n. Například z 16 binárních řetězců délky 4 existují 2F₄ = 6 bez sudého počtu po sobě jdoucích 0s nebo 1s - jsou to 0001, 0111, 0101, 1000, 1010, 1110. O podmnožinách existuje ekvivalentní prohlášení.

Vlastnosti sekvence

Prvních 21 čísel Fibonacci F_n jsou:^[2]

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

Sekvenci lze také rozšířit na záporný index n pomocí nového uspořádání relace opakování

${ displaystyle F_ {n-2} = F_ {n} -F_ {n-1},}$

což poskytuje posloupnost čísel „negafibonacci“^[49] uspokojující

${ displaystyle F _ {- n} = (- 1) ^ {n + 1} F_ {n}.}$

Obousměrná sekvence tedy je

F−8

F−7

F−6

F−5

F−4

F−3

F−2

F−1

F0

F1

F2

F3

F4

F5

F6

F7

F8

−21

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8

13

21

Vztah ke zlatému řezu

Uzavřený výraz

Jako každá posloupnost definovaná a lineární opakování s konstantními koeficienty, Fibonacciho čísla mají a uzavřený výraz. To stalo se známé jako Binetův vzorec, pojmenoval podle francouzského matematika Jacques Philippe Marie Binet, ačkoli to již bylo známo Abraham de Moivre a Daniel Bernoulli:^[50]

${ displaystyle F_ {n} = { frac { varphi ^ {n} - psi ^ {n}} { varphi - psi}} = { frac { varphi ^ {n} - psi ^ { n}} { sqrt {5}}}}$

kde

${ displaystyle varphi = { frac {1 + { sqrt {5}}} {2}} přibližně 1,61803 , 39887 ldots}$

je Zlatý řez (OEIS: A001622), a

${ displaystyle psi = { frac {1 - { sqrt {5}}} {2}} = 1- varphi = - {1 over varphi} přibližně -0,61803 , 39887 ldots.}$^[51]

Od té doby ${ displaystyle psi = - varphi ^ {- 1}}$, tento vzorec lze také zapsat jako

${ displaystyle F_ {n} = { frac { varphi ^ {n} - (- varphi) ^ {- n}} { sqrt {5}}} = { frac { varphi ^ {n} - (- varphi) ^ {- n}} {2 varphi -1}}}$

Chcete-li to vidět,^[52] Všimněte si, že φ a ψ jsou obě řešení rovnic

${ displaystyle x ^ {2} = x + 1 quad { text {a}} quad x ^ {n} = x ^ {n-1} + x ^ {n-2},}$

takže pravomoci φ a ψ uspokojit Fibonacciho rekurzi. Jinými slovy,

${ displaystyle varphi ^ {n} = varphi ^ {n-1} + varphi ^ {n-2}}$

a

${ displaystyle psi ^ {n} = psi ^ {n-1} + psi ^ {n-2}.}$

Z toho vyplývá, že pro všechny hodnoty A a b, posloupnost definovaná

${ displaystyle U_ {n} = a varphi ^ {n} + b psi ^ {n}}$

uspokojuje stejné opakování

${ displaystyle U_ {n} = a varphi ^ {n-1} + b psi ^ {n-1} + a varphi ^ {n-2} + b psi ^ {n-2} = U_ { n-1} + U_ {n-2}.}$

Li A a b jsou vybrány tak, aby U₀ = 0 a U₁ = 1 pak výsledná sekvence U_n musí to být Fibonacciho sekvence. To je stejné jako vyžadování A a b uspokojit soustavu rovnic:

${ displaystyle left {{ begin {pole} {l} a + b = 0 varphi a + psi b = 1 end {pole}} doprava.}$

který má řešení

${ displaystyle a = { frac {1} { varphi - psi}} = { frac {1} { sqrt {5}}}, quad b = -a,}$

vytvoření požadovaného vzorce.

Vezmeme-li počáteční hodnoty U₀ a U₁ být libovolné konstanty, obecnější řešení je:

${ displaystyle U_ {n} = a varphi ^ {n} + b psi ^ {n}}$

kde

${ displaystyle a = { frac {U_ {1} -U_ {0} psi} { sqrt {5}}}}$

${ displaystyle b = { frac {U_ {0} varphi -U_ {1}} { sqrt {5}}}}$.

Výpočet zaokrouhlením

Od té doby

${ displaystyle left | { frac { psi ^ {n}} { sqrt {5}}} doprava | <{ frac {1} {2}}}$

pro všechny n ≥ 0, číslo F_n je nejbližší celé číslo ${ displaystyle { frac { varphi ^ {n}} { sqrt {5}}}}$. Proto jej lze najít zaokrouhlování, pomocí funkce nejbližšího celého čísla:

${ displaystyle F_ {n} = left [{ frac { varphi ^ {n}} { sqrt {5}}} right], n geq 0.}$

Ve skutečnosti je chyba zaokrouhlování velmi malá, pro méně než 0,1 n ≥ 4a méně než 0,01 pro n ≥ 8.

Fibonacciho číslo lze také vypočítat pomocí zkrácení, pokud jde o funkce podlahy:

${ displaystyle F_ {n} = left lfloor { frac { varphi ^ {n}} { sqrt {5}}} + { frac {1} {2}} right rfloor, n geq 0.}$

Protože funkce podlahy je monotóní, druhý vzorec lze pro nalezení indexu převrátit n(F) největšího Fibonacciho čísla, které není větší než a reálné číslo F > 1:

${ displaystyle n (F) = levý lfloor log _ { varphi} levý (F cdot { sqrt {5}} + { frac {1} {2}} pravý) pravý rfloor ,}$

kde ${ displaystyle log _ { varphi} (x) = ln (x) / ln ( varphi) = log _ {10} (x) / log _ {10} ( varphi).}$

Limit po sobě jdoucích kvocientů

Johannes Kepler pozoroval, že poměr po sobě jdoucích Fibonacciho čísel konverguje. Napsal, že „jak 5 je 8, tak je 8 až 13, prakticky, a jak 8 je 13, tak je 13 až 21 téměř“, a uzavřel, že tyto poměry se blíží zlatému řezu ${ displaystyle varphi colon}$^[53][54]

${ displaystyle lim _ {n to infty} { frac {F_ {n + 1}} {F_ {n}}} = varphi.}$

Tato konvergence platí bez ohledu na počáteční hodnoty, s výjimkou 0 a 0, nebo jakékoli dvojice v zlatém řezu konjugátu, ${ displaystyle -1 / varphi.}$^{[je zapotřebí objasnění ]} To lze ověřit pomocí Binetův vzorec. Například počáteční hodnoty 3 a 2 generují sekvenci 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... Poměr po sobě následujících termínů v této sekvenci ukazuje stejná konvergence k zlatému řezu.

Postupné naklánění roviny a graf aproximací zlatého řezu vypočítaný dělením každého Fibonacciho čísla předchozím

Rozklad pravomocí

Protože zlatý poměr splňuje rovnici

${ displaystyle varphi ^ {2} = varphi +1,}$

tento výraz lze použít k rozložení vyšších sil ${ displaystyle varphi ^ {n}}$ jako lineární funkce nižších sil, kterou lze zase rozložit až na lineární kombinaci ${ displaystyle varphi}$ a 1. Výsledek opakovací vztahy získá Fibonacciho čísla jako lineární koeficienty:

${ displaystyle varphi ^ {n} = F_ {n} varphi + F_ {n-1}.}$

Tuto rovnici lze dokázat indukce na n.

Tento výraz platí také pro n <1 pokud je Fibonacciho sekvence F_n je rozšířena na záporná celá čísla pomocí Fibonacciho pravidla ${ displaystyle F_ {n} = F_ {n-1} + F_ {n-2}.}$

Maticová forma

Dvourozměrný lineární systém rozdílové rovnice který popisuje Fibonacciho sekvenci

${ displaystyle {F_ {k + 2} zvolit F_ {k + 1}} = { begin {pmatrix} 1 & 1 1 & 0 end {pmatrix}} {F_ {k + 1} zvolit F_ {k}} }$

alternativně označeno

${ displaystyle { vec {F}} _ {k + 1} = mathbf {A} { vec {F}} _ {k},}$

který přináší ${ displaystyle { vec {F}} _ {n} = mathbf {A} ^ {n} { vec {F}} _ {0}}$. The vlastní čísla matice A jsou ${ displaystyle varphi = { frac {1} {2}} (1 + { sqrt {5}})}$ a ${ displaystyle - varphi ^ {- 1} = { frac {1} {2}} (1 - { sqrt {5}})}$ odpovídající příslušnému vlastní vektory

${ displaystyle { vec { mu}} = { varphi vyberte 1}}$

a

${ displaystyle { vec { nu}} = {- varphi ^ {- 1} vyberte 1}.}$

Protože počáteční hodnota je

${ displaystyle { vec {F}} _ {0} = {1 zvolit 0} = { frac {1} { sqrt {5}}} { vec { mu}} - { frac {1 } { sqrt {5}}} { vec { nu}},}$

z toho vyplývá, že nth termín je

${ displaystyle { begin {aligned} { vec {F}} _ {n} & = { frac {1} { sqrt {5}}} A ^ {n} { vec { mu}} - { frac {1} { sqrt {5}}} A ^ {n} { vec { nu}} & = { frac {1} { sqrt {5}}} varphi ^ {n } { vec { mu}} - { frac {1} { sqrt {5}}} (- varphi) ^ {- n} { vec { nu}} ~ & = { cfrac {1} { sqrt {5}}} vlevo ({ cfrac {1 + { sqrt {5}}} {2}} vpravo) ^ {n} { varphi vyberte 1} - { cfrac {1} { sqrt {5}}} vlevo ({ cfrac {1 - { sqrt {5}}} {2}} vpravo) ^ {n} {- varphi ^ {- 1} zvolit 1}, end {zarovnáno}}}$

Z toho je nten prvek v řadě Fibonacci lze číst přímo jako a uzavřený výraz:

${ displaystyle F_ {n} = { cfrac {1} { sqrt {5}}} vlevo ({ cfrac {1 + { sqrt {5}}} {2}} vpravo) ^ {n} - { cfrac {1} { sqrt {5}}} vlevo ({ cfrac {1 - { sqrt {5}}} {2}} vpravo) ^ {n}.}$

Stejný výpočet může ekvivalentně provést diagonalizace z A prostřednictvím jeho použití vlastní složení:

${ displaystyle { begin {aligned} A & = S Lambda S ^ {- 1}, A ^ {n} & = S Lambda ^ {n} S ^ {- 1}, end {aligned}} }$

kde ${ displaystyle Lambda = { begin {pmatrix} varphi & 0 0 & - varphi ^ {- 1} end {pmatrix}}}$ a ${ displaystyle S = { begin {pmatrix} varphi & - varphi ^ {- 1} 1 & 1 end {pmatrix}}.}$Uzavřený výraz pro nprvní prvek v řadě Fibonacci je tedy dán vztahem

${ displaystyle { begin {aligned} {F_ {n + 1} zvolit F_ {n}} & = A ^ {n} {F_ {1} zvolit F_ {0}} & = S Lambda ^ {n} S ^ {- 1} {F_ {1} zvolte F_ {0}} & = S { begin {pmatrix} varphi ^ {n} & 0 0 & (- varphi) ^ {- n} end {pmatrix}} S ^ {- 1} {F_ {1} zvolte F_ {0}} & = { begin {pmatrix} varphi & - varphi ^ {- 1} 1 & 1 end {pmatrix}} { begin {pmatrix} varphi ^ {n} & 0 0 & (- varphi) ^ {- n} end {pmatrix}} { frac {1} { sqrt {5} }} { begin {pmatrix} 1 & varphi ^ {- 1} - 1 & varphi end {pmatrix}} {1 zvolit 0}, end {zarovnáno}}}$

což opět přináší

${ displaystyle F_ {n} = { cfrac { varphi ^ {n} - (- varphi) ^ {- n}} { sqrt {5}}}.}$

Matice A má určující -1, a tedy je to 2 × 2 unimodulární matice.

Tuto vlastnost lze chápat ve smyslu pokračující zlomek reprezentace zlatého řezu:

${ displaystyle varphi = 1 + { cfrac {1} {1 + { cfrac {1} {1 + { cfrac {1} {1+ ddots}}}}}}}$

Fibonacciho čísla se vyskytují jako poměr po sobě jdoucích konvergentů pokračující frakce pro φa matice vytvořená z po sobě jdoucích konvergentů jakékoli pokračující frakce má determinant +1 nebo -1. Maticová reprezentace poskytuje následující uzavřený výraz pro čísla Fibonacci:

${ displaystyle { begin {pmatrix} 1 & 1 1 & 0 end {pmatrix}} ^ {n} = { begin {pmatrix} F_ {n + 1} & F_ {n} F_ {n} & F_ {n- 1} end {pmatrix}}.}$

Vezmeme-li determinant obou stran této rovnice, získáme to Cassiniho identita,

${ displaystyle (-1) ^ {n} = F_ {n + 1} F_ {n-1} -F_ {n} ^ {2}.}$

Navíc od té doby Aⁿ A^m = A^n+m pro jakoukoli čtvercovou matici A, lze odvodit následující identity (jsou získány ze dvou různých koeficientů maticového produktu a jeden může snadno odvodit druhý z prvního změnou n do n + 1),

${ displaystyle { begin {aligned} {F_ {m}} {F_ {n}} + {F_ {m-1}} {F_ {n-1}} & = F_ {m + n-1}, F_ {m} F_ {n + 1} + F_ {m-1} F_ {n} & = F_ {m + n}. End {zarovnáno}}}$

Zejména s m = n,

${ displaystyle { begin {zarovnáno} F_ {2n-1} & = F_ {n} ^ {2} + F_ {n-1} ^ {2} F_ {2n} & = (F_ {n-1 } + F_ {n + 1}) F_ {n} & = (2F_ {n-1} + F_ {n}) F_ {n}. End {zarovnáno}}}$

Tyto poslední dvě identity poskytují způsob výpočtu Fibonacciho čísel rekurzivně v Ó(log (n)) aritmetické operace a v čase Ó(M(n) log (n)), kde M(n) je čas pro násobení dvou čísel n číslice. To odpovídá času pro výpočet nth Fibonacciho číslo z maticového vzorce v uzavřené formě, ale s méně redundantními kroky, pokud se člověk vyhne přepočítání již vypočítaného Fibonacciho čísla (rekurze s memorování ).^[55]

Identifikace

Může vyvstat otázka, zda kladné celé číslo X je Fibonacciho číslo. To platí tehdy a jen tehdy, pokud alespoň jeden z ${ displaystyle 5x ^ {2} +4}$ nebo ${ displaystyle 5x ^ {2} -4}$ je perfektní čtverec.^[56] Je to proto, že Binetův vzorec výše lze přeskupit dát

${ displaystyle n = log _ { varphi} left ({ frac {F_ {n} { sqrt {5}} + { sqrt {5F_ {n} ^ {2} pm 4}}} { 2}} vpravo),}$

což umožňuje najít pozici v pořadí daného Fibonacciho čísla.

Tento vzorec musí vrátit celé číslo pro všechny n, takže radikální výraz musí být celé číslo (jinak logaritmus nevrátí ani racionální číslo).

Kombinatorické identity

Většinu identit zahrnujících Fibonacciho čísla lze prokázat pomocí kombinatorické argumenty díky tomu, že F_n lze interpretovat jako počet sekvencí 1 s a 2 s, které se sčítají n - 1. Lze to brát jako definici F_n, s konvencí, že F₀ = 0, což znamená, že žádný součet nepřesahuje -1, a to F₁ = 1, což znamená, že prázdný součet se "sčítá" na 0. Zde záleží na pořadí součtu. Například 1 + 2 a 2 + 1 jsou považovány za dva různé součty.

Například relace opakování

${ displaystyle F_ {n} = F_ {n-1} + F_ {n-2},}$

nebo slovy, nth Fibonacciho číslo je součet předchozích dvou Fibonacciho čísel, lze je ukázat vydělením F_n součty 1 s a 2 s, které se přidají k n - 1 do dvou nepřekrývajících se skupin. Jedna skupina obsahuje součty, jejichž první člen je 1 a druhá součty, jejichž první člen je 2. V první skupině se zbývající členy přidávají k n - 2, takže má F_n-1 součty a ve druhé skupině se zbývající pojmy přidávají n - 3, takže existují F_n−2 částky. Existuje tedy celkem F_n−1 + F_n−2 celkem, což ukazuje, že se to rovná F_n.

Podobně lze ukázat, že součet prvních čísel Fibonacci až do nth se rovná (n + 2) -nd Fibonacciho číslo minus 1.^[57] V symbolech:

${ displaystyle sum _ {i = 1} ^ {n} F_ {i} = F_ {n + 2} -1}$

To se dělí vydělením součtů n + 1 jiným způsobem, tentokrát podle umístění prvního 2. Konkrétně první skupina se skládá ze součtů, které začínají 2, druhá skupina z těch, které začínají 1 + 2, třetí 1 + 1 + 2, a tak dále, až do poslední skupiny, která se skládá z jediného součtu, kde jsou použity pouze 1. Počet součtů v první skupině je F(n), F(n - 1) ve druhé skupině atd., S 1 součtem v poslední skupině. Takže celkový počet součtů je F(n) + F(n − 1) + ... + F(1) + 1, a proto se toto množství rovná F(n + 2).

Podobný argument, který seskupuje součty podle polohy první 1 místo první 2, dává další dvě identity:

${ displaystyle sum _ {i = 0} ^ {n-1} F_ {2i + 1} = F_ {2n}}$

a

${ displaystyle sum _ {i = 1} ^ {n} F_ {2i} = F_ {2n + 1} -1.}$

Slovy, součet prvních Fibonacciho čísel s lichým indexem až F_2n−1 je (2n) th Fibonacciho číslo a součet prvních Fibonacciho čísel se sudým indexem až F_2n je (2n + 1) Fibonacciho číslo minus 1.^[58]

Může být použit jiný trik k prokázání

${ displaystyle sum _ {i = 1} ^ {n} {F_ {i}} ^ {2} = F_ {n} F_ {n + 1},}$

nebo slovy součet čtverců prvních čísel Fibonacci až F_n je produktem nth a (n + 1) th Fibonacciho čísla. V tomto případě Fibonacciho obdélník velikosti F_n podle F(n + 1) lze rozložit na čtverce velikosti F_n, F_n−1a tak dále F₁ = 1, z čehož vyplývá identita porovnáním oblastí.

Symbolická metoda

Sekvence ${ displaystyle (F_ {n}) _ {n in mathbb {N}}}$ je také zvažováno použití symbolická metoda.^[59] Přesněji řečeno, tato sekvence odpovídá a specifikovatelná kombinatorická třída. Specifikace této sekvence je ${ displaystyle operatorname {Seq} ({ mathcal {Z + Z ^ {2}}})}$. Jak již bylo uvedeno výše, ${ displaystyle n}$-té Fibonacciho číslo se rovná počtu kombinatorické skladby (objednáno oddíly ) z ${ displaystyle n-1}$ s použitím výrazů 1 a 2.

Z toho vyplývá, že obyčejná generující funkce Fibonacciho sekvence, tj. ${ displaystyle sum _ {i = 0} ^ { infty} F_ {i} z ^ {i}}$, je komplexní funkce ${ displaystyle { frac {z} {1-z-z ^ {2}}}}$.

Jiné identity

Pomocí různých metod lze odvodit řadu dalších identit. Mezi nejvýznamnější patří:^[60]

Cassiniho a katalánská identita

Tvrdí to Cassiniho identita

${ displaystyle F_ {n} ^ {2} -F_ {n + 1} F_ {n-1} = (- 1) ^ {n-1}}$

Katalánská identita je zevšeobecněním:

${ displaystyle F_ {n} ^ {2} -F_ {n + r} F_ {n-r} = (- 1) ^ {n-r} F_ {r} ^ {2}}$

d'Ocagnova identita

${ displaystyle F_ {m} F_ {n + 1} -F_ {m + 1} F_ {n} = (- 1) ^ {n} F_ {m-n}}$

${ displaystyle F_ {2n} = F_ {n + 1} ^ {2} -F_ {n-1} ^ {2} = F_ {n} vlevo (F_ {n + 1} + F_ {n-1} right) = F_ {n} L_ {n}}$

kde L_n je n 'th Lucasovo číslo. Poslední je identita pro zdvojnásobení n; jiné identity tohoto typu jsou

${ displaystyle F_ {3n} = 2F_ {n} ^ {3} + 3F_ {n} F_ {n + 1} F_ {n-1} = 5F_ {n} ^ {3} +3 (-1) ^ { n} F_ {n}}$

podle Cassiniho identity.

${ displaystyle F_ {3n + 1} = F_ {n + 1} ^ {3} + 3F_ {n + 1} F_ {n} ^ {2} -F_ {n} ^ {3}}$

${ displaystyle F_ {3n + 2} = F_ {n + 1} ^ {3} + 3F_ {n + 1} ^ {2} F_ {n} + F_ {n} ^ {3}}$

${ displaystyle F_ {4n} = 4F_ {n} F_ {n + 1} vlevo (F_ {n + 1} ^ {2} + 2F_ {n} ^ {2} vpravo) -3F_ {n} ^ { 2} left (F_ {n} ^ {2} + 2F_ {n + 1} ^ {2} right)}$

Ty lze najít experimentálně pomocí mřížková redukce a jsou užitečné při nastavování speciální síto s číselným polem na faktorizovat Fibonacciho číslo.

Obecněji,^[60]

${ displaystyle F_ {kn + c} = součet _ {i = 0} ^ {k} {k vybrat i} F_ {ci} F_ {n} ^ {i} F_ {n + 1} ^ {ki} .}$

nebo alternativně

${ displaystyle F_ {kn + c} = součet _ {i = 0} ^ {k} {k vybrat i} F_ {c + i} F_ {n} ^ {i} F_ {n-1} ^ { ki}.}$

Uvedení k = 2 v tomto vzorci získáme opět vzorce z konce výše uvedené části Maticová forma.

Silová řada

The generující funkce Fibonacciho sekvence je výkonová řada

${ displaystyle s (x) = součet _ {k = 0} ^ { infty} F_ {k} x ^ {k}.}$

Tato řada je konvergentní pro ${ displaystyle | x | <{ frac {1} { varphi}},}$ a jeho součet má jednoduchou uzavřenou formu:^[61]

${ displaystyle s (x) = { frac {x} {1-x-x ^ {2}}}}$

To lze dokázat pomocí Fibonacciho rekurence k rozšíření každého koeficientu v nekonečném součtu:

${ displaystyle { begin {aligned} s (x) & = sum _ {k = 0} ^ { infty} F_ {k} x ^ {k} & = F_ {0} + F_ {1} x + sum _ {k = 2} ^ { infty} left (F_ {k-1} + F_ {k-2} right) x ^ {k} & = x + sum _ {k = 2 } ^ { infty} F_ {k-1} x ^ {k} + sum _ {k = 2} ^ { infty} F_ {k-2} x ^ {k} & = x + x součet _ {k = 0} ^ { infty} F_ {k} x ^ {k} + x ^ {2} součet _ {k = 0} ^ { infty} F_ {k} x ^ {k} & = x + xs (x) + x ^ {2} s (x). end {zarovnáno}}}$

Řešení rovnice

${ displaystyle s (x) = x + xs (x) + x ^ {2} s (x)}$

pro s(X) vede k výše uvedené uzavřené formě.

Nastavení X = 1/k, stává se uzavřená forma série

${ displaystyle sum _ {n = 0} ^ { infty} { frac {F_ {n}} {k ^ {n}}} = { frac {k} {k ^ {2} -k-1 }}.}$

Zejména pokud k je celé číslo větší než 1, pak tato řada konverguje. Další nastavení k = 10^m výnosy

${ displaystyle sum _ {n = 1} ^ { infty} { frac {F_ {n}} {10 ^ {m (n + 1)}}} = { frac {1} {10 ^ {2m } -10 ^ {m} -1}}}$

pro všechna kladná celá čísla m.

Některé matematické logické knihy představují zvláštní hodnotu, z níž pochází m = 1, který je ${ displaystyle { frac {s (1/10)} {10}} = { frac {1} {89}} =. 011235 ldots}$^[62] Podobně, m = 2 dává

${ displaystyle { frac {s (1/100)} {100}} = { frac {1} {9899}} =. 0001010203050813213455 ldots}$

Vzájemné částky

Nekonečné součty přes vzájemná Fibonacciho čísla lze někdy vyhodnotit z hlediska theta funkce. Například můžeme zapsat součet každého lichého indexovaného vzájemného Fibonacciho čísla jako

${ displaystyle sum _ {k = 0} ^ { infty} { frac {1} {F_ {2k + 1}}} = { frac { sqrt {5}} {4}} vartheta _ { 2} ^ {2} left (0, { frac {3 - { sqrt {5}}} {2}} right),}$

a součet čtverců vzájemných Fibonacciho čísel jako

${ displaystyle sum _ {k = 1} ^ { infty} { frac {1} {F_ {k} ^ {2}}} = { frac {5} {24}} vlevo ( vartheta _ {2} ^ {4} left (0, { frac {3 - { sqrt {5}}} {2}} right) - vartheta _ {4} ^ {4} left (0, { frac {3 - { sqrt {5}}} {2}} vpravo) +1 vpravo).}$

Pokud k prvnímu součtu přidáme 1 ke každému Fibonacciho číslu, existuje také uzavřený tvar

${ displaystyle sum _ {k = 0} ^ { infty} { frac {1} {1 + F_ {2k + 1}}} = { frac { sqrt {5}} {2}},}$

a tam je vnořené součet čtverců Fibonacciho čísel, který dává převrácenou hodnotu z Zlatý řez,

${ displaystyle sum _ {k = 1} ^ { infty} { frac {(-1) ^ {k + 1}} { sum _ {j = 1} ^ {k} {F_ {j}} ^ {2}}} = { frac {{ sqrt {5}} - 1} {2}}.}$

Žádný uzavřený vzorec pro reciproční Fibonacciho konstanta

${ displaystyle psi = sum _ {k = 1} ^ { infty} { frac {1} {F_ {k}}} = 3,359885666243 dots}$

je známo, ale počet byl prokázán iracionální podle Richard André-Jeannin.^[63]

The Millinova řada dává identitu^[64]

${ displaystyle sum _ {n = 0} ^ { infty} { frac {1} {F_ {2 ^ {n}}}} = { frac {7 - { sqrt {5}}} {2 }},}$

který vyplývá z uzavřené formy pro její dílčí součty jako N inklinuje k nekonečnu:

${ displaystyle sum _ {n = 0} ^ {N} { frac {1} {F_ {2 ^ {n}}}} = 3 - { frac {F_ {2 ^ {N} -1}} {F_ {2 ^ {N}}}}.}$

Prvočísla a dělitelnost

Vlastnosti dělitelnosti

Každé třetí číslo sekvence je sudé a obecněji každé kčíslo sekvence je násobkem F_k. Fibonacciho sekvence je tedy příkladem a posloupnost dělitelnosti. Fibonacciho sekvence ve skutečnosti splňuje silnější vlastnost dělitelnosti^[65][66]

${ displaystyle gcd (F_ {m}, F_ {n}) = F _ { gcd (m, n)}.}$

Jakákoli tři po sobě jdoucí čísla Fibonacci jsou párová coprime, což znamená, že pro každého n,

gcd (F_n, F_n+1) = gcd (F_n, F_n+2) = gcd (F_n+1, F_n+2) = 1.

Každé prvočíslo p vydělí Fibonacciho číslo, které lze určit hodnotou p modulo 5. Pokud p je tedy shodné s 1 nebo 4 (mod 5) p rozděluje F_p − 1, a pokud p je shodný s 2 nebo 3 (mod 5), pak, p rozděluje F_p + 1. Zbývající případ je takový p = 5, a v tomto případě p rozděluje F_p.

${ displaystyle { begin {cases} p = 5 & Rightarrow p mid F_ {p}, p equiv pm 1 { pmod {5}} & Rightarrow p mid F_ {p-1}, p equiv pm 2 { pmod {5}} & Rightarrow p mid F_ {p + 1}. end {cases}}}$

Tyto případy lze kombinovat do jednoho,po částech vzorec pomocí Legendární symbol:^[67]

${ displaystyle p mid F_ {p- left ({ frac {5} {p}} right)}.}$

Testování originality

Výše uvedený vzorec lze použít jako test primality v tom smyslu, že pokud

${ displaystyle n mid F_ {n- left ({ frac {5} {n}} right)},}$

kde byl symbol Legendre nahrazen symbolem Jacobi symbol, pak je to důkaz, že n je prvočíslo, a pokud nedokáže držet, pak n rozhodně není vrchol. Li n je složený a splňuje vzorec n je Fibonacciho pseudoprime. Když m je velké - řekněme 500bitové číslo - pak můžeme vypočítat F_m (mod n) efektivně využívající maticovou formu. Tím pádem

${ displaystyle { begin {pmatrix} F_ {m + 1} & F_ {m} F_ {m} & F_ {m-1} end {pmatrix}} equiv { begin {pmatrix} 1 & 1 1 & 0 konec {pmatrix}} ^ {m} { pmod {n}}.}$

Zde je síla matice A^m se počítá pomocí modulární umocňování, který může být přizpůsobeno maticím.^[68]

Fibonacciho prvočísla

A Fibonacci prime je Fibonacciho číslo primární. Prvních pár je:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ... OEIS: A005478.

Byly nalezeny Fibonacciho prvočísla s tisíci číslic, ale není známo, zda jich je nekonečně mnoho.^[69]

F_kn je dělitelné F_n, takže kromě F₄ = 3, jakýkoli Fibonacciho prime musí mít index prime. Jak jsou libovolně dlouhá běhy složená čísla, proto existují také libovolně dlouhé řady složených Fibonacciho čísel.

No Fibonacci number greater than F₆ = 8 is one greater or one less than a prime number.^[70]

The only nontrivial náměstí Fibonacci number is 144.^[71] Attila Pethő proved in 2001 that there is only a finite number of perfect power Fibonacci numbers.^[72] In 2006, Y. Bugeaud, M. Mignotte, and S. Siksek proved that 8 and 144 are the only such non-trivial perfect powers.^[73]

1, 3, 21, 55 are the only triangular Fibonacci numbers, which was conjectured by Vern Hoggatt and proved by Luo Ming.^[74]

No Fibonacci number can be a perfektní číslo.^[75] More generally, no Fibonaci number other than 1 can be multiply perfect,^[76] and no ratio of two Fibonacci numbers can be perfect.^[77]

Prime divisors

With the exceptions of 1, 8 and 144 (F₁ = F₂, F₆ a F₁₂) every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number (Carmichaelova věta ).^[78] As a result, 8 and 144 (F₆ a F₁₂) are the only Fibonacci numbers that are the product of other Fibonacci numbers OEIS: A235383.

The divisibility of Fibonacci numbers by a prime p souvisí s Legendární symbol ${displaystyle left({ frac {p}{5}} ight)}$ which is evaluated as follows:

${displaystyle left({frac {p}{5}} ight)={egin{cases}0&{ ext{if }}p=51&{ ext{if }}pequiv pm 1{pmod {5}}-1&{ ext{if }}pequiv pm 2{pmod {5}}.end{cases}}}$

Li p is a prime number then

${displaystyle F_{p}equiv left({frac {p}{5}} ight){pmod {p}}quad { ext{and}}quad F_{p-left({frac {p}{5}} ight)}equiv 0{pmod {p}}.}$^[79][80]

Například,

${displaystyle {egin{aligned}({ frac {2}{5}})&=-1,&F_{3}&=2,&F_{2}&=1,({ frac {3}{5}})&=-1,&F_{4}&=3,&F_{3}&=2,({ frac {5}{5}})&=0,&F_{5}&=5,({ frac {7}{5}})&=-1,&F_{8}&=21,&F_{7}&=13,({ frac {11}{5}})&=+1,&F_{10}&=55,&F_{11}&=89.end{aligned}}}$

It is not known whether there exists a prime p takhle

${displaystyle F_{p-left({frac {p}{5}} ight)}equiv 0{pmod {p^{2}}}.}$

Such primes (if there are any) would be called Zeď – Slunce – Slunce připravuje.

Také pokud p ≠ 5 is an odd prime number then:^[81]

${displaystyle 5F_{frac {ppm 1}{2}}^{2}equiv {egin{cases}{ frac {1}{2}}left(5left({frac {p}{5}} ight)pm 5 ight){pmod {p}}&{ ext{if }}pequiv 1{pmod {4}}{ frac {1}{2}}left(5left({frac {p}{5}} ight)mp 3 ight){pmod {p}}&{ ext{if }}pequiv 3{pmod {4}}.end{cases}}}$

Příklad 1. p = 7, in this case p ≡ 3 (mod 4) and we have:

${displaystyle ({ frac {7}{5}})=-1:qquad { frac {1}{2}}left(5({ frac {7}{5}})+3 ight)=-1,quad { frac {1}{2}}left(5({ frac {7}{5}})-3 ight)=-4.}$

${displaystyle F_{3}=2{ ext{ and }}F_{4}=3.}$

${displaystyle 5F_{3}^{2}=20equiv -1{pmod {7}};;{ ext{ and }};;5F_{4}^{2}=45equiv -4{pmod {7}}}$

Příklad 2. p = 11, in this case p ≡ 3 (mod 4) and we have:

${displaystyle ({ frac {11}{5}})=+1:qquad { frac {1}{2}}left(5({ frac {11}{5}})+3 ight)=4,quad { frac {1}{2}}left(5({ frac {11}{5}})-3 ight)=1.}$

${displaystyle F_{5}=5{ ext{ and }}F_{6}=8.}$

${displaystyle 5F_{5}^{2}=125equiv 4{pmod {11}};;{ ext{ and }};;5F_{6}^{2}=320equiv 1{pmod {11}}}$

Příklad 3. p = 13, in this case p ≡ 1 (mod 4) and we have:

${displaystyle ({ frac {13}{5}})=-1:qquad { frac {1}{2}}left(5({ frac {13}{5}})-5 ight)=-5,quad { frac {1}{2}}left(5({ frac {13}{5}})+5 ight)=0.}$

${displaystyle F_{6}=8{ ext{ and }}F_{7}=13.}$

${displaystyle 5F_{6}^{2}=320equiv -5{pmod {13}};;{ ext{ and }};;5F_{7}^{2}=845equiv 0{pmod {13}}}$

Příklad 4. p = 29, in this case p ≡ 1 (mod 4) and we have:

${displaystyle ({ frac {29}{5}})=+1:qquad { frac {1}{2}}left(5({ frac {29}{5}})-5 ight)=0,quad { frac {1}{2}}left(5({ frac {29}{5}})+5 ight)=5.}$

${displaystyle F_{14}=377{ ext{ and }}F_{15}=610.}$

${displaystyle 5F_{14}^{2}=710645equiv 0{pmod {29}};;{ ext{ and }};;5F_{15}^{2}=1860500equiv 5{pmod {29}}}$

For odd n, all odd prime divisors of F_n are congruent to 1 modulo 4, implying that all odd divisors of F_n (as the products of odd prime divisors) are congruent to 1 modulo 4.^[82]

Například,

${displaystyle F_{1}=1,F_{3}=2,F_{5}=5,F_{7}=13,F_{9}=34=2cdot 17,F_{11}=89,F_{13}=233,F_{15}=610=2cdot 5cdot 61.}$

All known factors of Fibonacci numbers F(i) for all i < 50000 are collected at the relevant repositories.^[83][84]

Periodicity modulo n

If the members of the Fibonacci sequence are taken mod n, the resulting sequence is periodicky with period at most 6n.^[85] The lengths of the periods for various n form the so-called Pisano periods OEIS: A001175. Determining a general formula for the Pisano periods is an open problem, which includes as a subproblem a special instance of the problem of finding the multiplikativní pořadí a modular integer or of an element in a konečné pole. However, for any particular n, the Pisano period may be found as an instance of detekce cyklu.

Right triangles

Starting with 5, every second Fibonacci number is the length of the hypotenuse of a right triangle with integer sides, or in other words, the largest number in a Pytagorejský trojnásobek. The length of the longer leg of this triangle is equal to the sum of the three sides of the preceding triangle in this series of triangles, and the shorter leg is equal to the difference between the preceding bypassed Fibonacci number and the shorter leg of the preceding triangle.

The first triangle in this series has sides of length 5, 4, and 3. Skipping 8, the next triangle has sides of length 13, 12 (5 + 4 + 3), and 5 (8 − 3). Skipping 21, the next triangle has sides of length 34, 30 (13 + 12 + 5), and 16 (21 − 5). This series continues indefinitely. The triangle sides A, b, C can be calculated directly:

${displaystyle {egin{aligned}a_{n}&=F_{2n-1}=F_{n}^{2}+F_{n-1}^{2}[4pt]b_{n}&=2F_{n}F_{n-1}[4pt]c_{n}&=F_{n}^{2}-F_{n-1}^{2}=F_{n+1}F_{n-2}.end{aligned}}}$

These formulas satisfy ${displaystyle a_{n}^{2}=b_{n}^{2}+c_{n}^{2}}$ pro všechny n, but they only represent triangle sides when n > 2.

Any four consecutive Fibonacci numbers F_n, F_n+1, F_n+2 a F_n+3 can also be used to generate a Pythagorean triple in a different way:^[86]

${displaystyle {egin{aligned}a_{n}&=F_{n+1}^{2}+F_{n+2}^{2}_{n}&=2F_{n+1}F_{n+2}c_{n}&=F_{n}F_{n+3}.end{aligned}}}$

These formulas satisfy ${displaystyle a_{n}^{2}=b_{n}^{2}+c_{n}^{2}}$ pro všechny n, but they only represent triangle sides when n > 0.

Velikost

Od té doby F_n je asymptotické na ${displaystyle varphi ^{n}/{sqrt {5}}}$, the number of digits in F_n is asymptotic to ${displaystyle nlog _{10}varphi approx 0.2090,n}$. As a consequence, for every integer d > 1 there are either 4 or 5 Fibonacci numbers with d decimal digits.

More generally, in the base b representation, the number of digits in F_n is asymptotic to ${displaystyle nlog _{b}varphi .}$

Zobecnění

The Fibonacci sequence is one of the simplest and earliest known sequences defined by a relace opakování, and specifically by a lineární diferenční rovnice. All these sequences may be viewed as generalizations of the Fibonacci sequence. In particular, Binet's formula may be generalized to any sequence that is a solution of a homogeneous linear difference equation with constant coefficients.

Some specific examples that are close, in some sense, from Fibonacci sequence include:

• Generalizing the index to negative integers to produce the negafibonacci čísla.
• Generalizing the index to real numbers using a modification of Binet's formula.^[60]
• Starting with other integers. Lucas numbers mít L₁ = 1, L₂ = 3 a L_n = L_n−1 + L_n−2. Primefree sequences use the Fibonacci recursion with other starting points to generate sequences in which all numbers are kompozitní.
• Letting a number be a linear function (other than the sum) of the 2 preceding numbers. The Pell čísla mít P_n = 2P_{n − 1} + P_{n − 2}. If the coefficient of the preceding value is assigned a variable value X, the result is the sequence of Fibonacciho polynomy.
• Not adding the immediately preceding numbers. The Padovan sekvence a Perrinova čísla mít P(n) = P(n − 2) + P(n − 3).
• Generating the next number by adding 3 numbers (tribonacci numbers), 4 numbers (tetranacci numbers), or more. The resulting sequences are known as n-Step Fibonacci numbers.^[87]

Viz také

Reference

Poznámky pod čarou

Citace