Rekurencje

Króliki Fibonacciego

 Fibonacci (Leonardo z Pizy; ur. około 1175 r. -

zm. 1250 r.) – włoski matematyk. Znany jako:

Leonardo Fibonacci, Filius Bonacci (syn

Bonacciego), Leonardo Pisano (z Pizy).

 1202 rok – jak rozmnażają się króliki?

 Króliki dorastają w ciągu jednego miesiąca.

 Zawsze rodzi się jedna para królików (jeden

męski i jeden żeński królik).

 Króliki nigdy nie umierają.

5. Rekurencje.

Króliki

Liczba par królików

1

1

2

3

5

Ciąg Fibonacciego

 Liczba par królików na początku każdego

miesiąca wynosi:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…

 Są to kolejne liczby ciągu Fibonacciego.
 Dwie pierwsze liczby tego ciągu to 1.
 Każda następna jest sumą dwóch

poprzednich.

Jeśli Fn oznacza n-tą liczbę Fibonacciego, to
F

n

=F

n -1

+F

n -2

;

F

0

=1, F

1

=1.

Kwadraty Fibonacciego i

muszle

1

2

3

5

8

1

Muszle - galeria

Liczby Fibonacciego a

wzrost roślin

 Łodyga potrzebuje

dwóch miesięcy aby

wypuścić nową odnóżkę,

potem wypuszcza nowe

pędy co miesiąc.

 Liczba łodyg w każdym

miesiącu stanowi kolejną

liczbę Fibonacciego.

 Biolodzy potrafią

wskazać rośliny, które

tak się rozmnażają, np.

dąb lub krwawnik

kichawiec

(sneezwort).

1

1

2

3

5

8

Fibonacci a słoneczniki

 Zliczając spirale prawo

i lewoskrętne

utworzone z ziaren

słonecznika

otrzymujemy dwie

sąsiednie liczby

Fibonacciego.

Fibonacci a szyszki

 Zliczamy spirale prawo
i lewoskrętne

utworzone z łusek
szyszki od miejsca
przytwierdzenia do
gałązki.

Jeszcze więcej szyszek

5

8

Ananasy

 Łuski ananasa są

sześciokątami,
dlatego możemy
wyróżnić trzy
rodzaje spiral.

13

8

5

Liczby Fibonacciego w

płatkach kwiatów

Kalia (white calla lily)– 1 płatek

Ostromlecz (euphorbia ) – 2 płatki

Trójlist (trillium) – 3 płatki

Liczby Fibonacciego w

płatkach kwiatów

Goździki – 5 płatków

Dzika róża – 5 płatków

Orlik (columbine) – 5 płatków

Liczby Fibonacciego w

płatkach kwiatów

Stokrotka – może
mieć 13, 21, 34, 55 lub 89
płatków

Krwiowiec (bloodroot) – 8 płatków

Stokrotka (shasta daisy) – 21 płatków

Nie zawsze Fibonacci…

Fuksja – 4 płatki

Krokus – 6 płatków

Narcyz – 6 płatków

Żródła:

•

http://www.mcs.surrey.ac.uk/Person
al/R.Knott/Fibonacci/fibnat.html

•

http://britton.disted.camosun.bc.ca/
fibslide/jbfibslide.htm

Wieże Hanoi

Liniowa, jednorodna relacja rekurencji ze stałymi współczynnikami (*)
jest to relacja rekurencji postaci:

an=c1an-1+c2an-2+...
+ckan-k,

gdzie c1, c2, ... ,ck  R i ck



0.

Liniowa oznacza, że każde ai jest w potędze co najwyżej pierwszej;

Jednorodna – że każdy człon po prawej stronie jest pomnożony przez
jakieś ai;

Relacja rekurencji

Wszystkie wpółczynniki ci są stałe (czyli niezależne od n);

Ponieważ ak zależy od k swoich poprzedników, więc rzędem relacji
jest k.

Aby rozwiązać relację rekurencji, będziemy potrzebowali k warunków
początkowych: a0 = c0, a1 = c1,..., ak = ck.

Przykłady.

1. sn = 2sn-1 – relacja (*) pierwszego rzędu

2. an = nan-1 jest liniowa i pierwszego rzędu. Ale współczynnik przy
an-1 nie jest stały;

3. bn = bn-1 + (n-1) jest relacją liniową pierwszego rzędu o stałych
współczynnikach. Ale ze względu na człon n-1 nie jest to relacja
jednorodna.

4.

jest jednorodna. Ale nie jest liniowa, bo an-1
występuje w drugiej potędze.

5. dn= 2dn-1+3 dn-6 jest relacją (*) rzędu 6.

Zauważmy, że rozwiązaniem równania sn = 2sn-1, gdzie s0 = 1 jest

Ogólniej, rozwiązaniem równania rekurencyjnego an =



an-1, gdzie a0 = c

jest

Rozważmy teraz równanie rekurencyjne typu (*) postaci:

an = a an-1 + b an-2,

gdzie a i b są niezerowymi stałymi.

Jeśli to równanie posiada niezerowe rozwiązanie postaci

to

To daje

czyli



musi być rozwiązaniemrównania charakterystycznego:

Twierdzenie. Niech



i



będą różnymi rozwiązaniami równania

charakterystycznego, gdzie a, b



R i b



0. Wtedy każde rozwiązanie

Równania an = a an-1 + b an-2, gdzie a0 = c0 i a1 = c1 jest postaci

dla pewnych stałych A i B.

Zauważmy, że twierdzenie nie może być stosowane, jeśli



=



.

Można jednak je stosować, jeśli



i



są liczbami zespolonymi.

Rozwiązania

i

są to rozwiązania podstawowe.

Rozwiązanie relacji rekurencji

jest kombinacją liniową rozwiązań podstawowych.

Przykład. Rozwiązać relację a

n

= 5a

(n-1)-

6 a

(n-2),

gdzie a

0

= 4 i a

1

= 7.

Przykład. Rozwiązać relację rekurencji Fibonacciego
F

n

= F

(n-1)+

F

(n-2),

gdzie F

0

= 1 i F

1

= 1.

Zadanie

Zadanie

Zadanie

Funkcje tworzące.

Niech a1, a2,..., an,... będzie ciągiem liczb rzeczywistych.
Funkcją tworzącą dla ciągu (an) nazywamy funkcję postaci:

Funkcją tworzącą, którą będziemy najczęściej używać jest

czyli

Dodawanie i mnożenie funkcji tworzących:

Niech

i

będą dwoma funkcjami tworzącymi.

Wtedy

oraz

Aby rozwiązać równanie rekurencyjne metodą funkcji tworzących,
potrzebny jest rozkład funkcji wymiernej na ułamki proste, np.

Przykład. Rozwiązać relację an= 5an-1-6 an-2, gdzie a0 = 4 i a1 = 7.

Przykład. Rozwiązać relację rekurencji Fibonacciego
Fn= Fn-1+Fn-2, gdzie F1 = 1 i F2 = 1.