Indukcja matematyczna - zasada, schemat dowodu i przykłady

Indukcja matematyczna to metoda dowodzenia twierdzeń prawdziwych dla wszystkich liczb naturalnych (od pewnego miejsca). Wystarczy pokazać, że twierdzenie zachodzi dla pierwszej liczby (baza) oraz że z jego prawdziwości dla dowolnej liczby $k$ wynika prawdziwość dla $k + 1$ (krok indukcyjny). Działa to jak domino: pierwsza kostka się przewraca, a każda przewraca następną - więc przewrócą się wszystkie.

Schemat dowodu

1. Baza indukcji. Sprawdź twierdzenie dla najmniejszej liczby, od której ma zachodzić (zwykle $n = 1$ albo $n = 0$).
2. Założenie indukcyjne. Załóż, że twierdzenie jest prawdziwe dla pewnego $k$.
3. Teza indukcyjna. Zapisz, co trzeba udowodnić dla $k + 1$.
4. Dowód kroku. Wyprowadź tezę z założenia.
5. Wniosek. Na mocy zasady indukcji twierdzenie zachodzi dla wszystkich $n$.

Przykład 1 - suma kolejnych liczb

Twierdzenie. $1 + 2 + \ldots + n = \frac{n(n + 1)}{2}$ dla każdego $n \ge 1$.

Baza. Dla $n = 1$: lewa strona to $1$, prawa $\frac{1 \cdot 2}{2} = 1$.

Krok. Załóżmy, że $1 + \ldots + k = \frac{k(k + 1)}{2}$. Wtedy

$1 + \ldots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2},$

czyli wzór zachodzi dla $k + 1$. Na mocy zasady indukcji zachodzi dla każdego $n$. $\blacksquare$

Tak samo dowodzi się, że suma $n$ pierwszych liczb nieparzystych to $n^2$: $1 + 3 + \ldots + (2n - 1) = n^2$.

Przykład 2 - podzielność

Twierdzenie. Liczba $n^3 - n$ jest podzielna przez $6$ dla każdego $n \ge 1$.

Baza. $1^3 - 1 = 0$, a $0$ dzieli się przez $6$.

Krok. Załóżmy, że $6 \mid k^3 - k$. Wtedy

$(k + 1)^3 - (k + 1) = k^3 + 3k^2 + 2k = (k^3 - k) + 3k(k + 1).$

Pierwszy składnik dzieli się przez $6$ z założenia, a $k(k + 1)$ - iloczyn dwóch kolejnych liczb - jest parzysty, więc $3k(k + 1)$ dzieli się przez $6$. Suma dzieli się przez $6$. $\blacksquare$

Przykład 3 - nierówności

Nierówność Bernoulliego. Dla $x \ge -1$ i każdego $n \ge 1$: $(1 + x)^n \ge 1 + nx$.

Krok indukcyjny: jeśli $(1 + x)^k \ge 1 + kx$, to mnożąc przez $1 + x \ge 0$:

$(1 + x)^{k+1} \ge (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2 \ge 1 + (k + 1)x.$

Baza nie zawsze to 1. Nierówność $2^n > n^2$ zachodzi dopiero od $n = 5$ ($32 > 25$); dla $n = 4$ mamy równość $16 = 16$, a dla $n = 3$ nierówność jest fałszywa ($8 < 9$). Dlatego bazą jest $n_0 = 5$, a w kroku korzysta się z tego, że $k \ge 5$: $2^{k+1} = 2 \cdot 2^k > 2k^2 \ge (k + 1)^2$.

Indukcja zupełna

W indukcji zupełnej (silnej) w kroku zakłada się prawdziwość twierdzenia dla wszystkich liczb od $n_0$ do $k$, a nie tylko dla $k$. Tak dowodzi się na przykład, że każda liczba naturalna większa od $1$ jest iloczynem liczb pierwszych: albo $k + 1$ jest pierwsza, albo jest iloczynem dwóch mniejszych liczb, a te - z założenia - są już iloczynami liczb pierwszych (zob. podstawowe twierdzenie arytmetyki).

Gdzie łatwo o błąd: „wszystkie konie są tej samej maści”

Słynny błędny „dowód” indukcyjny: w każdym stadzie $n$ koni wszystkie mają tę samą maść. Baza: stado z jednego konia. Krok: ze stada $k + 1$ koni usuwamy jednego - zostaje $k$ koni tej samej maści; usuwamy innego - znów $k$ koni tej samej maści; zbiory się pokrywają, więc wszystkie $k + 1$ koni ma tę samą maść.

Błąd tkwi w kroku z $k = 1$ do $k = 2$: dwa zbiory jednoelementowe nie mają wspólnego konia, więc nie da się „przenieść” maści. Krok indukcyjny musi działać dla każdego $k \ge n_0$ - tutaj zawodzi dokładnie w jednym miejscu, i to wystarczy, by cały dowód upadł.

Najczęstsze pytania

Na czym polega indukcja matematyczna? Na pokazaniu, że twierdzenie zachodzi dla pierwszej liczby i że jego prawdziwość dla dowolnej liczby $k$ pociąga prawdziwość dla $k + 1$. Wtedy zachodzi dla wszystkich kolejnych liczb.

Czy wystarczy sprawdzić twierdzenie dla wielu liczb? Nie. Sprawdzenie nawet milionów przypadków niczego nie dowodzi - np. wielomian $n^2 - n + 41$ daje liczby pierwsze dla $n = 1, \ldots, 40$, a dla $n = 41$ już nie (zob. ciąg Eulera). Indukcja obejmuje wszystkie $n$ naraz.

Czy bazą indukcji musi być 1? Nie - bazą jest najmniejsza liczba, dla której twierdzenie ma zachodzić. Dla $2^n > n^2$ bazą jest $5$.

Co to jest indukcja zupełna? Wariant, w którym w kroku zakłada się prawdziwość twierdzenia dla wszystkich liczb od bazy do $k$. Jest równoważna zwykłej indukcji, ale bywa wygodniejsza.

Podsumowanie

• Indukcja: baza $T(n_0)$ i krok $T(k) \Rightarrow T(k + 1)$ dają $T(n)$ dla wszystkich $n \ge n_0$.
• Przykłady: $1 + \ldots + n = \frac{n(n+1)}{2}$, $6 \mid n^3 - n$, $(1 + x)^n \ge 1 + nx$.
• Baza nie musi być równa $1$; krok musi działać dla każdego $k \ge n_0$.
• Indukcja zupełna zakłada prawdziwość dla wszystkich liczb do $k$.
• Więcej o metodach dowodzenia: rachunek zdań i twierdzenia z dowodami.