dziękuję :): Która z podanych funkcji jest rozwiązaniem równania rekurencyjnego T(0)=1, T(n+1) = T(0)+...+T(n) dla wszystkich naturalnych n? 1. T(n) = lg n dla n>0. 2. T(n) = 1+2n dla wszystkich n. 3. T(n) = 2ⁿ⁻¹ dla n>0. 4. T(n) = 2ⁿ⁺¹ dla wszystkich n.

Basia: (1) nie, bo T(0)=1 i T(1) = ln1 = 0 T(2) = ln2 ≠ 1+0=1 (2) nie, bo T(0) = 1 i T(1) = 3 i T(2) = 5 5≠1+3 (4) nie, bo T(0) = 2 i T(1) = 4 i T(2) = 8 8≠2+4 no to sprawdźmy (3) dowodzimy równość T(0)+T(1)+....+T(n) = T(n+1) indukctjnie krok 1 T(0) = 1 T(1) = 2¹⁻¹ = 2⁰=1 T(2) = 2²⁻¹ = 2¹ = 2 T(2) =2=1+1=T(0)+T(1) krok 2 Z: T(0)+T(1)+....+T(n) = T(n+1) T: T(0)+T(1)+....+T(n)+T(n+1) = T(n+2) dowód: T(0)+T(1)+....+T(n)+T(n+1) = T(n+1)+T(n+1) = 2*T(n+1) = 2*2ⁿ = 2ⁿ⁺¹ = T(n+2) c.b.d.u.