Fibonaccijevo število

Iz Wikipedije, proste enciklopedije

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} 0;\,\qquad\qquad\qquad\quad\,\ \ \,&&n=0\,;\ \ \\ 1;\qquad\qquad\qquad\qquad\,&&n=1;\ \ \,\\ F(n-2)+F(n-1);&&\mbox{sicer.} \end{matrix} \right.$

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

Pokritje ravnine s kvadrati v velikosti Fibonaccijevih števil

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.

[uredi] 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 lastnosti. Zato funkciji φⁿ in (1-φ)ⁿ tvorita novo bazo istega prostora.

Z nastavitvijo koeficientov za primerne začetne vrednosti F(0) = 0 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.

[uredi] 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 natanč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 0 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.

[uredi] 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.

[uredi] 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.

[uredi] 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}