Redigerer Fibonaccitall

'''Fibonacci-tallene''', også skrevet '''fibonaccitallene''' og kalt '''Fibonacci-rekken''' og liknende, er en serie [[tall]] der hvert ledd (fra og med det tredje) er lik summen av de to foregående og forholdet mellom to påfølgende tall er lik [[det gylne snitt]]. Tallrekka er oppkalt etter den italienske matematikeren [[Leonardo Fibonacci]] (cirka 1175–1235). Historisk er også navnet '''Lames tall''' brukt etter den franske matematikeren [[Gabrielle Lame]]. I [[matematikk]] er et fibonaccitall et tall i den uendelige [[følge (matematikk)|følgen]]
:<math>0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots.</math>

Følgen kalles for '''Fibonacci-følgen'''. Bortsett fra de to første startverdiene 0 og 1 framkommer leddene i følgen ved å summere de to forrige leddene.  Formelt kan dette uttrykkes som

:<math>
  a_n  = 
   \begin{cases}
    0 & \mbox{hvis }n=0  \\
    1 & \mbox{hvis }n=1 \\
    a_{n-1}+a_{n-2} & \mbox{ellers}
   \end{cases}
 </math>

Fibonaccitallene kan også finnes ved å ta utgangspunkt i [[Blaise Pascal#Pascals talltrekant|Pascals trekant]] og forskyve alle radene slik at hver rad begynner én posisjon lengre til høyre enn raden over. Da vil den venstre delen se slik ut:
:{| class=table style=text-align:center
|-
| ||1
|-
| || || ||1|| ||1
|-
| ||colspan=4| ||1|| ||2|| ||1
|-
| ||colspan=6| ||1|| ||3|| ||3|| ||1
|-
| ||colspan=8| ||1|| ||4|| ||6|| ||4|| ||1
|-
| ||colspan=10| ||1|| ||5|| ||10|| ||10|| ||5|| ||1
|-
| ||colspan=12| ||1|| ||6|| ||15|| ||20|| ||15|| ||…
|-
| ||colspan=14| ||1|| ||7|| ||21|| ||35|| ||…
|-
| ||colspan=16| ||1|| ||8|| ||28|| ||…
|-
|| ||colspan=18| ||1|| ||9|| ||…
|-
| ||colspan=20| ||1|| ||…
|-
| ||colspan=22| ||osv.
|-
|'''Σ'''&emsp; ||&thinsp;'''1'''&thinsp;||&nbsp;||&thinsp;'''1'''&thinsp;||&nbsp;||&thinsp;'''2'''&thinsp;||&nbsp;||&thinsp;'''3'''&thinsp;||&nbsp;||&thinsp;'''5'''&thinsp;||&nbsp;||&thinsp;'''8'''&thinsp;||&nbsp;||'''13'''||&nbsp;||'''21'''||&nbsp;||'''34'''||&nbsp;||'''55'''||&nbsp;||'''89'''|| ||'''osv.'''
|}
Summen ('''Σ''') av hver enkelt rekke er et fibonaccitall.

== Liste over fibonaccitall ==
De første fibonaccitallene er ({{OEIS|A000045}})

:{| class="wikitable"
|-
| ''F''<sub>0</sub>
| ''F''<sub>1</sub>
| ''F''<sub>2</sub>
| ''F''<sub>3</sub> 
| ''F''<sub>4</sub>
| ''F''<sub>5</sub>
| ''F''<sub>6</sub>
| ''F''<sub>7</sub>
| ''F''<sub>8</sub>
| ''F''<sub>9</sub>
| ''F''<sub>10</sub>
| ''F''<sub>11</sub>
| ''F''<sub>12</sub>
| ''F''<sub>13</sub>
| ''F''<sub>14</sub>
| ''F''<sub>15</sub>
| ''F''<sub>16</sub>
| ''F''<sub>17</sub>
| ''F''<sub>18</sub>
| ''F''<sub>19</sub>
| ''F''<sub>20</sub>
|-
| 0
| 1
| 1
| 2
| 3
| 5
| 8
| 13
| 21
| 34
| 55
| 89
| 144
| 233
| 377
| 610
| 987
| 1597
| 2584
| 4181
| 6765
|}

== Eksplisitt form for fibonaccitall ==
Fibonaccitallene kan uttrykkes eksplisitt, det vil si uten bruk av rekursjonsformelen.  Den lukkete formen er kjent som [[Jacques Philippe Marie Binet|Binets]] formel

:<math>a_n = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}={{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}\, ,</math> 

selv om den ble først utledet av [[Abraham de Moivre|de Moivre]]. Her er &phi; forholdstallet i [[det gyldne snitt]], definert ved 
 
:<math>\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\dots\,</math>

== Forholdet mellom påfølgende fibonaccitall ==
Forholdet mellom to påfølgende fibonaccitall nærmer seg forholdstallet i det gylne snitt som grenseverdi:

:<math>\lim_{n\to\infty}\frac{a_{n+1}}{a_n}=\varphi,</math>  

Grenseverdien ble først påvist av [[Johannes Kepler]]. 

== Historie ==
Fibonaccitallene ble først beskrevet av den [[indisk matematikk|indiske matematikeren]] [[Pingala]], født ca. år 500 f. Kr.<ref>Parmanand Singh. "Acharya Hemachandra and the (so called) Fibonacci Numbers". Math. Ed. Siwan, 20(1):28-30, 1986. ISSN 0047-6269]</ref><ref>Parmanand Singh,"The So-called Fibonacci numbers in ancient and medieval India." Historia Mathematica 12(3), 229–44, 1985.</ref> Han beskrev de grunnleggende idéene bak Fibonnacifølgen. I den moderne verden er likevel fenomenet best kjent på grunn oppdagelsene gjort av [[Leonardo Fibonacci]] ([[1170]]&ndash;[[1250]]), fra [[Pisa]] i Nord-Italia. Han beskrev økningen i en noe idealisert kaninbestand (antall par kaniner) etter ''n'' måneder hvis følgende kriteria blir møtt:

* Den første måneden blir det bare født ett kaninpar,
* Nyfødte kaninpar blir produktive fra og med den andre måneden og utover,
* [[Innavl]] eksisterer ikke,
* Hver måned produserer hvert kjønnsmodent par et nytt kaninpar, og
* Kaninene dør aldri.

Formelen ovenfor passer til kaninproblemet fordi hvis vi i måneden ''n'' har ''a'' kaniner og i måneden ''n+1'' har ''b'' kaniner, så vil vi i måneden ''n+2'' ha ''a+b'' kaniner.
Dette fordi vi vet at hver kanin hovedsakelig føder en ny kanin hver måned (eller egentlig at hvert par føder et annet par, men det er akkurat det samme) og det betyr at alle ''a'' kaniner føder et tilsvarende antall ''a'' kaniner som vil bli kjønnsmodne etter to måneder, som er nøyaktig i måneden ''n+2''.
Det er derfor vi har bestanden ved tidspunktet ''n+1'' (som er ''b'') pluss bestanden ved tidspunkt ''n'' (som er ''a'').

Eksempler på Fibonacci-følgen finnes også i stor grad i naturen, for eksempel vil antall kronblader på blomster og antall blader ofte følge følgen. 

I den norske artikkelen von Brasch mfl. 2013<ref>Fibonaccirekken i økonomifaget, Samfunnsøkonomen nr 2, 2013 [http://samfunnsokonomene.no/magasin/] {{Wayback|url=http://samfunnsokonomene.no/magasin/ |date=20131027190227 }}</ref> vises det hvordan Fibonaccifølgen på to måter kan kobles til økonomifaget. For det første kan den kobles direkte til økonomiske teorier, som for eksempel en sentralbanks rentesetting, konsument- og investeringsadferd.  For det andre kan den brukes som måleinstrument for å tallfeste økonomiske parametre. Den norske populærvitenskapelige fremstillingen bygger i hovedsak på resultatene i von Brasch mfl. 2012 <ref>Optimal Control and the Fibonacci Sequence, 2012, Journal of Optimization Theory and Applications, DOI: 10.1007/s10957-012-0061-2 [http://link.springer.com/article/10.1007%2Fs10957-012-0061-2]</ref>.

== [[Perl]]-script for utskrift av følgen ==

<pre>
#!/usr/bin/perl

use bigint;

my ($i, $j) = (1, 1);
for (;;) {
    print("$i\n");
    ($i, $j) = ($i, $i+$j);
}
</pre>

== [[Java (programmeringsspråk)|Java]]-kode for å beregne fibonaccitall nummer n == 

<pre>
public static int fib(int n) {
    if (n < 2) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }	
}
</pre>

== [[Python (programmeringsspråk)|Python]]-kode for å beregne fibonaccitall nummer n == 
 def fib(n): return n if n in (0,1) else fib(n-1)+fib(n-2)

== [[ActionScript]]-kode for å beregne fibonaccitall nummer n == 

<syntaxhighlight lang="actionscript">
public static function fib (n:uint):uint
{
	if (n <= 1 && n >= 0)
	{
		return n;
	}
			
	return fib (n – 2) + fib (n – 1);
}
</syntaxhighlight>

== [[PHP]]-kode for å beregne fibonaccitall nummer n == 

<syntaxhighlight lang="php">
public function fib ($n)
{
	if ($n AND $n <= 1)
	{
		return $n;
	}
			
	return fib ($n – 2) + fib ($n – 1);
}
</syntaxhighlight>

==Referanser==
<references/>
{{Autoritetsdata}}

[[Kategori:Rekursjon]]
[[Kategori:Heltallsfølger]]