262080413

A. PAWEŁ WOJDA

1 mikrosekundy jedno, można z łatwością oszacować czas potrzebny wsystkich kółek na grubo ponad 500 000 łat).

1.3. Równania rekurencyjne. Niech będzie zadany ciąg (a_n) w następujący sposób.

•    Dane są wartości ao, ai,..., a^-i (a więc k pierwszych wyrazów ciągu) oraz wzór

•    a_n = f(a_n-i,a_n-2,...a_n-k), gdzie / jest pewną funkcją.

Zdefiniowany w taki sposób ciąg (a_n) nazywamy rekurencyjnym stopnia k.

1.3.1. Ciąg Fibonacciego. Ciąg Fibonacciego² to z pewnością najsłynniejszy ciąg rekurencyjny (drugiego stopnia). Pomijając tu anegdotę o królikach, można go zdefiniować następująco:

•    /o = l

•    h = i

•    fn+l = fn + fn—1 dla II > 2

Oczywiście i tym razem można z łatwością wypisać pierwszych kilka wyrazów ciągu:

h = 2,/₃ = 3 ,/₄ = 5,/s = 8,/₆ = 13, /₇ = 21,/₈ = 34, /₉ = 55,/₁₀ = 89

Tym razem jednak ciąg kolejnych wyrazów, nawet gdybyśmy wypisali ich znacznie więcej, nie sugeruje żadnego ogólnego wzoru. Na następnym wykładzie poznamy sposób jak sobie z niektórymi ciągami rekurencyjny mi radzić. Metoda którą poznamy obejmuje także ciąg Fibonacciego. Nie precyzując metody ogólnej ciąg Fibonacciego jednak rozwiązaliśmy. Okazało się, że

fn =

1

{>¥)

n+1

1 - \/5

Tak skomplikowane rozwiązanie oczywiście wyjaśnia, dlaczego nie byliśmy w stanie odgadnąć ogólnego wzoru.

²Postaci i znaczeniu Fibonacciego (1175-1250) poświęciłem na wykładzie chwilkę. Warto poszperać w wyszukiwarce i poczytać o człowieku, który poruszył europejską matematykę, napisał pierwsze znaczące dzieła matematyczne w Europie po 1000 lat zacofania.