Fibonacci jada

Fibonacci jada on arvude jada, mille kaks esimest liiget on vastavalt F₁=0 ja F₂=1 ning iga järgnev liige on kahe eelneva liikme summa. Jada esimesed liikmed on

$0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;233,\;377,\;610,\ \ldots.$

(esimesed 500 elementi on loetletud siin).

Fibonacci jada {F_n} defineeritakse rekurrentse seosega

$F_n = F_{n-1} + F_{n-2}, \,$

mis lahendatakse algtingimustel

$F_0 = 0, \quad F_1 = 1. \,$

Ajalugu

Teadaolevalt esinevad Fibonacci arvud esmakordselt mātrāmeru nime all Pingala sanskritikeelses käsikirjas Chandaḥśāstra ('Prosoodiakunst'; 450 eKr või 200 eKr).

Aastal 1202 tutvustas seda jada läänemaailmale itaalia matemaatik Leonardo Fibonacci.

Pealiige

Fibonacci arvud on tihedalt seotud kuldlõikega: kui valida piisavalt suur Fibonacci arv, siis on sellele eelnev Fibonacci arv sellest alati ligikaudu kuldlõike suhtarvu pöördväärtus $1/\varphi \approx 0,618$ korda väiksem ning järgnev arv on sellest $\varphi \approx 1,618$ korda suurem.

Viimast väljendab asjaolu, et Fibonacci jada esitub kujul

$F_{n} = \frac{\varphi^{n} - (-\varphi)^{-n}}{\sqrt{5}} = \frac{\varphi^{n} - (1-\varphi)^{n}}{\sqrt{5}},$

kus $\varphi$ on kuldlõike suhtarv. See valem saadakse eeltoodud rekurrentse seose $F_n = F_{n-1} + F_{n-2}$ lahendamisel algtingimustel $F_0 = 0$, $F_1 = 1$.

Fibonacci jada pealiikme valemi tuletamine

Unustame esialgu algtingimused ja otsime rekurrentse võrrandi

$F_{n+2} = F_{n+1} + F_{n} \qquad (1)$

lahendit kujul

$F_{n} = x^n. \,$

Asendades oletatava lahendi võrrandisse (1), saame pärast kõikide suuruste samale poole võrdusmärki viimist ja $x^n$-ga jagamist karakteristliku ruutvõrrandi

$x^2 - x - 1 = 0. \,$

Selle ruutvõrrandi lahendid on

$x_1 = \frac{1 + \sqrt{5}}{2} = \varphi, \quad x_2 = \frac{1 - \sqrt{5}}{2} = 1 - \varphi, \,$

kus $\varphi$ on kuldlõike suhtarv. Et seos (1) on lineaarne, siis on $F_{n}$ üldlahend

$F_n = A \varphi^n + B (1 - \varphi)^n, \qquad (2)$

kus kordajad $A$ ja $B$ leitakse algtingimustest:

$F_0 = 0, \quad F_1 = 1. \qquad (3)$

Asendades üldlahendi (2) algtingimustesse (3), saame lineaarvõrrandisüsteemi

$F_0 = A + B = 0, \quad F_1 = A \varphi + B (1 - \varphi) = 1,$

mille lahendamine annab A ja B väärtused:

$A = - B = \frac{1}{2\varphi - 1} = \frac{1}{\sqrt 5}. \,$

Asendades kordajad A ja B üldlahendisse (2), jõuamegi oodatud tulemuseni

$F_n = \frac{\varphi^{n} - (1-\varphi)^{n}}{\sqrt{5}}. \,$

Loodus

Fibonacci jada võib kohata ka looduses. Näiteks taimede ehituses: et lehed ühtlaselt päikest saaksid, on need paigutunud korrapäraselt. Näiteks kahe kohatkuti lehe vahel on tihti Fibonacci arv lehti. Sama on täheldatud ka käbi kihtide puhul.

Lucas' jada

Vaata ka: Lucas' jada

Lucas' jada liikmed defineeritakse samuti rekursiivselt kahe eelneva liikme summana, kuid selle esimesed liikmed erinevad Fibonacci jada omadest, mistõttu on Lucas' jada Fibonacci jadast erinev. Selle esimesed liikmed on:

$2,\;1,\;3,\;4,\;7,\;11,\;18,\;29,\ \ldots.$

Vaata ka

• Faktoriaal

Välislink

• Iteratiivne Java applet, mis leiab igale sisendile Fibonacci arvu