Indukcja matematyczna (indukcja zupełna) - zarys historyczny
Indukcja zupełna to po prostu inna (bardziej sprecyzowana) nazwa indukcji matematycznej, którą będziemy się tu zajmować, więc nie martwcie się, to nie jest żadna inna magia. Dlaczego postanowiłem o niej napisać? Dlatego, że przez dużą ilość czasu nie czaiłem dlaczego ona działa. Wydawało mi się, że z jej pomocą można udowodnić każdą bzdurę, tylko jakoś nie udało mi się wymyślić żadnej dowodliwej bzdury. Postanowiłem wierzyć matematykom na słowo, że zasada indukcji matematycznej działa.
Jednakże po pójściu na studia matematyczne zaczęło mnie to nurtować bardziej niż wcześniej. No i dopiero na Matematyce zrozumiałem o co w tym chodzi. Nic dziwnego - na studiach inżynierskich nie miałem teorii, żeby zrozumieć indukcję.
A więc zważając na to, że indukcji uczą na każdych studiach inżynierskich, opiszę wszystko od podstaw.
Zasada indukcji matematycznej (ZIM) - treść twierdzenia
Założenia
1. Niech \(T(n)\) będzie pewną własnością liczb naturalnych.
2. Niech zachodzi \(T(n_0)\).
3. Niech dla każdego \(n \geqslant n_0\) prawdziwa jest implikacja \(T(n) \implies T(n+1)\).
Teza
Jeśli spełnione są założenia, to wtedy dla każdej liczby naturalnej \(n \geqslant n_0\) zachodzi \(T(n)\).
O co w tym chodzi?
Teza zachodzi, gdy spełnione są założenia. Zatem zawsze, gdy chcemy skorzystać z zasady indukcji matematycznej, musimy mieć pewność, że prawdziwe są jej założenia (zresztą z każdym innym twierdzeniem należy obchodzić się również w taki sposób). W zadaniach to właśnie sprawdzanie założeń jest głównym problemem. Tylko co my tak naprawdę sprawdzamy?
\(T(n)\) ma być własnością liczb naturalnych, czyli funkcją taką, że po podstawieniu konkretnego \(n\) otrzymamy zdanie logiczne, które mówi coś o liczbach naturalnych. Co to jest zdanie logiczne? Zdanie, któremu możemy jednoznacznie przypisać prawdziwość lub fałszywość. Taką wartością \(T(n)\) może być na przykład wszystkie liczby naturalne są większe od \(-1\) (\(T(n)\)dla \(n=1\)). Uwaga! Zdaniami logicznymi są również zdania fałszywe, np. wszystkie liczby naturalne są większe od \(43\).
Okazuje się, że do korzystania z ZIM \(T(n)\) nie musi być prawdziwe dla wszystkich liczb naturalnych. Musi być natomiast prawdziwe dla prawie wszystkich, czyli dla wszystkich od pewnego miejsca, np. dla wszystkich liczb naturalnych większych od \(100\).
Drugie założenie mówi, że ma zachodzić \(T(n_0)\). To jest chyba w miarę jasny punkt: istnieje jakaś liczba naturalna, którą nazywamy \(n_0\) i dla niej \(T(n)\) jest zdaniem prawdziwym. Trzecie założenie mówi, że najlepiej, jeśli \(n_0\) jest najmniejszą liczbą naturalną, dla której \(T(n)\) jest prawdziwe.
Trzecie założenie jest chyba najbardziej niejasne. Długo zastanawiałem się: o co chodzi z tą implikacją? Implikacja ma być prawdziwa. Co to znaczy? Implikację można opisać taką tabelką prawdy:
\[ \newcommand\T{\Rule{0pt}{1em}{.3em}}
\begin{array}{|c|c|c|}
\hline p & q & p \implies q \T \\\hline
0 & 0 & 1 \\\hline
0 & 1 & 1 \\\hline
1 & 0 & 0 \\\hline
1 & 1 & 1 \\\hline
\end{array}
\]
\(1\) oznacza prawdziwość zdania, a \(0\) jego fałszywość. Tabelka mówi tyle: implikacja \(p \implies q\) jest prawdziwa, gdy \(p\) jest fałszywe lub gdy \(p,q\) są prawdziwe. Implikacja jest fałszywa, gdy \(p\) jest prawdziwe, a \(q\) fałszywe.
Założenie naszego twierdzenia mówi: Niech dla każdego \(n \geqslant n_0\) prawdziwa jest implikacja \(T(n) \implies T(n+1)\). Implikacja \(T(n) \implies T(n+1)\) jest prawdziwa wtedy i tylko wtedy, gdy \(T(n)\) jest fałszywe lub \(T(n),T(n+1)\) są prawdziwe. Zauważmy, że z wcześniejszego założenia (u mnie był to numerek 2.) mamy, że \(T(n_0)\) ma być prawdziwe.
Założenie, w którym jesteśmy teraz (czyli numer 3.) mówi, że implikacja ma być prawdziwa dla \(n_0\) i dla większych od niego liczb. Przypominam, że zdanie wcześniej przypomniałem, że \(T(n_0)\) jest prawdziwe, więc nie ma szans, żeby \(T(n)\) było fałszywe dla wszystkich \(n \geqslant n_0\). Skoro \(T(n_0)\)jest prawdziwe, to implikacja \(T(n) \implies T(n+1)\) może być prawdziwa dla \(n_0\) tylko wtedy, gdy \(T(n_0+1)\) jest prawdziwe.
Jeśli to zrozumiałeś, to możesz być z siebie zadowolony, bo zrozumiałeś najtrudniejszą rzecz w zrozumieniu tego, co się tak naprawdę robi w zadaniach z użyciem zasady indukcji matematycznej. Jeśli nie zrozumiałeś, to przeczytaj ten akapit jeszcze raz, powoli, ze zrozumieniem. Mam nadzieję, że wtedy wszystko będzie jasne.
Ale to jeszcze nie koniec wyjaśnień. Napisałem tak: Implikacja \(T(n) \implies T(n+1)\) może być prawdziwa dla \(n_0\) tylko wtedy, gdy \(T(n_0+1)\) jest prawdziwe. W takim razie jest możliwe tylko jedno wyjście, jeśli chodzi o prawdziwość implikacji z założenia: \(T(n)\) jest prawdziwe i \(T(n+1)\). Prawdziwość \(T(n+1)\) ma wynikać z prawdziwości \(T(n)\). Czy wynika? Jeszcze nie wiemy.
Załóżmy, że dla każdego \(n \geqslant n_0\) prawdziwe jest \(T(n)\). Sprawdźmy czy prawdziwe jest \(T(n+1)\). Jeśli tak, to implikacja jest prawdziwa. Jeśli nie, to implikacja jest fałszywa i nie możemy skorzystać z ZIM.
Tutaj dochodzi kolejna możliwość problemu ze zrozumieniem: skąd wiemy, że \(T(n)\) jest prawdziwe? Odpowiedź: nie wiemy. Ale JEŻELI przy prawdziwym \(T(n)\) prawdziwe jest też \(T(n+1)\), to możemy skorzystać z twierdzenia o indukcji matematycznej. Dlaczego możemy? Zapraszam do dowodu tego twierdzenia, który znajduje się na dole strony ;) Dlaczego MOŻEMY założyć, że \(T(n)\) jest prawdziwe?
Dlatego, że to jest jedyny sposób sprawdzenia prawdziwości implikacji. Jeżeli jest fałszywe, to implikacja i tak jest prawdziwa. Natomiast nie wiemy co jest, jeśli \(T(n)\) jest prawdziwe - i to właśnie sprawdzamy. To jest główna część zadania, w którym dowodzimy coś indukcyjnie.
Sprawdziliśmy wszystkie założenia. Możemy przejść do tezy. A ona mówi tyle, że \(T(n)\) jest prawdziwe dla wszystkich \(n \geqslant n_0\). A zazwyczaj to właśnie trzeba udowodnić.
Przykład rozwiązania zadania z użyciem twierdzenia o indukcji matematycznej
Podam treść tego samego zadania, zapisaną na 3 różne sposoby, z którymi możecie się spotkać. Wariantów jest jeszcze więcej, ale są podobne.
Udowodnij indukcyjnie, że dla wszystkich liczb naturalnych \(n \geqslant 7\) zachodzi \(2^n > n+120\).
Udowodnij indukcyjne, że \(\forall n \colon \left(\left(n \in \mathbb{N} \wedge n \geqslant 7 \right) \implies 2^n>n+120 \right)\).
Udowodnij indukcyjnie, że \(\bigwedge_{n \in \mathbb{N}} \ n \geqslant 7 \implies 2^n > n+120\).
Okej, rozwiązujemy. Pierwsze założenie? Spełnione. Naszym \(T(n)\) jest \(2^n > n+120\).
Drugie założenie? Naszym \(n_0\) jest \(7\), co jest podane w treści zadania. Sprawdźmy czy zachodzi (czyli czy jest prawdziwe) \(T(n_0)\). \(T(7) \equiv 2^7 > 7+120 \iff 128 > 127\) - to jest prawdziwe! Super, drugie założenie jest spełnione.
Zobaczmy czy spełnione jest trzecie założenie. Załóżmy, że dla ustalonego \(n \geqslant 7\) zachodzi \(2^n > n+120 \) (czyli \(T(n)\)). Sprawdźmy czy zachodzi wtedy \(T(n+1)\), czyli \(2^{n+1} > (n+1)+120\).
\[ 2^{n+1}=2^n \cdot 2^1 = 2 \cdot 2^n > 2 \cdot (n+120) = 2n+240 > n+240 > n+121 = \\
= n+120+1 = (n+1)+120
\]
Jak widać, \(T(n+1)\) jest prawdziwe, więc prawdziwa jest implikacja \(T(n) \implies T(n+1)\), więc prawdziwe jest trzecie założenie. Zatem wszystkie 3 założenia są spełnione. Zatem zachodzi teza twierdzenia o indukcji matematycznej, czyli prawdziwe jest \(T(n)\) dla każdego \(n \geqslant 7\), czyli dla każdego \(n \geqslant 7\) zachodzi \(2^n > n+120\), co należało udowodnić.
W miarę ładne rozwiązanie, którego prawdopodobnie oczekuje twój nauczyciel na sprawdzianie
1. Dla \(n=7\) mamy \(2^7=128>127=7+120\).
2. Załóżmy, że dla ustalonego \(n\) zachodzi \(2^n > n+120 \). Wtedy:
\[ 2^{n+1}=2^n \cdot 2^1 = 2 \cdot 2^n > 2 \cdot (n+120) = 2n+240 > n+240 > n+121 = \\
= n+120+1 = (n+1)+120
\]
Zatem na mocy zasady indukcji matematycznej \(2^n > n+120\) dla każdego \(n \geqslant 7\).
Próba udowodnienia bzdury za pomocą twierdzenia o indukcji matematycznej
Z dowodu zasady indukcji matematycznej, który znajdziemy na dole tej strony, wynika, że nie da się za pomocą tego twierdzenia udowodnić bzdury. Zobaczmy które założenie nie jest spełnione. Spróbujmy udowodnić, że dla każdego \(n \in \mathbb{N}\) zachodzi \(n=n^2\).
1. Dla \(n=0\) mamy \(n=0=0^2=n^2\), więc własność jest prawdziwa.
2. Załózmy, że dla ustalonego \(n\) zachodzi \(n=n^2\). Wtedy \(n+1=n^2+1\), ale \(n^2+1 \neq (n+1)^2=n^2+1+2n\). Więc założenie o prawdziwości implikacji nie zachodzi, więc nie możemy skorzystać z ZIM.
Dowód zasady indukcji matematycznej
Dowód zostawiam dla chętnych, student studiów inżynierskich nie musi ani go znać, ani rozumieć. Najpierw przypomnę treść twierdzenia.
Założenia
1. Niech \(T(n)\) będzie pewną własnością liczb naturalnych.
2. Niech zachodzi \(T(n_0)\).
3. Niech dla każdego \(n \geqslant n_0\) prawdziwa jest implikacja \(T(n) \implies T(n+1)\).
Teza
Jeśli spełnione są założenia, to wtedy dla każdej liczby naturalnej \(n \geqslant n_0\) zachodzi \(T(n)\).
Dowód
Wiemy z założeń, że własność \(T(n)\) jest prawdziwa dla \(n=n_0\) i dla każdego \(n \geqslant n_0\) zachodzi implikacja \(T(n) \implies T(n+1)\). Załóżmy nie wprost, że teza ZIM jest nieprawdziwa, czyli nieprawda, że \(\forall n \geqslant n_0 \colon T(n)\).
Wtedy zbiór liczb naturalnych większych lub równych \(n_0\), dla których własność jest nieprawdziwa, jest niepusty: \( \{n \geqslant n_0 \colon \neg T(n)\} \neq \varnothing \). Oznaczmy przez \(k_0\) najmniejszy element tego zbioru. Wiemy z założenia, że \(T(n_0)\) jest prawdziwe, więc \(k_0 \neq n_0\), więc \(k_0=k+1\) dla pewnego \(k \geqslant n_0\).
\(k=k_0-1\), a \(k_0\) jest najmniejszą liczbą, dla którego \(T\) nie zachodzi, zatem \(T(k)\) zachodzi. Skoro \(k \geqslant n_0\), to z założenia o prawdziwości implikacji \(T(n) \implies T(n+1)\) dla każdego \(n \geqslant n_0\), musi być prawdziwe też \(T(k+1)\), czyli \(T(k_0)\). Jest to sprzeczne z założeniem, że \(T(k_0)\) nie zachodzi. Zatem \(\forall n \geqslant n_0 \colon T(n)\), co kończy dowód.