Ogled vira Fibonaccijevo število

'''Fibonaccijeva [[število|števila]]''', ki določajo '''Fibonaccijevo zaporedje''', so v [[matematika|matematiki]] [[rekurzija|rekurzivno]] določena z naslednjimi [[enačba]]mi:

: <math>
  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.
 </math>

Zaporedje začnemo z dvema številoma, običajno 1 in 1. Naslednje Fibonaccijevo število dobimo, če seštejemo predhodni. Prva Fibonaccijeva števila so {{OEIS|id=A000045}}:<ref>{{sktxt|Knott|1996-2011}}.</ref>

:{| class="wikitable" style="text-align:right"
|-
|  <math>F_{ 0}\, </math> || <math>F_{ 1}\, </math> || <math>F_{ 2}\, </math>
|| <math>F_{ 3}\, </math> || <math>F_{ 4}\, </math> || <math>F_{ 5}\, </math>
|| <math>F_{ 6}\, </math> || <math>F_{ 7}\, </math> || <math>F_{ 8}\, </math> 
|| <math>F_{ 9}\, </math> || <math>F_{10}\, </math> || <math>F_{11}\, </math> 
|| <math>F_{12}\, </math> || <math>F_{13}\, </math> || <math>F_{14}\, </math> 
|| <math>F_{15}\, </math> || <math>F_{16}\, </math> || <math>F_{17}\, </math> 
|| <math>F_{18}\, </math> || <math>F_{19}\, </math> || <math>F_{20}\, </math>
|| <math>F_{21}\, </math>
|-
| 1 || '''1''' || 2 || 3 || 5
|| 8 || 13 || 21 || 34
|| 55 || 89 || 144 || 233
|| 377 || 610 || 987 || 1597
|| 2584 || 4181 || 6765 || 10946 || 17711
|}

