Zadání cvičení pro 10-11. týden: 30.4.-11.5.
V květnu několik cvičení odpadá. Měli bychom do konce semestru dobře
předvést využití vytvořujících funkcí pro řešení rekurencí. Vysvětlete přitom
obecný algoritmus, patrně ale stačí zůstat o lineárních rekurencí (ne nutně ho-
mogeních).
Příklad. (12.75)
Najděte vytvořující funkci a explicitní vyjádření pro n-tý člen posloupnosti {an}
definované rekurentním vztahem
a0 = 1, a1 = 2
an = 4an−1 − 3an−2 + 1 pro n ≥ 2.
Příklad. (12.76)
Pomocí vytvořující funkce vyřešte následující rekurenci:
a0 = 1, a1 = 2
an = 5an−1 − 4an−2 n ≥ 2
Příklad. (12.69)
Vyřešte rekurenci
a0 = a1 = 1,
an = an−1 + 2an−2 + (−1)n
.
Ve zbylém čase řešte další rekurence, a ukažte pokud možno některý ze
složitějších příkladů, např. 12.73.
1