Fibonaccitall

Dette innlegget har allerede blitt vist 2535 ganger!

Fibonaccitall er definert på følgende måte:
Fn = Fn-1 + Fn-2. Der F0 = 0 og F1 = 1

Altså:
F2 = F1 + F0 = 1 + 0 = 1
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5

Teorem: Fn og Fn+1 er relativt primiske for alle n >= 0

Lemma: La m >= 0 og n => 1 være heltall:
Fm+n = Fn*Fm+1 + Fn-1*Fmm

Største felles divisor av fibonaccitall

Lemma: Fm Fnm for alle m >= 1 og n >= 0

Lemma: gcd(Fm, Fn) = gcd(Fn+n, Fn)

Lemma: gcd(Fa, Fb) = gcd(Fb, Fa mod b) for naturlige tall a,b (merk: husk Euklids algoritme her)

Teorem: gcd(Fa, Fb) = Fgcd(a,b) for alle naturlige tall a,b

Eks: regn ut gcd(F321, F78):
gcd(F321, F78) = Fgcd(321,78)
gcd(321,78) = 3
F3 = 2
gcd(F321,F78) = F3 = 2