Indukcja matematyczna – teoria
Definicja schematu dowodu, wersja od \(k_0\), jak pisać dowody i na co uważać.
1 O co chodzi w indukcji
Indukcja matematyczna to metoda dowodzenia zdań o liczbach naturalnych. Zamiast sprawdzać osobno \(T(1),T(2),T(3),\dots\), wykonujemy dwa kroki:
- pokazujemy, że zdanie jest prawdziwe dla pewnej pierwszej liczby (to jest start),
- pokazujemy, że jeśli jest prawdziwe dla pewnego \(n\), to jest prawdziwe także dla \(n+1\) (to jest przejście).
Wtedy prawdziwość „przechodzi” na wszystkie kolejne liczby naturalne.
Jak rozumieć to intuicyjnie
Możesz myśleć o szeregu kostek domina: jeśli przewrócisz pierwszą, a każda przewraca następną, to w końcu przewrócą się wszystkie.
W indukcji:
- „pierwsza kostka” to warunek startowy (baza),
- „każda przewraca następną” to krok indukcyjny \(T(n)\Rightarrow T(n+1)\).
2 Twierdzenie o indukcji zupełnej
Niech \(T(n)\) będzie zdaniem (formą zdaniową) o liczbie naturalnej \(n\), czyli \(n\in\mathbb{N}\).
Załóżmy, że spełnione są dwa warunki:
- \(T(1)\) jest prawdziwe,
- dla każdego \(n\in\mathbb{N}\) prawdziwa jest implikacja \(T(n)\Rightarrow T(n+1)\).
Wtedy dla każdej liczby naturalnej \(n\) zdanie \(T(n)\) jest prawdziwe.
W warunku 2:
- \(T(n)\) nazywamy założeniem indukcyjnym,
- \(T(n+1)\) nazywamy tezą indukcyjną.
3 Wersja indukcji od \(k_0\)
Niech \(T(n)\) będzie zdaniem o \(n\in\mathbb{N}\). Załóżmy, że:
- \(T(k_0)\) jest prawdziwe dla pewnej liczby naturalnej \(k_0\),
- dla każdego \(n\in\mathbb{N}\) zachodzi implikacja \(T(n)\Rightarrow T(n+1)\).
Wtedy dla każdego \(n\ge k_0\) zdanie \(T(n)\) jest prawdziwe.
Ta wersja jest szczególnie przydatna, gdy zdanie nie ma sensu (albo nie jest prawdziwe) dla małych \(n\), np. zaczyna działać dopiero od \(n=2\) lub \(n=3\).
4 Uniwersalny schemat dowodu indukcyjnego
Krok 1. Baza indukcyjna (start): sprawdź \(T(1)\) albo \(T(k_0)\).
Krok 2. Założenie indukcyjne: przyjmij, że \(T(n)\) jest prawdziwe dla pewnego, ale ustalonego \(n\ge 1\) (albo \(n\ge k_0\)).
Krok 3. Krok indukcyjny: wykaż, że z założenia \(T(n)\) wynika \(T(n+1)\). To zwykle oznacza rachunki prowadzące od lewej strony w \(T(n+1)\) do prawej, z wykorzystaniem założenia.
Krok 4. Wniosek: napisz, że na mocy indukcji \(T(n)\) jest prawdziwe dla wszystkich \(n\) (albo dla wszystkich \(n\ge k_0\)).
Najczęstszy „szkielet” zapisu (do kopiowania)
Sprawdzimy tezę indukcyjnie.
1. (Baza) Dla \(n=1\) (lub \(n=k_0\)) zachodzi …
2. (Założenie) Przyjmijmy, że dla pewnego \(n\ge 1\) zachodzi …
3. (Krok) Wtedy …, więc zachodzi … dla \(n+1\).
4. Wobec tego, na mocy indukcji, … dla wszystkich \(n\in\mathbb{N}\) (lub \(n\ge k_0\)).
5 Jak robić krok indukcyjny w praktyce
Co najczęściej działa:
- zapisz \(T(n+1)\) i spróbuj przekształcić lewą stronę, aż pojawi się fragment równy temu, co masz w \(T(n)\),
- wstaw założenie indukcyjne dokładnie w tym miejscu, gdzie pasuje,
- na końcu doprowadź rachunek do postaci \(T(n+1)\).
Na co uważać:
- w kroku indukcyjnym nie wolno zakładać „od razu”, że \(T(n+1)\) jest prawdziwe,
- założenia indukcyjnego nie wolno używać dla innych liczb niż \(n\) (np. dla \(n+1\) lub \(n-1\)),
- nie wystarczy sprawdzić kilku pierwszych wartości \(n\) – to nie jest dowód.
Mini-przykład: jak „podstawić” założenie
Jeśli założenie indukcyjne ma postać
\[ 1+2+\dots+n=\frac{n(n+1)}{2}, \]
to w kroku indukcyjnym zaczynasz od
\[ 1+2+\dots+n+(n+1) \]
i zamieniasz fragment \(1+2+\dots+n\) na \(\frac{n(n+1)}{2}\), bo dokładnie to mówi założenie.
6 Typowe błędy w indukcji
- Brak bazy indukcyjnej albo sprawdzenie złej bazy (np. zadanie działa dopiero od \(n=2\), a sprawdzono \(n=1\)).
- Niedokładny krok indukcyjny: „widać, że” bez rachunków, bez pokazania miejsca użycia założenia.
- Używanie założenia indukcyjnego w niewłaściwej formie (np. bez przepisania go dokładnie i jednoznacznie).
- Zapominanie o warunkach (np. \(n\ge 1\), dodatniość \(a,b\), itp.), które są potrzebne w przekształceniach.
- „Sprawdzenie kilku przykładów” zamiast dowodu.
Jak sprawdzić, czy dowód jest kompletny
Po skończeniu dowodu zadaj sobie trzy pytania:
- Czy baza została sprawdzona dla właściwej liczby startowej?
- Czy w kroku indukcyjnym jasno napisałem, gdzie i jak użyłem \(T(n)\)?
- Czy na końcu jest wniosek „na mocy indukcji” z poprawnym zakresem \(n\) (od 1 albo od \(k_0\))?
