rekurencja_wzory fibonacciego

[Lukas:)]

1. Rozwiąż rekurencję an = an−1 +2an−2 dla n > 2 z warunkami początkowymi a1 = a2 = 1
z pomocą funkcji tworzącej oraz metody opartej o równanie charakterystyczne.

2. Liczby Lucasa: rozważ ciąg ln = an−1 +2an−2, gdzie an są liczbami Fibonacciego. Znajdź
rekurencję wyrażająca ln poprzez ln−1 i ln−2, oraz stosowne warunki początkowe, następnie
rozwiąż tę rekurencję.

3. Woparciu o dowolną metodę rozwiąż rekurencję an = 6an−1−11an−2+6an−3 z warunkami
początkowymi a0 = a1 = a2 = 1.

4. Rozwiąż rekurencję niejednorodną an = an−1 + 2an−2 + (−1)n dla n > 2 z warunkami
początkowymi a1 = a2 = 1.

5. Załóż, że masa kolejnych krążków Wież Hanoi rośnie jak n2 – jest to dość realistyczne,
bo typowa zabawka ma krążki o promieniach z grubsza wzrastających jak n i o tej samej
grubości. Jaką całkowitą masę trzeba przenieść przy wykonaniu algorytmu ???

6. Rozwiąż rekurencję an+1 = a2
n, gdzie n ≥ 1, z warunkiem a1 = 2. (Wskazówka: wykorzystaj
funkcję log.)

7. Na okregu wybrano n różnych punktów, a miedzy nimi narysowano wszystkie możliwe
cięciwy. Na ile obszarów zostało podzielone koło?

8. Wiedząc, że truteń płodzony jest bezpłciowo z królowej, a królowa płodzona jest płciowo
z trutnia i królowej, narysuj drzewo genealogiczne trutnia. Policz liczbe osobników w
każdym pokoleniu tego drzewa. Co odkryłeś?