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.