szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 sie 2017, o 16:19 
Użytkownik

Posty: 1491
Lokalizacja: Kraków
Witam serdecznie. Wpadła mi w ręce Matematyka konkretna i chciałbym się czegoś nauczyć podczas czytania tej książki, dlatego będę zadawał pytania na forum. Proszę o wyrozumiałość, jestem humanistą (I wish) ;)

Jest rekurencja zadana następująco:
f(1) = \alpha \\ f(2n) = 2f(n) + \beta \\ f(2n+1) = 2f(n) + \gamma

Chciałym pokazać indukcyjnie, że f(n) = 2^m \alpha+ (2^m - l - 1) \beta + l \gamma jest rozwiązaniem tej rekurencji; przy czym n = 2^m + l , \quad 0  \le l < 2^m

Oto moje podejście. Sama postać rekurencji sugeruje, żeby osobno rozpatrzeć przypadek parzysty i nieparzysty. Dla m=0 i l=0 zachodzi f(1) = \alpha, więc przechodzę dalej.

Zakładam, że zachodzi f(2^m + l) = 2^m \alpha+ (2^m - l - 1) \beta + l \gamma dla dowolnego, ale ustalonego m i parzystego l.
Gdy n = 2^m +l jest parzyste, czyli gdy l jest parzyste mamy:

f(2^{m+1} + l) = f \left( 2 \left( 2^m + \frac{l}{2} \right) \right)  = 2f \left( 2^m + l\right)  +
 \beta = \\ = 2 \left[ \alpha 2^m + \beta \left( 2^m - 1 - \frac{l}{2} \right) + \gamma \frac{l}{2} \right] + \beta = ... = \alpha 2^{m+1} + \beta \left( 2^{m+1} - l - 1 \right) + \gamma l

Pokazałem, że z prawdziwości dla m wynika prawdziwość dla m+1 (wykorzystałem założenie indukcyjne na początku drugiej linijki).
Nieparzysty przypadek rozpatrzyłem analogicznie, nie będę go przepisywał. Moje pytanie: czy to rozumowanie jest poprawne? Nie wiem czy mogę tak sobie stosować indukcję względem m. Odnoszę wrażenie, że przy tej indukcji względem m sporo liczb pomijam. W klasycznym przypadku indukcja kojarzy mi się z wchodzeniem po drabince szczebel po szczeblu (tj. kolejne liczby naturalne), a tutaj przy przejściu z m do m+1 mam wrażenie, że coś gubię.

Będę ogromnie wdzięczny za rozwianie moich wątpliwości i słowo komentarza.
Góra
Mężczyzna Offline
PostNapisane: 23 sie 2017, o 00:42 
Użytkownik
Avatar użytkownika

Posty: 1229
Ogólnie, jak chcesz udowodnić twierdzenie, które mówi, że dla dowolnych liczb naturalnych n,m zachodzi T(m,n), to trzeba to zrobić w ten sposób:

1. Krok zerowy, tzn. dla (m,l) = (0,0).
2. Krok indukcyjny "pierwszy" załóżmy, że teza zachodzi dla pary (m,0), gdzie m > 0. Należy pokazać, że teza zachodzi dla pary (m+1, 0).
3. Krok indukcyjny "po drugiej współrzędnej". Ustalamy l > 0. Chcemy pokazać, że jeśli dla dowolnego m spełnione jest twierdzenie dla pary liczb (m,l), to twierdzenie jest też prawdziwe dla pary (m, l+1).

Mam nadzieję, że rozjaśniłem. Generalnie intuicja jest taka, że "po tej drabince" wspinamy się tak:

(0,0), (1, 0), (2,0), \ldots, (k, 0), \ldots, (1,1), (2,1), (3,1), \ldots, (k,1),\ldots, (1,2), (2,2), (3,2), \ldots

W przypadku tego zadania, robimy tak na prawdę indukcję tylko po n, ponieważ jeśli napisalibyśmy twierdzenie używając kwantyfikatorów, to miałoby ono postać:

\forall m\in\NN \forall l\in\{0,1,\ldots, 2^m-1\} T(m,l), co można zastąpić przez

\forall m\in\NN T'(m), gdzie T'(m) to twierdzenie, które ma postać:

\forall l\in\{0,1,\ldots, 2^m-1\} T(m,l).

Więc robisz de facto indukcję nie po \NN^2 tylko po \NN, więc to jest taka standardowa indukcja, tylko wyraziłeś liczbę n w postaci 2^m + l i podzieliłeś indukcję na dwa przypadki, tzn gdy l jest parzyste i gdy l jest nieparzyste i wszystko jest ok. Masz tu po prostu dwa typy wchodzenia po drabince: albo z nieparzystego szczebla wchodzisz na parzysty szczebel albo z parzystego szczebla wchodzisz na nieparzysty, i już.

Jest tylko mały mankament - tzn pownieneś udowodnić, że twierdzenie jest prawdziwe dla wszystkich liczb postaci 2^m, bo nie zrobiłeś przejścia z 2^m + l, gdzie l = 2^m -1 do 2^{m+1} i tu faktycznie niektóre szczeble drabiny gubisz :(

Uff... ale długie, mam nadzieję, że trochę pomoże...

Pozdrawiam :)
Góra
Mężczyzna Offline
PostNapisane: 23 sie 2017, o 08:32 
Użytkownik

Posty: 1491
Lokalizacja: Kraków
Wydaję mi się, że teraz już rozumiem o co chodzi. Dziękuję bardzo za pomoc.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dowód wykazać że graf jest Eulerowski  superes  1
 Rekurencja liniowa niejednorodna - funkcja tworząca  conqueror  7
 Rekurencja liniowa i wzór jawny  Mardax  5
 dowód kombinatoryczny - zadanie 5  bellaa87  1
 Rekurencja - wzór jawny  kheops  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl