Fibonaccitall

I matematikk er et fibonaccitall eller et Fibonacci-tall et tall i den uendelige følgen

$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

$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 er navnsatt etter den italienske matematikeren Leonardo Fibonacci. Historisk er også navnet Lames tall brukt, etter den franske matematikeren Gabrielle Lame.

Liste over 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

Eksplisitt form for fibonaccitall

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

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

Her er $\varphi\,$ forholdstallet i det gyldne snitt, definert ved

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

Forholdet mellom påfølgende fibonaccitall

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

$\lim_{n\to\infty}\frac{a_{n+1}}{a_n}=\varphi,$

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

Historie

Fibonaccitallene ble først beskrevet av den indiske matematikeren Pingala, født ca. år 500 f. Kr. 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.

Perlscript for utskrift av følgen

#!/usr/bin/perl

use bigint;

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

Javakode for å beregne fibonaccitall nummer n

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

Pythonkode for å beregne fibonaccitall nummer n

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

ActionScriptkode for å beregne fibonaccitall nummer n

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

PHPkode for å beregne fibonaccitall nummer n

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