Fibonaccin lukujono

Fibonaccin lukujono määritellään rekursiivisesti seuraavasti:^[1]

${\displaystyle F(n)={\begin{cases}0&{\mbox{, kun }}n=0\\1&{\mbox{, kun }}n=1\\F(n-1)+F(n-2)&{\mbox{, kun }}n>1\\\end{cases}}}$

Fibonaccin lukujono energialaitoksen piipussa Turussa. Työ on italialaisen Mario Merzin ympäristötaideteos Fibonacci Sequence 1–55.

Toisin sanoen Fibonaccin lukujonon ajatuksena on laskea yhteen kaksi edellistä lukua, ja näin saada seuraavan luvun arvo. Fibonaccin lukujonon ensimmäiset yksitoista lukua järjestyksessä ovat 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Joskus on myös tapana määritellä Fibonaccin lukujonon alkavan ykkösestä eikä nollasta.

Keskiaikainen italialainen matemaatikko Leonardo Pisano eli Fibonacci kirjoitti luvuista vuoden 1202 kirjassaan Liber abaci.^[2]

Fibonaccin jono on kiinnostava, koska sen kahden perättäisen luvun suhde lähestyy kultaista leikkausta. Koska Fibonacci-tyyppisesti eteneviä korkoa korolle -summautuvia prosesseja löytyy paljon biologisesta luonnosta, löytyy sieltä myös paljon kultaista leikkausta vastaavia suhteita. Monissa kukissa terälehtien määrä vastaa jotakin Fibonaccin lukujonon lukua, kuten päivänkakkarassa 34.

Fibonaccin luvut ovat Fibonaccin polynomien erikoistapaus.^[1]

Analyyttinen muoto

Fibonaccin lukujono voidaan esittää myös analyyttisessä muodossa. Fibonaccin lukujonon yleisen termin lauseke on

${\displaystyle F\left(n\right)={{\varphi ^{n}-(1-\varphi )^{n}} \over {\sqrt {5}}}}$, jossa ${\displaystyle \varphi }$ on kultainen leikkaus ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618}$, eli kaavaan sijoitettuna:

${\displaystyle F\left(n\right)={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)}$.^[3]

Identiteettejä

Fibonaccin luvuista on muodostettu erilaisia identiteettejä.^[1]

Catalanin identiteetti:^[1]

${\displaystyle F\left(n\right)^{2}-F(n+r)F(n-r)=(-1)^{n-r}F(r)^{2}}$

D'Ocagnen identiteetti:^[1]

${\displaystyle F(m)F(n+1)-F(n)F(m+1)=(-1)^{n}F(m-n)}$

Gelin-Cesàro -identiteetti:^[1]

${\displaystyle F(n)^{4}-F(n-2)F(n-1)F(n+1)F(n+2)=1}$

Cassinin identiteetti:^[1]

${\displaystyle F(n-1)F(n+1)-F(n)^{2}=(-1)^{n}}$

Tribonaccin luvut

Fibonaccin luvuista väännettyä muotoa, jossa lasketaan kahden sijaan yhteen kolme perättäistä lukua, kutsutaan ”Tribonaccin luvuiksi”. Sen ensimmäiset luvut ovat 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81 ja 149.^[4]

Tribonaccin lukuja seuraavat korkeamman asteen lukujonot ovat ”tetranacci”, ”pentanacci”, ”heksanacci”, ”heptanacci”, ”octanacci” ja ”enneanacci”. Näissä lasketaan neljä, viisi, kuusi, seitsemän, kahdeksan tai yhdeksän perättäistä lukua yhteen.^[5]

Tetranaccin ensimmäiset luvut ovat 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208 ja 401.^[6]

Yleinen kaava, josta voidaan selvittää mikä hyvänsä luku, jossa on laskettu yhteen n peräkkäistä lukua, on

${\displaystyle F(n)={\frac {\alpha ^{n+1}}{(\alpha -\beta )(\alpha -\gamma )}}+{\frac {\beta ^{n+1}}{(\beta -\alpha )(\beta -\gamma )}}+{\frac {\gamma ^{n+1}}{(\gamma -\alpha )(\gamma -\beta )}}}$, missä ${\displaystyle \alpha ,\beta }$ ja ${\displaystyle \gamma }$ ovat polynomin ${\displaystyle P(x)=x^{3}-x^{2}-x-1}$ juuret.^[4]

3-Fibonaccin lukujonossa lasketaan aina yhteen edellinen luku kerrottuna kolmella ja sitä edeltävä luku sellaisenaan. Ensimmäiset luvut ovat 0, 1, 3, 10, 33, 109, 360, 1189, 3927 ja 12 970.^[7]

Ohjelmallinen toteutus

Fibonaccin luvut ovat laskettavissa JavaScriptillä rekursiolla seuraavalla funktiolla:

function fibonacci(n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n > 1) {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

Historiaa

Kanien lisääntyminen Fibonaccin kuvailemalla tavalla. Sukukypsät kanit on merkitty sinisillä ja punaisilla täplillä. Alenevat vaakarivit ovat toisiaan seuraavia lisääntymiskausia.

Fibonacci julkaisi lukujonon idean teoksessaan Liber abaci vuonna 1202. Hän esitteli nimellään kulkevien lukujen syntymekanismia kertoen maatilan pihalla kasvatettavien kanien lisääntymistä. Ensin oli kanipari. Se tuli sukukypsäksi ja sai kaksi poikasta. Seuraavassa vaiheessa kanipari sai uudelleen kaksi poikasta ja edelliset vain varttuivat sukukypsiksi. Sitten, kun ensimmäinen pari sai kolmannet poikasensa, saivat ensimmäiset poikaset poikasparin, ja toinen poikue varttui sukukypsäksi. Näin jatkuen kanit lisääntyivät varsin rivakasti.

Katso myös

• Zeckendorfin lause