Indukcja matematyczna

Indukcja polega na wyciąganiu ogólnych wniosków na podstawie skończenie wielu przypadków.
Przykładowo wielekroć obserwowaliśmy, Ŝe jabłko puszczone z pewnej wysokości spada. Newton
wywnioskował stąd ogólne prawo ciąŜenia. Podobnie obserwując codzienne wschody słońca moŜna po
pewnym czasie dojść do przekonania, Ŝe słońce zawsze wschodzi o świcie. Jak wiemy, w długim okresie
czasu nie będzie to jednak prawda. Zatem metoda indukcji jest zawodną metodą wnioskowania.

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 

Ponadto niech 

, zaś dla 

nawias kwadratowy oznacza tu część całkowitą liczby rzeczywistej. Wtedy 

 dla 

 oraz

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

 i

1.

dla kaŜdego 

 mamy 

.

2.

Istnienie takiego zbioru 

 przyjmuje się w teorii mnogości w zasadzie jako aksjomat. Z tej definicji

wynika natychmiast następująca zasada.

Twierdzenie 13..1 (Zasada indukcji matematycznej)   Jeśli 

 jest podzbiorem zbioru liczb naturalnych

 takim, Ŝe

 i

1.

dla kaŜdego 

 mamy teŜ 

,

2.

to wtedy 

 jest zbiorem wszystkich liczb naturalnych.

Dowód. Jeśli 

 spełnia warunki 1. i 2., to spełnia teŜ warunki definiujące w teorii mnogości zbiór liczb

naturalnych, więc 

. Z załoŜenia jednak 

, więc 

. 

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

 i

1.

dla kaŜdego 

, 

 pociąga 

,

2.

to wtedy

3.

dla kaŜdego 

 mamy 

.

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.

Twierdzenie 13..2 (Zasada minimum)   KaŜdy niepusty podzbiór zbioru liczb naturalnych zawiera
element najmniejszy.

Dowód. Niech 

 będzie niepustym podzbiorem 

 i niech

Przypuśćmy nie wprost, Ŝe 

 nie ma elementu najmniejszego. W szczególności 

 (bo   jest

najmniejszą liczbą naturalną), więc 

.

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

Zatem 

 to funkcja zdaniowa 

.

1. Przypadek 

 (sprawdzamy, Ŝe 

). Niech 

.

, więc 

 zachodzi.

2. Krok indukcyjny. Przypuśćmy

, Ŝe zachodzi 

. Udowodnimy

, tzn. 

.

Niech więc 

. Na mocy załoŜenia indukcyjnego, 

. Dlatego mamy

co kończy dowód kroku indukcyjnego.

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

Wtedy zdanie 

 jest równowaŜne zdaniu

które wynika z zasady indukcji matematycznej.

Zasada indukcji porządkowej.

Przed dowodem zwróćmy uwagę, Ŝe ta forma indukcji ma tylko jeden krok indukcyjny:

Jednak dla 

 zdanie to mówi, Ŝe

Poprzednik tej implikacji, czyli zdanie

jest prawdziwy (bo dla kaŜdego 

 jest fałszem), więc z 

 wynika w szczególności, Ŝe 

jest prawdą. Zatem ``pierwszy krok'' indukcji jest tu jakby ukryty.
Dowód 

. Dowód przeprowadzimy przy uŜyciu zasady minimum. Przypuśćmy nie wprost, Ŝe 

zachodzi, jednak zbiór 

 jest niepusty. Niech 

 będzie jego najmniejszym

elementem. Wówczas prawdą jest, Ŝe 

. Stosując 

 dla 

 dostajemy, Ŝe 

,

czyli 

, sprzeczność. 

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 

.

Łącznie liczba przekątnych 

 wynosi

co kończy dowód.

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

Mamy więc 

 i tak dalej. Ogólnie

moŜna udowodnić (przez indukcję), Ŝe

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.

Podobnie definiujemy potęgowanie, tzn funkcję dwuargumentową 

 dla 

 i 

.

ś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.