Fasit Mattenøtt TU 20 - 2003





La svaret generelt være f(n), der oppgavens svar fås ved f(10). Vi setter både f(0) = 1 og f(1) = 1. Siden neste trinn kan nås direkte eller fra det nedenfor, får vi for n større eller lik 2 at f(n) = f(n-1) + f(n-2). Løsningen kan derfor løses ved rekursjon til å være f(10)=89.

Denne rekken er meget interessant og kalles Fibonacci-rekken, eller Fibonacci-følgen, etter Leonardo fra Pisa (omkring 1200) som ble kalt Fibonacci. Her er et knippe med pussigheter.

Et Fibonacci-tall f(n) er et partall hvis og bare hvis n er delelig med 3. f(n) er delelig med 3 hvis og bare hvis n er delelig med 4. f(n) er delelig med 4 hvis og bare hvis n er delelig med 6. f(n) er delelig med 5 hvis og bare hvis n er delelig med 5.

Ja, er ikke dette pussig så vet ikke jeg? Det er også en underlig sammenheng mellom Fibonacci-tallene og binomialkoeffisientene som jeg ikke skal komme inn på her.