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ølgen

${\displaystyle 0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots .}$

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

${\displaystyle a_{n}={\begin{cases}0&{\mbox{hvis }}n=0\\1&{\mbox{hvis }}n=1\\a_{n-1}+a_{n-2}&{\mbox{ellers}}\end{cases}}}$

Fibonaccitallene kan også finnes ved å ta utgangspunkt i 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:

	1
			1		1
					1		2		1
							1		3		3		1
									1		4		6		4		1
											1		5		10		10		5		1
													1		6		15		20		15		…
															1		7		21		35		…
																	1		8		28		…
																			1		9		…
																					1		…
																							osv.
Σ	1		1		2		3		5		8		13		21		34		55		89		osv.

Summen (Σ) av hver enkelt rekke er et fibonaccitall.

De første fibonaccitallene er (følge A000045 i OEIS)

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19	F20
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765

Fibonaccitallene kan uttrykkes eksplisitt, det vil si uten bruk av rekursjonsformelen. Den lukkete formen er kjent som Binets formel

${\displaystyle a_{n}={{\varphi ^{n}-(1-\varphi )^{n}} \over {\sqrt {5}}}={{\varphi ^{n}-(-1/\varphi )^{n}} \over {\sqrt {5}}}\,,}$

selv om den ble først utledet av de Moivre. Her er φ forholdstallet i det gyldne snitt, definert ved

${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\dots \,}$

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

${\displaystyle \lim _{n\to \infty }{\frac {a_{n+1}}{a_{n}}}=\varphi ,}$

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

Fibonaccitallene ble først beskrevet av den indiske matematikeren Pingala, født ca. år 500 f. Kr.^[1][2] 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–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^[3] 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 ^[4].

#!/usr/bin/perl

use bigint;

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

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

def fib(n): return n if n in (0,1) else fib(n-1)+fib(n-2)

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

public function fib ($n)
{
	if ($n AND $n <= 1)
	{
		return $n;
	}
			
	return fib ($n – 2) + fib ($n – 1);
}