Potwierdzenie rekurencji
-
- Użytkownik
- Posty: 32
- Rejestracja: 31 sie 2011, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: polska
- Podziękował: 2 razy
Potwierdzenie rekurencji
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?
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?
-
- Użytkownik
- Posty: 32
- Rejestracja: 31 sie 2011, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: polska
- Podziękował: 2 razy
Potwierdzenie rekurencji
\(\displaystyle{ T(n)=2T(n-1)}\)
Ostatnio zmieniony 20 sty 2015, o 11:26 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
- Użytkownik
- Posty: 422
- Rejestracja: 13 cze 2012, o 21:30
- Płeć: Mężczyzna
- Lokalizacja: Wroc
- Podziękował: 25 razy
- Pomógł: 64 razy
Potwierdzenie rekurencji
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?
Jest jeszcze jakaś inna rekurencja w tym zadaniu?
Co to jest "moja" rekurencja?
-
- Użytkownik
- Posty: 32
- Rejestracja: 31 sie 2011, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: polska
- Podziękował: 2 razy
Potwierdzenie rekurencji
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}\)
\(\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}\)
Ostatnio zmieniony 20 sty 2015, o 11:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
-
- Użytkownik
- Posty: 32
- Rejestracja: 31 sie 2011, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: polska
- Podziękował: 2 razy
Potwierdzenie rekurencji
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
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Potwierdzenie rekurencji
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}}\)
-
- Użytkownik
- Posty: 32
- Rejestracja: 31 sie 2011, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: polska
- Podziękował: 2 razy
Potwierdzenie rekurencji
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
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