Podobnie w matematyce można obserwować, że pewne własności liczb
naturalnych przysługują kolejno liczbom
Po
sprawdzeniu wielu takich liczb pojawia sie pokusa, by metodą indukcji
przyjąć, że dana własność przysługuje wszystkim liczbom
naturalnym. Droga ta prowadzić może na manowce.
Przykład. Niech
zaś dla
W odróżnieniu od zawodnej metody indukcji opisanej powyżej, indukcja matematyczna jest jak najbardziej niezawodną metodą dowodzenia twierdzeń. Nazwa tej metody bierze się z pewnego zewnętrznego podobieństwa do metody indukcji.
Indukcja matematyczna dotyczy własności liczb naturalnych.
W rozdziale 11 podaliśmy, jak w teorii mnogości definiuje się
liczby naturalne. Przypomnijmy, że to zbiór pusty
,
zaś liczba
to zbiór
. W teorii mnogości definiuje
się zbiór liczb naturalnych
jako najmniejszy zbiór
taki, że
Zasadę indukcji matematycznej formułuje się również w nieco innej
postaci, w której można ją stosować bezpośrednio do dowodzenia twierdzeń. Mianowicie, dla każdej funkcji zdaniowej
, jeżeli
Zasada indukcji matematycznej w tej formie wynika z twierdzenia 13.1,
gdy za przyjmiemy wykres funkcji zdaniowej
. Punkty
1. i 2. w tej zasadzie nazywamy krokami indukcyjnymi (w punkcie
1. często pomijamy tę nazwę). Zdanie
nazywamy tezą
indukcyjną (tezą indukcyjną nazywa się też samą funkcję
zdaniową
).
Formalnie zasadę indukcji matematycznej dla funkcji zdaniowej
możemy zapisać w postaci zdania
Z zasady indukcji matematycznej wynika tak zwana zasada minimum.
Przypuśćmy teraz,
że . Znaczy to, że
jest rozłączny z
. Jeśli teraz
, to
byłaby najmniejszą liczbą w
, sprzeczność. Dostajemy więc
, czyli również
i
.
W ten sposób widzimy, że zbiór spełnia założenia
twierdzenia 13.1. Dlatego wnioskujemy, że
. Znaczy to jednak,
że
, sprzeczność.
Przykład. Udowodnimy metodą indukcji matematycznej
nierówność Bernoulliego: dla i
mamy
.
Nasza teza indukcyjna to
1. Przypadek (sprawdzamy, że
). Niech
.
, więc
zachodzi.
2. Krok indukcyjny. Przypuśćmy13.2, że zachodzi
. Udowodnimy
, tzn.
.
Niech więc .
Na mocy założenia indukcyjnego,
. Dlatego mamy
Z zasady indukcji matematycznej wnioskujemy, że teza indukcyjna
zachodzi dla wszystkich
.
Stosuje się też różne warianty zasady indukcji matematycznej.
Indukcja od miejsca
.
Dowód. Wprowadzamy nową funkcję zdaniową
wzorem
Zasada indukcji porządkowej.
Przed dowodem zwróćmy uwagę, że ta forma indukcji ma tylko jeden
krok indukcyjny:
Przykład. Udowodnimy, że liczba przekątnych -kąta
wypukłego jest równa
.
Niech
oznacza funkcję zdaniową: `` liczba przekątnych
-kąta
wypukłego jest równa
''. Wówczas nasza teza
indukcyjna ma postać
.
1. Sprawdzamy, że teza zachodzi dla . Wówczas
i jest to
rzeczywiście liczba przekątnych trójkąta.
2. Krok indukcyjny. Przypuśćmy, że oraz
jest
prawdziwe. Udowodnimy
.
W tym celu rozważmy
-kąt wypukły
o wierzchołkach
. Wówczas
są wierzchołkami
-kąta
wypukłego
, który z założenia indukcyjnego ma
przekątnych.
Przekątne to dokładnie przekątne
i dodatkowo
przekątnych lączących
z wierzchołkami
oraz przekątna
.
Definicje rekurencyjne (indukcyjne).
Jeśli dana jest liczba
i funkcja
o dziedzinie
, to
możemy zdefiniować nową funkcję
o dziedzinie
(czyli:
ciąg), która spełnia następujący układ warunków
W definicji tej podajemy wartość funkcji dla argumentu
, a
następnie wyznaczamy wartości
dla kolejnych liczb naturalnych
posługując się rekurencyjnym warunkiem
. W wariantach tej metody możemy określać
wartości funkcji
dla kilku początkowych argumentów, a
następnie w warunku rekurencyjnym wartość
moze zależeć od
wartości
dla kilku poprzednich argumentów. W ten sposób
definiujemy poniżej ciąg Fibonacciego. Używając zasady indukcji matematycznej można
udowodnić, że w istocie istnieje jedyna funkcja
określona tymi
warunkami. Łatwiej jednak zrozumieć ten fakt na przykładzie.
Przykład. Ciąg Fibonacciego określony jest warunkami
Schemat definicji rekurencyjnej funkcji i więcej zmiennych
wygląda podobnie.
oznacza tu liczbę naturalną, zaś
i
są danymi funkcjami o odpowiednich dziedzinach. Wówczas definiujemy
nową funkcje
określoną warunkami
Przykład. Niech
oznacza funkcję
następnika, tzn.
. Używając tej funkcji możemy
zdefiniować rekurencyjnie dwuargumentowe funkcje dodawania i
mnożenia liczb naturalnych.
ściśle rzecz biorąc, operacje
i
również są zdefiniowane rekurencyjnie (dla danego ciągu
).
W wielu definicjach i rozumowaniach przeprowadzanych pozornie bez
użycia indukcji tkwi ona jednak ukryta pod sformułowaniami typu ``i
tak dalej'' lub napisami typu ``''. Odnosi się to również
często do sytuacji, gdzie zastępujemy dowód używający jawnie
indukcji matematycznej przez dowód jakoby do tej zasady się nie odwołujący.
Ludomir Newelski 2006-08-29