[[Slika:FibonacciBlocks.svg|thumb|right|200px|[[teselacija|Pokritje]] ravnine s kvadrati v velikosti Fibonaccijevih števil]]
[[Slika:Yupana 1.png|thumb|right|200px|Jupana ([[kečuanščina|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.<ref>{{navedi splet|last1= Aimi|first1= Antonio|last2= De Pasquale|first2= Nicolino|url= http://www.quipus.it/english/Andean%20Calculators.pdf|title= ANDEAN CALCULATORS|accessdate= |language=en}}</ref>]]
[[Slika:Fibonacci spiral 34.svg|thumb|right|200px|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]]]]
[[Slika:Liber abbaci magliab f124r.jpg|thumb|right|200px|Stran iz [[Leonardo Fibonacci|Fibonaccijevega]] dela ''Knjiga o abaku'' (''[[Liber Abaci]]''; [[Narodna osrednja knjižnica (Firence)|Narodna osrednja knjižnica v Firencah]]) prikazuje Fibonaccijevo zaporedje (uokvirjeno desno) s členi od 0 do 12 označenimi s črno z [[rimske številke|rimskimi]] in z vrednostmi označenimi z rdečo z [[arabske številke|indoarabskimi številkami]]]]
[[Slika:fibonacci.ogg|thumb|Fibonaccijevo zaporedje zvokovno, [[interval (glasba)|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 '''[[Fibonaccijevo zaporedje|Fibonaccijevega zaporedja]]''' lahko uporabimo splošneje na vsaki [[funkcija|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 [[Johannes Kepler|Kepler]], stopnja rasti Fibonaccijevih števil, ''F''(''n'' + 1) / ''F''(''n''), [[konvergenca|konvergira]] k [[število zlatega reza|številu zlatega reza]], označenem z φ. To je pozitivni koren kvadratne enačbe ''x''<sup>2</sup> - ''x'' - 1 = 0, tako da je φ<sup>2</sup> = φ + 1. Če pomnožimo obe strani z φ<sup>''n''</sup>, dobimo φ<sup>''n''+2</sup> = φ<sup>''n''+1</sup> + φ<sup>''n''</sup>, in je funkcija φ<sup>''n''</sup> Fibonaccijevo zaporedje. Lahko se pokaže, da ima negativni koren kvadratne enačbe, 1 - φ, enake značilnosti. Zato funkciji φ<sup>''n''</sup> in (1-φ)<sup>''n''</sup> tvorita novo bazo istega prostora.

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

: <math>F\left(n\right) = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}} . </math>

Isti rezultat dobimo, če uporabimo postopke [[rodovna funkcija|rodovnih funkcij]] ali reševanja linearnih [[rekurenčna enačba|rekurenčnih enačb]].

Ko gre ''n'' v neskončnost, drugi člen konvergira proti nič, tako, da Fibonaccijeva števila težijo k eksponentu φ<sup>''n''</sup> / √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:

: <math>\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} , 
</math>

ki namesto potenciranja uporablja kvadriranje.

=== Uporabe ===

Fibonaccijeva števila so pomembna pri analizi poteka [[Evklidov algoritem|Evklidovega algoritma]] za določitev [[največji skupni delitelj|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.

[[Jurij Vladimirovič Matijasevič|Matijasevič]] je pokazal, da lahko Fibonaccijeva števila določimo s posebno [[diofantska enačba|diofantsko enačbo]], kar nas vodi do njegove izvirne rešitve [[Matijasevičev izrek|10. Hilbertovega problema]].

Fibonaccijeva števila se pojavijo v enačbi za diagonale [[Pascalov trikotnik|Pascalovega trikotnika]].

Zanimiva uporaba Fibonaccijevega zaporedja je pri pretvarjanju [[milja|milj]] v [[kilometer|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 [[zlati rez|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 [[Lucasovo zaporedje|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 [[teorija števil|teoriji števil]] in dokazovanju [[praštevilo|praštevilskosti]].

=== Algoritem ===

V [[programski jezik pascal|pascalu]] lahko rekurzivni postopek prepišemo neposredno:
<syntaxhighlight lang="pascal">
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}
</syntaxhighlight>
Vendar je taka neposredna uporaba [[rekurzija|rekurzije]] '''zelo''' neučinkovita in pravzaprav služi kot šolski primer, kako je ne smemo uporabljati. Učinkovitejši je iterativni postopek:
<syntaxhighlight lang="pascal">
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}
</syntaxhighlight>
V [[Java (programski jezik)|javi]] (kot metoda) bi algoritem zgledal tako: 
<syntaxhighlight lang="java">
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;
    }
}
</syntaxhighlight>V [[Python (programski jezik)|Pythonu]], kot funkcija, bi algoritem zgledal tako:<syntaxhighlight lang="python3">
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
</syntaxhighlight>

== Fibonaccijeva števila v naravi ==
[[Slika:Helianthus whorl.jpg|thumb|right|200px|[[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]])]]
[[Slika:FibonacciChamomile.PNG|thumb|right|200px|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,<ref>{{sktxt|Douady|Couder|1996}}.</ref> npr. pri številu [[list (rastlina)#Venčni listi|venčnih listov]] in v spiralnih strukturah, ki jih mnoge rastline uporabljajo za razporeditev [[seme]]n (glej tudi [[Fermatova spirala]]). Poleg števila parov zajcev je znan primer tudi število [[čebela|č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.<ref>{{navedi splet|url= http://american-university.com/cas/mathstat/newstudents/shared/puzzles/fibbee.html|title= The Fibonacci Numbers and the Ancestry of Bees|accessdate= 2009-12-03|language=en}}</ref> V praksi se še danes uporablja izpopolnjene različice Fibonaccijeve sheme pri preučevanju drugih [[živali|živalskih]] [[populacija|populacij]].

Pri nekaterih [[cvetnice|cvetnicah]] so ta števila jasno izražena pri venčnih listih. Tako imajo [[lilije]] 3 venčne liste, [[zlatica|zlatice]] 5, [[ostrožnik (rastlina)|ostrožniki]] pogosto 8, [[ognjič]] 13, [[aster|astre]] 21 in [[navadna marjetica|marjetice]] ter [[sončnica|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 [[jelka (rod)|jelovih]] [[storž]]ih so tipično razporejene v dveh družinah prepletenih spiral; storž [[norveška jelka|norveške jelke]] ima tako 5 zavojev lusk v eni družini, v drugi pa 3.<ref>{{sktxt|Prusinkiewicz|Lindenmayer|1990}}.</ref>

== Fibonaccijeva števila v leposlovju ==

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

== Glej tudi ==

* [[obratna Fibonaccijeva konstanta]]

== Sklici ==
{{sklici|2}}

== Viri ==

* {{navedi revijo|last1= Douady|first1= S|last2= Couder|first2= Y.|title= Phyllotaxis as a Dynamical Self Organizing Process|journal= [[Journal of Theoretical Biology]]|year= 1996|issue= 178|pages= 255–274|url= http://www.math.ntnu.no/~jarlet/Douady96.pdf|doi= 10.1006/jtbi.1996.0026|volume= 178|format= |access-date= 2009-12-03|archive-date= 2006-05-26|archive-url= https://web.archive.org/web/20060526054108/http://www.math.ntnu.no/~jarlet/Douady96.pdf|url-status= dead}}
* {{citat|url= http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html|publisher= Surrey|place= Združeno kraljestvo|first= Ron|last= Knott|title= Fibonacci|year= 1996–2011|contribution= Fib table|accessdate= 2013-05-10|language=en}}. Stran navaja prvih 300 Fibonaccijevih števil 300 F<sub>''n''</sub> razstavljenih na prafaktorje in povezavami na druge obsežnejše razpredelnice.
* {{navedi knjigo|last1= Prusinkiewicz|first1= P.|authorlink1= |last2= Lindenmayer|first2= A.|title= The Algorithmic Beauty of Plants|publisher= Springer-Verlag|year= 1990|location= |pages= 101–107|url= http://algorithmicbotany.org/papers/#webdocs|doi= |isbn= 978-0387972978}}

{{-}}

{{zaporedja in vrste}}

{{normativna kontrola}}
[[Kategorija:Zaporedja]]
[[Kategorija:Fibonaccijeva števila| ]]