Zasada indukcji matematycznej to wygodna metoda dowodzenia twierdzeń dotyczących liczb naturalnych.
Znany jest wzór na sumę kolejnych liczb naturalnych:
\(S_n = 1+2+3+\ldots + n = \frac{n(n+1)}{2}\).
Spróbujmy go udowodnić. Łatwo sprawdzić, że dla małych wartości n ten wzór daje dobry wynik - powiedzmy, do n = 10, a dalej tracimy cierpliwość. Ale to, że dla \(n \leq 10\) wzór jest dobry, nie znaczy jeszcze, że dla wszystkich wartości n jest poprawny...
Spróbujmy sprawdzić wzór dla n = 11, ale nie bezpośrednimi rachunkami, dodając wszystkie liczby od 1 do 11. Zauważmy, że sumę liczb od 1 do 11 otrzymujemy, dodając 11 do sumy liczb od 1 do 10: S11 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) + 11 = S10 + 11.
Ale dla n = 10 sprawdziliśmy nasz wzór, więc w powyższych obliczeniach zamiast S10 możemy wstawić wartość obliczoną z wzoru:
\(S_{11} = S_{10} + 11 = \frac{10(10+1)}{2} + 11 = \frac{10\cdot 11}{2} + 11 = \frac{11(10 + 2)}{2} = \frac{11\cdot 12}{2}\).
Wynik jest zgodny ze wzorem, który dowodzimy! Zrobiliśmy więc krok naprzód - wzór został sprawdzony dla wszystkich \(n \leq 11\). A dzięki temu, że skorzystaliśmy ze sprawdzonej wcześniej prawdziwości wzoru dla n = 10, nie namęczyliśmy się zbytnio przy obliczeniach dla n = 11.
Co dalej? Zauważmy, że tej samej metody możemy użyć do sprawdzenia wzoru dla n = 12: S12 = S11 + 12; korzystamy z tego, że wiemy już, że wzór jest prawdziwy dla n = 11 i wstawiamy odpowiednią wartość: \(S_{12} = \frac{11\cdot 12}{2} + 12 = \frac{12\cdot 13}{2}\).
Widać już, że z prawdziwości wzoru dla n = 12 możemy tą samą metodą wywnioskować jego prawdziwość dla n = 13, a stąd wyprowadzimy wzór dla n = 14, potem n = 15, n = 16... Ogólnie umiemy udowodnić, że jeśli wzór jest prawdziwy dla pewnej liczby \(k \in \mathbb{N}\), to jest on prawdziwy również dla k + 1. Tą metodą po kilku godzinach udowodnilibyśmy wzór dla n = 1847, a po paru dniach dla może nawet dla n = 92334522.
Tak naprawdę umiemy udowodnić nasz wzór dla dowolnej zadanej wartości n - metoda jest znana, tylko może to wymagać dużo pracy, ponieważ dowód wzoru dla n wymaga, żebyśmy najpierw udowodnili go dla n − 1, czyli wcześniej musimy wykonać dowód dla n − 2, itd...
Wobec tego przydałoby nam się prawo, które mówiłoby, że gdy prawdziwość pewnego zdania umiemy dowodzić dla dowolnych \(n \in \mathbb{N}\), wykonując najpierw sprawdzenie dla małych liczb, a potem przeprowadzając dowód dla coraz większych liczb, aż do n, to owo zdanie jest prawdziwe dla wszystkich liczb naturalnych nie mniejszych od wartości, od których zaczęliśmy sprawdzanie.
Zasada indukcji matematycznej pozwala właśnie na prowadzenie dowodów w taki sposób:
|
Zasada indukcji matematycznej Niech A(n) będzie pewnym twierdzeniem matematycznym zależnym od liczby naturalnej \(n \in \mathbb{N}\). Jeśli spełnione są następujące warunki:
to wówczas twierdzenie A(n) jest prawdziwe dla każdego \(n \in \mathbb{N}\), \(n \geq n_0\). |
Możemy teraz porządnie dokończyć dowód z przykładu.
W tym przypadku twierdzenie A(n) brzmi "prawdziwy jest wzór \(S_n = \frac{n(n+1)}{2}\)".
Chcemy go udowodnić dla wszystkich liczb naturalnych, czyli n0 = 1.
Porządny opis dowodu indukcyjnego (czyli opartego na zasadzie indukcji) opiera się na następującym schemacie.
(0) Warto na początku napisać, że stosujemy zasadę indukcji - to ułatwia czytelnikowi zrozumienie dowodu.
(1) Pierwszy krok indukcyjny. Sprawdzamy prawdziwość twierdzenia dla małych wartości n, żeby mieć podstawę do wyprowadzania go dla większych n.
W naszym przykładzie wystarczy sprawdzić, że wzór działa dla n = 1: \(S_1 = 1 = \frac{1\cdot 2}{2}\).
(2) Główna część dowodu. Zakładamy teraz, że udowodniliśmy twierdzenie A(n) dla wszystkich \(n \in \mathbb{N}\) spełniających \(n_0 \leq n \leq k\) - to się nazywa założeniem indukcyjnym. Stąd chcemy wywnioskować prawdziwość twierdzenia A(k + 1).
Wracając do przykładu, zakładamy, że wzór jest prawdziwy dla n spełniających \(1 \leq n \leq k\). Chcemy wykazać, że \(S_{k+1} = \frac{k(k+1)}{2}\).
Wiemy, że Sk + 1 = Sk + k + 1.
Korzystamy z założenia indukcyjnego, zastępując w powyższej równości Sk przez \(\frac{k(k+1)}{2}\). Otrzymujemy
\(S_{k+1} = \frac{k(k+1)}{2} + k+1 = (k+1)(\frac{k}{2} + 1) = (k+1)(\frac{k+2}{2}) = \frac{(k+1)(k+2)}{2}\),
czyli nasz wzór dla n = k + 1.
(3) Stąd na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich liczb naturalnych niemniejszych od n0.
W naszym przypadku, wzór jest prawdziwy dla wszystkich \(n \in \mathbb{N}\).
Dowód. Przeprowadzimy dowód indukcyjny. (1) Sprawdzamy wzór dla n = 1:
\(S_1 = 1 = \frac{1\cdot 2}{2}\).
(2) Załóżmy teraz, że wzór jest prawdziwy dla n spełniających \(1 \leq n \leq k\). Chcemy wykazać, że \(S_{k+1} = \frac{k(k+1)}{2}\). Wiemy, że Sk + 1 = Sk + k + 1. Korzystamy z założenia indukcyjnego, zastępując w powyższej równości Sk przez \(\frac{k(k+1)}{2}\). Otrzymujemy \(S_{k+1} = \frac{k(k+1)}{2} + k+1 = (k+1)(\frac{k}{2} + 1) = (k+1)(\frac{k+2}{2}) = \frac{(k+1)(k+2)}{2}\), czyli tezę twierdzenia dla liczby k + 1.
Wobec tego na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla każdej liczby naturalnej.