plik

Teoria liczb 2010, sem.IV,

B.Bajorska, O.Macedońska

Wykład 13.

Liczby Fibonacci

Potrzebne: (i). Jeśli b

|c, to NW D(a + c, b) = NW D(a, b).

(ii). Jeśli N W D(a, c) = 1, to N W D(a, bc) = N W D(a, b).

Leonardo Fibonacci (1170-1250). Wiadomo, że Leonardo urodził się w

1170 w Pizie. Należał do rodu Bonacci (Fibonacci = ”syn dobrotliweg”).
W roku 1192 Ojciec pełniąc obowiązki sekretarza Republiki Piza, wyjechał
do terazniejszej Algerii i zabrał syna, by nauczył sie rachunków i mógł być
kupcem. Właśnie tam Leonardo zainteresował się matematyką i nauczył
się nowych metod z użyciem cyfr pochodzących z Indii, ale znanych jako
arabskie.

W 1202 roku Fibonacci napisał słynną ksęgę ”Liber Abaci”. Słowo ”aba-

cus” (z greckiego ”abax”) oznacza deskę posiadającą rowki z wgłębieniami,
gdzie przesuwano kamyczki do liczenia. Używano abacus do XVIII wieku,
do powstania liczydła, gdy zamieniono rowki drutami z przesuwanymi kora-
likami.

Wielu historyków uważa, że w nazwa ”Liber abbaci” ma być tłumaczona

jako ”Księga rachunków”.

Ksęga ”Liber Abaci” była napisana ręcznie i systematycznie przedstaw-

iała wiedzę matematyki arabskiej. Była to pierwsza encyclopedia mate-
matyki, w ciągu stuleci służyła jako podstawowy podręcznik aryt-
metyki i algebry na terenie Europy Zachodniej.

W książce ”Liber Abaci” 1202, Leonardo Fibonacci wprowadził arab-

skie (ale wcześniej hinduskie) cyfry, których używamy do dziś.

Ciąg Fibonacci

Leonardo Fibonacci zajmował się zagadnieniem, które doprowadziło go do
rekurencyjnego określenia pewnego ci¸

agu liczb, które na jego cześć zostały

nazwane liczbami Fibonacciego. Konkretnie chodziło o obliczenie, jak szybko
powiększać się będzie populacja królików pochodzących od jednej pary.

Ile par królików może spłodzić jedna para w ciągu roku jeśli:

(i) każda para rodzi nową parę pod koniec każdego miesiąca zaczynając od
drugiego miesiąca. życia;
(ii) króliki nie zdychają.

Wzrost populacji królików opisuje ciąg Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

w którym każdy wyraz jest sumą dwóch poprzednich: f

= f

= 1, f

−1

+ f

−2

, n

≥ 3.

Na tarczy słonecznika znajdują się dwa układy linii spiralnych.

Jeśli

policzymy spirale zgodne z ruchem wskazówek zegara i spirale przeciwne do
nich, to otrzymamy liczby Fibonacciego. 34 i 55 lub 55 i 89.

Spirale Fibonacciego występują w szyszkach sosnowych z liczbami 8 i 13.

Liczby Fibonacciego można odczytać z ananasa: 8 i 13.

Liczba płatków stokrotki jest liczbą Fibonacciego: 13 21 34 55 89.

Jedno z najstarszych twierdzeń dotyczących liczb Fibonacci po raz pier-

wszy opublikowano w roku 1680 przez włoskiego astronoma Jean-Dominique
Cassiniego.

Twierdzenie 1. (Cassini, 1680) Dla liczb Fibonacci zachodzi tożsamość

n+1

= f

n+2

+ (

−1)

Dowód. Zastosujmy indukcje względem n. Dla n = 1 mamy f

= f

−1 =

− 1 = 1. Załóżmy, że f

k+1

= f

k+2

+ (

−1)

. Dodajemy do obu stron

k+1

k+2

. Mamy

k+1

+ f

k+1

k+2

= f

k+2

+ f

k+1

k+2

+ (

−1)

k+1

+ f

k+2

) = f

k+2

+ f

k+1

) + (

−1)

k+1

k+3

= f

k+2

+ (

−1)

k+2

= f

k+1

k+3

+ (

−1)

k+1

Na przyklad 8

· 8 = 5 · 13 − 1 powoduje powstanie łamigłówki.

