Fibonaccijevo število

Fibonaccijeva števila, ki določajo Fibonaccijevo zaporedje, so v matematiki rekurzivno določena z naslednjimi enačbami:

$F_{n}\equiv F(n)=\left\{{\begin{matrix}1;\,\qquad \qquad \qquad \quad \,\ \ \,&&n=0\,;\ \ \\1;\qquad \qquad \qquad \qquad \,&&n=1;\ \ \,\\F(n-2)+F(n-1);&&n>1.\end{matrix}}\right.$

Zaporedje začnemo z dvema številoma, običajno 1 in 1. Naslednje Fibonaccijevo število dobimo, če seštejemo predhodni. Prva Fibonaccijeva števila so (OEIS A000045):

$F_{0}\,$	$F_{1}\,$	$F_{2}\,$	$F_{3}\,$	$F_{4}\,$	$F_{5}\,$	$F_{6}\,$	$F_{7}\,$	$F_{8}\,$	$F_{9}\,$	$F_{10}\,$	$F_{11}\,$	$F_{12}\,$	$F_{13}\,$	$F_{14}\,$	$F_{15}\,$	$F_{16}\,$	$F_{17}\,$	$F_{18}\,$	$F_{19}\,$	$F_{20}\,$	$F_{21}\,$
1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765	10946	17711

Pokritje ravnine s kvadrati v velikosti Fibonaccijevih števil

Jupana (kečuansko za orodje za štetje) je računalo, ki so ga uporabljali Inki. Raziskovalci menijo da so računi temeljili na Fibonaccijevih številih da se je zmanjšalo število potrebnih zrn na polje.

Fibonaccijeva spirala tvorjena z risanjem lokov, ki povezujejo nasprotni oglišči kvadratov v Fibonaccijevem pokritju. Tu so kvadrati velikosti 1, 1, 2, 3, 5, 8, 13, 21 in 34; glej zlata spirala

Stran iz Fibonaccijevega dela Knjiga o abaku (Liber Abaci; Narodna osrednja knjižnica v Firencah) prikazuje Fibonaccijevo zaporedje (uokvirjeno desno) s členi od 0 do 12 označenimi s črno z rimskimi in z vrednostmi označenimi z rdečo z indoarabskimi številkami

Fibonaccijevo zaporedje zvokovno, harmonični intervali naraščajo, melodični pa padajo.

To zaporedje je prvi opisal Leonardo Fibonacci pri opisu rasti določenega števila zajcev. Števila opisujejo število parov idealiziranega števila zajcev po n mesecih, če upoštevamo:

• prvi mesec se rodi samo en nov par,
• novorojeni pari so plodni od svojega drugega meseca naprej,
• vsak mesec vsak ploden par zaplodi nov par in
• zajci nikoli ne umrejo.

Enačba

Izraz Fibonaccijevega zaporedja lahko uporabimo splošneje na vsaki funkciji g, kjer je g(n + 2) = g(n) + g(n + 1). Te funkcije so natanko tiste oblike g(n) = aF(n) + bF(n + 1) za poljubna števila a in b, tako da Fibonaccijeva zaporedja tvorijo vektorski prostor s funkcijami F(n) in F(n + 1) kot baza.

Kot je pokazal Kepler, stopnja rasti Fibonaccijevih števil, F(n + 1) / F(n), konvergira k številu zlatega reza, označenem z φ. To je pozitivni koren kvadratne enačbe x² - x - 1 = 0, tako da je φ² = φ + 1. Če pomnožimo obe strani z φⁿ, dobimo φⁿ⁺² = φⁿ⁺¹ + φⁿ, in je funkcija φⁿ Fibonaccijevo zaporedje. Lahko se pokaže, da ima negativni koren kvadratne enačbe, 1 - φ, enake značilnosti. Zato funkciji φⁿ in (1-φ)ⁿ tvorita novo bazo istega prostora.

Z nastavitvijo koeficientov za primerne začetne vrednosti F(0) = 1 in F(1) = 1, dobimo:

$F\left(n\right)={\phi ^{n} \over {\sqrt {5}}}-{(1-\phi )^{n} \over {\sqrt {5}}}.$

Isti rezultat dobimo, če uporabimo postopke rodovnih funkcij ali reševanja linearnih rekurenčnih enačb.

Ko gre n v neskončnost, drugi člen konvergira proti nič, tako, da Fibonaccijeva števila težijo k eksponentu φⁿ / √5, in zaradi tega njihova razmerja konvergirajo. V bistvu je drugi člen dovolj majhen in lahko dobimo Fibonaccijeva števila samo iz prvega člena, če jih zaokrožamo na najbližje celo število.

Računanje Fibonaccijevih števil

Računanje Fibonaccijevih števil z računanjem potenc števila zlatega reza ni preveč praktično, razen za majhne vrednosti n, ker se bodo zaokrožitvene napake povečale in števila s tekočo vejico po navadi niso dovolj točna.

Tudi neposredna rekurzivna uporaba določitve Fibonaccijevega zaporedja ni preveč prikladna, ker moramo računati preveč vrednosti zaporedoma (razen če programski jezik dovoljuje shrambo predhodnih vrednosti fukcije). Zato po navadi računamo Fibonaccijeva števila od spodaj navzgor. Začnemo z vrednostima 1 in 1, potem pa izmenoma zamenjujemo prvo število z drugim, drugo število pa z vsoto prejšnjih dveh.

Za velike vrednosti in, če uporabimo programski jezik z možnostjo računanja velikih števil, je hitrejša pot računanja Fibonaccijevih števil z naslednjo matrično enačbo:

${\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F\left(n+1\right)&F\left(n\right)\\F\left(n\right)&F\left(n-1\right)\end{bmatrix}},$

ki namesto potenciranja uporablja kvadriranje.

Uporabe

Fibonaccijeva števila so pomembna pri analizi poteka Evklidovega algoritma za določitev največjega skupnega delitelja dveh celih števil. Izkaže se, da se algoritem najslabše izkaže ravno v primeru, ko določamo največji skupni delitelj dveh zaporednih Fibonaccijevih števil.

Matijasevič je pokazal, da lahko Fibonaccijeva števila določimo s posebno diofantsko enačbo, kar nas vodi do njegove izvirne rešitve 10. Hilbertovega problema.

Fibonaccijeva števila se pojavijo v enačbi za diagonale Pascalovega trikotnika.

Zanimiva uporaba Fibonaccijevega zaporedja je pri pretvarjanju milj v kilometre. Na primer, če bi radi vedeli koliko kilometrov je 5 milj, vzamemo Fibonaccijevo število (5) in poiščemo naslednje (8). 5 milj je približno 8 kilometrov. To deluje ker je pretvorbeni količnik med miljami in kilometri približno enak φ.

Logaritmično spiralo lahko poenostavimo, če začnemo v središču kartezičnega koordinatnega sestava, se premaknemo za F(1) enot v desno, za F(2) enot navzgor, za F(3) enot v levo, za F(4) enot navzdol, za F(5) enot v desno in tako naprej. To je podobno konstrukciji, omenjeni v članku o zlatem rezu. Fibonaccijeva števila se v naravi pojavijo velikokrat, kadar so logaritmične spirale sestavljene iz nezveznih enot, kot so tiste pri sončnicah ali pri borovih storžih.

Posplošitve

Posplošitev Fibonaccijevega zaporedja so Lucasova zaporedja. Eno vrsto lahko določimo z:

L(0) = 0

L(1) = 1

L(n+2) = PL(n+1) + QL(n)

kjer je običajno Fibonaccijevo zaporedje poseben primer P = Q = 1. Druga vrsta Lucasovega zaporedja se začne z L(0) = 2, L(1) = P. Takšna zaporedja se uporabljajo v teoriji števil in dokazovanju praštevilskosti.

Algoritem

V pascalu lahko rekurzivni postopek prepišemo neposredno:

function F(n:integer):integer;
begin
  if (n=0) or (n=1) then 
    F := 1
  else
    F := F(n-1) + F(n-2);
end;{F}

Vendar je taka neposredna uporaba rekurzije zelo neučinkovita in pravzaprav služi kot šolski primer, kako je ne smemo uporabljati. Učinkovitejši je iterativni postopek:

function F(n:integer):integer;
var a,b,c,j : integer;
begin
  a:=1; b:=1;
  for j:=3 to n do begin
    c := a+b;  a := b;  b := c;
  end;
  F := c;
end;{F}

V javi (kot metoda) bi algoritem zgledal tako:

static int fibonacci (int n) {	
  int f=0,f1=1,f2=1;
  for (int i=1; i<=n;i++) {
    if (i<3) f=1;
    else {
	f=f1+f;
	f1=f2;
	f2=f;
    }
}

V Pythonu, kot funkcija, bi algoritem zgledal tako:

def fibonacci(n):
    if n < 3:
        return 1

    f1, f2 = 1, 1
    for _ in range(3, n + 1):
        f1, f2 = f2, f1 + f2
    return f2

Fibonaccijeva števila v naravi

Sončnica ima cvetove razporejene v dve družini, pri čemer je v eni 34 spiralnih zavojev, v drugi pa 55 zavojev. (glej tudi Fermatova spirala)

Glava cvetlice barvilna pasja kamilica (Cota tinctoria) kaže postavitev 21-ih (modro) in 13-ih (zelenomodro) spiralnih zavojev

Poleg rasti določenega števila zajcev so Fibonaccijeva števila tudi drugod v naravi, npr. pri številu venčnih listov in v spiralnih strukturah, ki jih mnoge rastline uporabljajo za razporeditev semen (glej tudi Fermatova spirala). Poleg števila parov zajcev je znan primer tudi število čebel pri idealiziranemu razmnoževanju, če upoštevamo da:

• se iz neoplojenega jajčeca izvali samec,
• se iz jajčeca, ki ga oplodi samec, izvali samica.

Samec bo tako vedno imel enega starša, samica pa dva. Če analiziramo število prednikov kateregakoli samca (1), bo ta imel vedno enega starša, tj. samico (1). Slednja ima dva starša, samca in samico (2), ta samec pa bo prav tako imel enega starša in samica dva starša, kar da število 3. V praksi se še danes uporablja izpopolnjene različice Fibonaccijeve sheme pri preučevanju drugih živalskih populacij.

Pri nekaterih cvetnicah so ta števila jasno izražena pri venčnih listih. Tako imajo lilije 3 venčne liste, zlatice 5, ostrožniki pogosto 8, ognjič 13, astre 21 in marjetice ter sončnice navadno po 34, 55 ali 89 listov. Lahko se pojavijo manj običajna števila, in sicer dvojna Fibonaccijeva števila, kar je posledica tehnike gojenja rastlin, ki podvoji število listov, ali pa podobna nepravilna zaporedja (npr. 1, 3, 4, 7, 18, ...). Pri razporeditvi semen so znani primer sončnice, ki imajo semena razporejena v dve družini, pri čemer je v manjših sončnicah v eni družini 34 spiralnih zavojev, v drugi pa 55, pri večjih pa sta ti dve števili 55 in 89 ali 89 in 144. Tudi luske na jelovih storžih so tipično razporejene v dveh družinah prepletenih spiral; storž norveške jelke ima tako 5 zavojev lusk v eni družini, v drugi pa 3.

Fibonaccijeva števila v leposlovju

Fibonaccijeva števila je uporabil Dan Brown v svoji knjigi Da Vincijeva šifra.

Glej tudi

• obratna Fibonaccijeva konstanta

Viri

• Douady, S; Couder, Y. (1996). »Phyllotaxis as a Dynamical Self Organizing Process« (PDF). Journal of Theoretical Biology. Zv. 178, št. 178. str. 255–274. doi:10.1006/jtbi.1996.0026. Arhivirano iz prvotnega spletišča (PDF) dne 26. maja 2006. Pridobljeno 3. decembra 2009.
• Knott, Ron (1996–2011), »Fib table«, Fibonacci (v angleščini), Združeno kraljestvo: Surrey, pridobljeno 10. maja 2013. Stran navaja prvih 300 Fibonaccijevih števil 300 F_n razstavljenih na prafaktorje in povezavami na druge obsežnejše razpredelnice.
• Prusinkiewicz, P.; Lindenmayer, A. (1990). The Algorithmic Beauty of Plants. Springer-Verlag. str. 101–107. ISBN 978-0387972978.