6099520163

Indukcja Rekurencja (urencyjnych

Liniowe jednorodne zależności rekurencyjne

Przykład: Na ile różnych sposobów można wejść na schody zbudowane z n stopni, jeżeli w każdym kroku można pokonać 1 lub 2 stopnie?

Po dołożeniu do schodów n-tego stopnia, liczba dróg jest równa sumie a„_\ (ostatni krok krótki) i a_n_2 (ostatni krok długi): a_n = a_n-1 + 3n-2-

X² = X + 1

^1,2 =

l±>/5

2

Rozwiązanie ogólne dane jest wzorem a_n — o:ix{^J + (*2X2-