Twierdzenie 2. Niech f

będzie n-tą liczbą Fibonacciego. Wtedy N W D(f

, f

n+1

) =

1 dla n

≥ 1.

Dowód. Jeśli d

n+1

i d

, to d

−1

. Rozumując tak samo, otrzymamy

−2

, d

−3

,..., i w końcu d

. Stąd d = 1.

Twierdzenie 3. Dla liczb Fibonnaciego zachodzi równość:

m+n

= f

−1

+ f

n+1

Dowód. Stosujemy indukcję ze względu na n, przy ustalonym m. Dla n = 1
f

m+1

:= f

−1

+ f

= f

−1

+ f

bo f

= f

= 1 więc OK.

Zakładamy, że wzór jest prawdziwy dla n i n

−1 : f

m+n

= f

−1

n+1

oraz f

m+(n

−1)

= f

−1

+ f

. Sprawdzamy czy równość zachodzi dla

n + 1:

m+n+1

:= f

m+n

+ f

m+n

−1

= (f

−1

+ f

n+1

) + (f

−1

+ f

) =

−1

+ f

−1

) + f

n+1

+ f

) = f

−1

n+1

+ f

n+2

= f

m+(n+1)

Uwaga Liczba 12 jest podzielna przez 6, 4, 3, 2 i 1 a f

= 144 jest podzielne

przez: f

= 8, f

= 3, f

= 2, f

= f

= 1.

Twierdzenie 4. Liczba f

jest podzielna przez f

dla m, n

≥ 1 .

Dowód. Stosujemy indukcję ze względu na n przy ustalonym m dla n = 1 :
f

. Zakładamy: f

. Pokazemy, że f

m(n+1)

Na podstawie Twierdzenia 3, f

m(n+1)

= f

mn+m

= f

−1

+ f

m+1

Zauważmy, ze f

dzieli każdy składnik. Czyli dzieli też ich sumę.

Lemat 1. Jeśli m = qn + r, to N W D(f

, f

) = N W D(f

, f

Dowód. Korzystając z Twierdzenia 3 mamy f

qn+r

= f

−1

+ f

r+1

N W D(f

, f

) = N W D(f

qn+r

, f

) = N W D(f

−1

r+1

, f

Jeśli b

|c, to NW D(a + c, b) = NW D(a, b); z warunku f

otrzymujemy

N W D(f

, f

) = N W D(f

−1

+ f

r+1

, f

) = N W D(f

−1

, f

Wystarczy więc wykazać, że N W D(f

−1

, f

) = 1. Niech N W D(f

−1

, f

) =

d. Ponieważ d

i f

, więc d

, a jednocześnie d

−1

, czyli d dzieli

kolejne liczby Fibonacciego i zgodnie z Twierdzenia 2, d = 1, co kończy
dowód.

Twierdzenie 5. Dla liczb Fibonacci’ego N W D(f

, f

) = f

, gdzie d =

N W D(m, n).

Dowód. Przyjmijmy, że m

≥ n. Z algorytmu Euklidesa:

m = q

n + r

gdzie 0 < r

− 1 < n,

n = q

+ r

gdzie 0 < r

< r

...............................................
r

−2

= q

−1

+ r

gdzie 0 < r

< r

−1

= qk + 1r

+ 0.

Z Lematu 1 wynika, że:

N W D(f

, f

) = N W D(f

, f

) = N W D(f

, f

) = . . . = N W D(f

−1

, f

) = f

Z drugiej strony r

= N W D(m, n), co kończy dowód.

Przykład N W D(2584, 610) = N W D(f

, f

) = f

N W D(18,15)

= f

= 2.

Wniosek 1. Jeśli m, n > 2, to dla liczb Fibonacciego f

wtedy i tylko

wtedy, gdy m

|n, bo: f

⇒ NW D(f

, f

) = f

⇒ NW D(m, n) = m ⇒

|n.

Wzór Bineta (1843)

√




(

1 +

√

)

n+1

−

(

−

√

)

n+1


 , n ∈ N.

Złoty podział

a - x

− x

+ ax

− a

= 0

−1 −

√

a =

−a · 1, 618... < 0,

x = x

−1 +

√

a = a

· 0, 618... .

1 +

√

:= φ naz.ZOTALICZBA

Konstrukcja złotej liczby