Potwierdzenie rekurencji

[matiss]

Hej,
obliczyłem w zadaniu iż moją rekurencję można zapisać w następujący sposób:
\(\displaystyle{ T(n)= \begin{cases} 1, n=0 \\ 2T(n-1), n>0 \end{cases}}\)

Muszę to jednak potwierdzić poprzez indukcję i szczerze mówiąc nie wiem jak się za to zabrać, może ktoś pomóc?

[Snayk]

Jaką rekurencję?

[matiss]

\(\displaystyle{ T(n)=2T(n-1)}\)

[Snayk]

Ale co tu potwierdzać indukcyjnie. Masz rekurencję określoną wzorem który napisałeś i co tu potwierdzać, przecież to definicja.

Jest jeszcze jakaś inna rekurencja w tym zadaniu?
Co to jest "moja" rekurencja?

[matiss]

W treści zadania mam pseudokod algorytmu, na podstawie tego pseudokodu obliczyłem kilka pierwszych wyrazów,\(\displaystyle{ T(0)=1. T(1)=2, T(2)=4, T(3)=8}\), z tego ułożyłem wcześniejszy zapis.
\(\displaystyle{ T(n)= \begin{cases} 1, n=0 \\ 2T(n-1), n>0 \end{cases}}\)

Oczywiście można zauważyć również że \(\displaystyle{ T(n)=2^n}\), jednak to co mam teraz to wzór wyededukowany na podstawie kilku pierwszych wartości, a tak być nie może, wzór należy udowodnić dla wszystkich \(\displaystyle{ n \in\NN}\).

Źle zapisałem wzór który potrzebuje udowodnić, muszę udowodnić prawdziwość:\(\displaystyle{ T(n)=2^n}\)

[Snayk]

Jedną z metod znajdowania wzorów jawnych ciągów rekurencyjnych jest po prostu zgadywanie.
W twoim przypadku nawet nie ma co zgadywać.

[matiss]

Ja to wiem Niestety jeśli oddam w ten sposób zadanie, jest ono niezaliczone, możemy spierać się o zasadność tego, ale takie zostały ustalone zasady.

[Premislav]

To udowodnij indukcyjnie. Dla \(\displaystyle{ n=1}\) działa, a dalej w kroku indukcyjnym jak masz \(\displaystyle{ T(k)=2^{k}}\) z założenia indukcyjnego, to \(\displaystyle{ T(k+1)}\) dzięki temu wzorowi rekurencyjnemu jest równe\(\displaystyle{ 2T(k)=2\cdot 2^{k}}\)

[matiss]

Czyli takie coś jest ok?
T(k+1)= 2^(k+1)
Z wcześniejszych informacji wiemy, iż:
T(k)=2T(k-1)
T(k+1)=2T(k+1-1)

L= T(k+1) P=2^(k+1)
L=2T(k)
L=2*2^k (z założenia)
L= 2^(k+1)
L=P