Rekurencja, dowód indukcyjny.

[NogaWeza]

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:
\(\displaystyle{ f(1) = \alpha \\ f(2n) = 2f(n) + \beta \\ f(2n+1) = 2f(n) + \gamma}\)

Chciałym pokazać indukcyjnie, że \(\displaystyle{ f(n) = 2^m \alpha+ (2^m - l - 1) \beta + l \gamma}\) jest rozwiązaniem tej rekurencji; przy czym \(\displaystyle{ 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 \(\displaystyle{ m=0}\) i \(\displaystyle{ l=0}\) zachodzi \(\displaystyle{ f(1) = \alpha}\), więc przechodzę dalej.

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

\(\displaystyle{ 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 \(\displaystyle{ m}\) wynika prawdziwość dla \(\displaystyle{ 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 \(\displaystyle{ m}\). Odnoszę wrażenie, że przy tej indukcji względem \(\displaystyle{ 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 \(\displaystyle{ m}\) do \(\displaystyle{ m+1}\) mam wrażenie, że coś gubię.

Będę ogromnie wdzięczny za rozwianie moich wątpliwości i słowo komentarza.

[jutrvy]

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

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

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

\(\displaystyle{ (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 \(\displaystyle{ n}\), ponieważ jeśli napisalibyśmy twierdzenie używając kwantyfikatorów, to miałoby ono postać:

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

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

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

Więc robisz de facto indukcję nie po \(\displaystyle{ \NN^2}\) tylko po \(\displaystyle{ \NN}\), więc to jest taka standardowa indukcja, tylko wyraziłeś liczbę \(\displaystyle{ n}\) w postaci \(\displaystyle{ 2^m + l}\) i podzieliłeś indukcję na dwa przypadki, tzn gdy \(\displaystyle{ l}\) jest parzyste i gdy \(\displaystyle{ 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 \(\displaystyle{ 2^m}\), bo nie zrobiłeś przejścia z \(\displaystyle{ 2^m + l}\), gdzie \(\displaystyle{ l = 2^m -1}\) do \(\displaystyle{ 2^{m+1}}\) i tu faktycznie niektóre szczeble drabiny gubisz

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

Pozdrawiam

[NogaWeza]

Wydaję mi się, że teraz już rozumiem o co chodzi. Dziękuję bardzo za pomoc.