Równanie rekurencyjne Highway: Cześć. W jaki sposób rozwiązać takie równanie rekurencyjne? Mam je do zrobienia na Algorytmy na studiach.

⎧	T(0) = 1
⎩	T(n) = 2T(n − 1) + 1

jc: Oblicz kilka początkowych wyrazów, może zobaczysz co się dzieje.

Adamm: Można np. podstawić 1, 3, 7, 15, 31, 63 I zobaczyć że wyrazy tego ciągu przypominają 2ⁿ⁺¹−1

Adamm: Inny sposób to "rozłożyć" równanie rekurencyjne otrzymując sumę T(n) = 2ⁿ+...+1 = 2ⁿ⁺¹−1

ABC: metodą wyciągania królika z kapelusza zauważasz że T(n)=2ⁿ⁺¹−1 i udowadniasz to indukcyjnie krok indukcyjny : T(n+1)=2T(n)+1 =2*(2ⁿ⁺¹−1)+1=2ⁿ⁺²−2+1=2ⁿ⁺²−1

kerajs: Albo : rozwiązując rekurencyjne równanie jednorodne: r=2 przewidując z równania niejednorodnego postać wzoru ogólnego na: T(n)=A2ⁿ+B i wyznaczając brakujące współczynniki z warunków początkowych: 1=A2⁰+B ⋀ 3=A2¹+B co da: T(n)=2*2ⁿ−1 albo: PS Pewnie mariuszm poda rozwiązanie z funkcją tworzącą.