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 NW D(a, c) = 1, to NW D(a, bc) = NW 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ś.
1 CiÄ…g Fibonacci
Leonardo Fibonacci zajmował się zagadnieniem, które doprowadziło go do
rekurencyjnego określenia pewnego ciagu 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: f1 = f2 = 1, fn =
fn-1 + fn-2, n e" 3.
1
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ść
2
fn+1 = fnfn+2 + (-1)n.
2
Dowód. Zastosujmy indukcje względem n. Dla n = 1 mamy f2 = f1f3-1 =
2
2 - 1 = 1. Załóżmy, że fk+1 = fkfk+2 + (-1)k. Dodajemy do obu stron
fk+1fk+2. Mamy
2
fk+1 + fk+1fk+2 = fkfk+2 + fk+1fk+2 + (-1)k,
fk+1(fk+1 + fk+2) = fk+2(fk + fk+1) + (-1)k,
2
fk+1fk+3 = fk+2 + (-1)k,
2
fk+2 = fk+1fk+3 + (-1)k+1.
Na przyklad 8 · 8 = 5 · 13 - 1 powoduje powstanie Å‚amigłówki.
Twierdzenie 2. Niech fn będzie n-tą liczbą Fibonacciego. Wtedy NW D(fn, fn+1) =
1 dla n e" 1.
Dowód. Jeśli d|fn+1 i d|fn, to d|fn-1. Rozumując tak samo, otrzymamy
d|fn-2, d|fn-3,..., i w końcu d|f1. Stąd d = 1.
2
Twierdzenie 3. Dla liczb Fibonnaciego zachodzi równość:
fm+n = fm-1fn + fmfn+1.
Dowód. Stosujemy indukcję ze względu na n, przy ustalonym m. Dla n = 1
fm+1 := fm-1 + fm = fm-1f1 + fmf2 bo f1 = f2 = 1 więc OK.
Zakładamy, że wzór jest prawdziwy dla n i n-1 : fm+n = fm-1fn+fmfn+1
oraz fm+(n-1) = fm-1fn-1 + fmfn. Sprawdzamy czy równość zachodzi dla
n + 1:
fm+n+1 := fm+n + fm+n-1 = (fm-1fn + fmfn+1) + (fm-1fn-1 + fmfn) =
fm-1(fn + fn-1) + fm(fn+1 + fn) = fm-1fn+1 + fmfn+2 = fm+(n+1).
Uwaga Liczba 12 jest podzielna przez 6, 4, 3, 2 i 1 a f12 = 144 jest podzielne
przez: f6 = 8, f4 = 3, f3 = 2, f2 = f1 = 1.
Twierdzenie 4. Liczba fmn jest podzielna przez fm dla m, n e" 1 .
Dowód. Stosujemy indukcję ze względu na n przy ustalonym m dla n = 1 :
fm|fm. Zakładamy: fm|fmn. Pokazemy, że fm|fm(n+1).
Na podstawie Twierdzenia 3, fm(n+1) = fmn+m = fmn-1fm + fmnfm+1.
Zauważmy, ze fm dzieli każdy składnik. Czyli dzieli też ich sumę.
Lemat 1. Jeśli m = qn + r, to NW D(fm, fn) = NW D(fr, fn).
Dowód. Korzystając z Twierdzenia 3 mamy fqn+r = fqn-1fr + fqnfr+1,
NW D(fm, fn) = NW D(fqn+r, fn) = NW D(fqn-1fr+fqnfr+1, fn).
Jeśli b|c, to NW D(a + c, b) = NW D(a, b); z warunku fn|fqn otrzymujemy
NW D(fm, fn) = NW D(fqn-1fr + fqnfr+1, fn) = NW D(fqn-1fr, fn).
Wystarczy więc wykazać, że NW D(fqn-1, fn) = 1. Niech NW D(fqn-1, fn) =
d. Ponieważ d|fn i fn|fqn, więc d|fqn, a jednocześnie d|fqn-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 NW D(fm, fn) = fd, gdzie d =
NW D(m, n).
Dowód. Przyjmijmy, że m e" n. Z algorytmu Euklidesa:
m = q1n + r1 gdzie 0 < r - 1 < n,
n = q2r1 + r2 gdzie 0 < r2 < r1,
...............................................
rk-2 = qkrk-1 + rk gdzie 0 < rk < rk-1,
rk-1 = qk + 1rk + 0.
Z Lematu 1 wynika, że:
NW D(fm, fn) = NW D(fn, fr ) = NW D(fr , fr ) = . . . = NW D(fr , fr ) = fr .
1 1 2 k-1 k k
Z drugiej strony rk = NW D(m, n), co kończy dowód.
3
Przykład NW D(2584, 610) = NW D(f18, f15) = fNW D(18,15) = f3 = 2.
Wniosek 1. Jeśli m, n > 2, to dla liczb Fibonacciego fm|fn wtedy i tylko
wtedy, gdy m|n, bo: fm|fn Ò! NW D(fm, fn) = fm Ò! NW D(m, n) = m Ò!
m|n.
Wzór Bineta (1843)
îÅ‚( " )n+1 ( " )n+1Å‚Å‚
1 1 + 5 1 - 5
ðÅ‚ ûÅ‚
fn = " - , n " N.
2 2
5
2 Złoty podział
a
a - x
x
a x
=
x a - x
x2 + ax - a2 = 0
" "
-1 - 5 -1 + 5
x1 = a = -a · 1, 618... < 0, x = x2 = a = a · 0, 618... .
2 2
"
a 1 + 5
= := Ć naz.ZOTALICZBA
x 2
Konstrukcja złotej liczby
4
(a)2 (
a)2
a2 + = x +
2 2
x2 + ax - a2 = 0
"
5 - 1
x = a.
2
Konstrukcja złotego prostokąta
5
Wyszukiwarka
Podobne podstrony:
tydzień na wschodzie 13 201013 12 2010SIMR AN2 EGZ 2010 09 13 rozw13 grudzień 2010 kluczrecepty z 13,12,20102010 nr 12 13 Polityka Chin w regionie Azji ŚrodkowejROZPORZĄDZENIE MINISTRA SPRAW WEWNĘTRZNYCH I ADMINISTRACJI z dnia 13 wrzesnia 2010 w sprawie Rady I2010 05 07 13;50;24Technologia Informacyjna ( 13 10, 27 10, 03 11 2010)2010 05 07 13;50;40SIMR AN2 EGZ 2010 09 13UAS 13 zaoer4p2 5 13więcej podobnych podstron