Najczęściej stosowane sformułowanie zasady indukcji wykorzystuje fakt, że każdy podzbiór A jakiegoś zbioru, wyznacza pewną właściwość (własność) W przysługującą tylko elementom tego podzbioru. Niech więc W(n) będzie własnością liczb naturalnych, wtedy zasada indukcji matematycznej może być sformułowana następująco:

Dowody twierdzeń matematycznych wykorzystujące zasadę indukcji nazywamy dowodami indukcyjnymi.

Na czym polega dowód indukcyjny? Najpierw pokazujemy, że rozważana własność przysługuje liczbie naturalnej 0. Ten etap dowodu nazywamy bazą indukcji. Następnie zakładamy, że dla jakiegoś n, rozważana własność przysługuje liczbie n, czyli zakładamy W(n). O tym założeniu mówimy, że jest to założenie indukcyjne. Z założenia indukcyjnego dowodzimy tezy indukcyjnej, tzn. dowodzimy, że własność W przysługuje następnej liczbie naturalnej n+1. Ten etap dowodu indukcyjnego nazywamy krokiem indukcyjnym. Teraz pozostaje już tylko do wyciągnięcia wniosek, że rozważana własność W przysługuje wszystkim liczbom naturalnym.

Ideę dowodu indukcyjnego zilustrujemy na kilku przykładach.

Dowód.

Oznaczmy przez W zdanie wyrażające własność liczb naturalnych taką, że

W(n) wttw liczba podzbiorów zbioru n elementowego wynosi 2ⁿ.

Baza indukcji. Ponieważ zbiór pusty ma dokładnie jeden podzbiór, zatem jeśli |X| = 0, to |P(X)|= 1=2⁰. Wynika stąd, że liczba 0 ma własność W.

Założenie indukcyjne. Załóżmy, że wszystkie zbiory k elementowe mają własność W(k), tzn. liczba wszystkich podzbiorów zbioru k-elementowego wynosi 2^k.

Teza indukcyjna. Będziemy dowodzili, że zbiór (k+1)-elementowy ma też własność W.

Dowód tezy. Rozważmy zbiór (k+1)-elementowy X, X = {x₁,x₂,..., x_k,x_k+1}. Podzielmy wszystkie podzbiory zbioru X na dwie kategorie:

- Podzbiory zbioru X, w których nie występuje element x _k+1,

- Podzbiory zbioru X, w których występuje element x _k+1.

Podzbiory pierwszej kategorii są to wszystkie podzbiory zbioru k-elementowego, więc na mocy założenia indukcyjnego jest ich 2^k. Podzbiory drugiej kategorii otrzymujemy biorąc jakikolwiek podzbiór A zbioru k-elementowego X\{x _k+1}, a następnie dołączając element x_k+1. Takich podzbiorów, znów na mocy założenia indukcyjnego jest 2^k. Razem 2^k + 2^k = 2^k+1

podzbiorów. Czyli własność W jest prawdziwa dla k+1.

Na mocy zasady indukcji możemy teraz wyciągnąć wniosek, że zdanie W(n) jest prawdziwe dla wszystkich liczb naturalnych. ♦

Czasami wygodniej jest stosować nieco inną wersję zasady indukcji, w której założenie indukcyjne jest mocniejszym zdaniem niż w aksjomacie Peano Ax5. Pokażemy, że ta nowa forma zasady indukcji jest konsekwencją aksjomatów Peano.

Dowód.

Gdyby oba założenia były spełnione oraz A ≠ N, wtedy zbiór N\A nie byłby pusty. Weźmy więc jego element najmniejszy n₀. Taki element istnieje na mocy zasady minimum. Mamy n₀ ≠ 0, bo 0 ∈ A.

Wszystkie liczby mniejsze niż n₀ też nie należą do N\A, bo założyliśmy, że n₀ jest najmniejszym elementem należącym do N\A. Zatem wszystkie liczby mniejsze od n₀ należą do A. Stąd, na mocy drugiego założenia, n₀ ∈ A. Sprzeczność. ♦

Zadanie 9.3.1 Udowodnić, wykorzystując jedną z postaci zasady indukcji matematycznej, że dla dowolnego a >-1 i dla dowolnej liczby naturalnej n, (1+a)ⁿ ≥ 1 + n a.

Rozwiązanie:

Niech W(n) oznacza zdanie (1+a)ⁿ ≥ 1+ na.

Baza indukcji: Ponieważ (1+a)⁰ ≥ 1, zatem zachodzi W(0).

Założenie indukcyjne: Załóżmy, że W(k) jest zdaniem prawdziwym, tzn. mamy (1+a)^k ≥ 1+ ka.

Teza: W(k+1) jest zdaniem prawdziwym, tzn. (1+a)^k+1 ≥ 1+ (k+1)a.

Dowód tezy: (1+a)^k+1 = (1+a)^k (1+a). Wykorzystamy teraz założenie indukcyjne i otrzymamy (1+a)^k+1 ≥ (1+ ka)(1+a) ≥ 1 + ka + a + kaa ≥ 1+ (k+1)a + ka².

Ponieważ ka² ≥0, zatem ostatecznie (1+a)^k+1 ≥ 1+ (k+1)a. Czyli prawdziwe jest zdanie W(k+1). Ponieważ oba założenia zasady indukcji matematycznej są spełnione, zatem wnioskujemy, że W(n) jest prawdziwe dla wszystkich liczb naturalnych n.

Pytanie 9.3.1: Czy założenie a>-1 jest istotne w powyższym zadaniu? Gdzie z niego skorzystaliśmy?

Czasami zdarza się, że zdanie określające jakieś własności liczb naturalnych jest prawdziwe nie dla wszystkich, ale dla prawie wszystkich liczb naturalnych, tzn. dla wszystkich poczynając od pewnej ustalonej liczby. Zdarza się też, że chcemy udowodnić twierdzenie dotyczące nie liczb naturalnych, a liczb całkowitych większych od pewnej ustalonej liczby m. Wtedy możemy się posłużyć nieco inną formą zasady indukcji matematycznej, sformułowaną w twierdzeniu 9.3.2.

Dowód.

Oznaczmy przez W(n) zdanie α(m+n). Warunek pierwszy twierdzenia 9.3.2 dowodzi, że W(0) jest zdaniem prawdziwym. Załóżmy, że prawdziwe są własności W(0), ..., W(k-1). Oznacza to, wobec przyjętej definicji własności W, że zdania α(m), α(m+1),..., α(m+k-1) są wszystkie prawdziwe. Na mocy drugiego warunku, zdanie α(m+k) jest więc prawdziwe. W konsekwencji, zdanie W(k) jest prawdziwe.

Wykazaliśmy więc, że zachodzi warunek: jeśli własności W(0), ..., W(k-1) są prawdziwe dla pewnego k, to prawdziwa jest też własność W(k). Możemy zatem zastosować twierdzenie 9.3.1 i wyciągnąć wniosek, że wszystkie zdania W(n) są prawdziwe, a więc tym samym zdania α(n) są prawdziwe dla dowolnego n ≥ m. ♦

Opisaną wyżej technikę dowodu indukcyjnego zastosujemy w dowodzie lematu 9.3.2.

Dowód.

Część 1 dowodu. Na początek udowodnimy, że |X₁ × X₂| = |X₁| ⋅ |X₂| dla dowolnych zbiorów skończonych X₁, X₂. Przeprowadzimy dowód indukcyjny ze względu na liczbę elementów w zbiorze X₂. Jeżeli zbiór X₂ jest pusty, to nie możemy utworzyć żadnej pary uporządkowanej, której drugi element należy do X₂. Zatem |X₁ × X₂| = 0 = |X₁| ⋅ |X₂|.

Załóżmy (założenie indukcyjne), że twierdzenie |X₁ × X₂| = |X₁| ⋅ |X₂| jest prawdziwe, gdy zbiór X₂ ma k elementów. Rozważmy zbiór (k+1)-elementowy X = {a₁, a₂, ..., a_k+1}. Wszystkie pary w produkcie X₁ × X możemy podzielić na 2 grupy:

1. pary postaci (x, a_k+1) dla x ∈ X₁.
2. pary, w których drugi element jest różny od a _k+1,

Par pierwszego typu jest dokładnie tyle, ile elementów ma zbiór X₁, a więc |X₁|. Par drugiego rodzaju jest tyle, ile elementów ma produkt X₁ × {a₁, a₂, ..., a_k}. Na mocy założenia indukcyjnego |X₁ × {a₁, a₂, ..., a_k}| = |X₁| ⋅k, zatem |X₁ × X| = |X₁| ⋅k + |X₁| = |X₁| ⋅(k+1).

Udowodniliśmy więc krok indukcyjny: jeżeli równość |X₁ × X₂| = |X₁| ⋅ |X₂| zachodzi dla k-elementowego zbioru X₂, to również zachodzi dla (k+1)-elementowego zbioru X₂. Na mocy zasady indukcji wzór |X₁ × X₂| = |X₁| ⋅ |X₂| jest prawdziwy dla zbiorów skończonych o dowolnej liczbie elementów.

Część 2 dowodu. Oznaczmy przez α(n) równość (*). W części pierwszej dowodu wykazaliśmy, że α(2) jest zdaniem prawdziwym dla dowolnych zbiorów X₁, X₂ (baza indukcji).

Załóżmy teraz, że α(k) jest zdaniem prawdziwym dla pewnego k ∈ N (założenie indukcyjne), udowodnimy, że α(k+1) jest też zdaniem prawdziwym.

Niech X₁, X₂, ..., X_k+1, będą dowolnie ustalonymi zbiorami skończonymi. Zauważmy, że każdemu elementowi (x₁, x₂, ..., x_k, x_k+1) produktu kartezjańskiego zbiorów X₁ × ... × X_k × X_k+1 można jednoznacznie przyporządkować parę uporządkowaną (a, x_k+1), gdzie a = (x₁, x₂, ..., x_k). Wynika stąd, że różnych elementów postaci (x₁, x₂, ..., x_k, x_k+1) jest tyle ile jest różnych par uporządkowanych postaci ((x₁, x₂, ..., x_k), x_k+1). Mamy więc

| X₁ × X₂ × ... × X_k × X_k+1| = | X₁ × X₂ × ... × X_k| ⋅ |X_k+1|.

Na mocy założenia indukcyjnego | X₁ × X₂ × ... × X_k| = | X₁ | ⋅ | X₂ | ⋅ ... ⋅ |X_k|, a stąd i z poprzedniej równości wynika prawdziwość zadania α(k+1).

Oba założenia zasady indukcji matematycznej są spełnione, zatem zdanie α(n) jest prawdziwe dla wszystkich liczb naturalnych n>1.

Uwaga: Czytelnik zechce wyszukać inny, niż przytoczony w części pierwszej, dowód, że liczba elementów produktu kartezjańskiego dwóch zbiorów skończonych, jest równa iloczynowi liczb elementów tych zbiorów. ♦

Na zakończenie tej części wykładu rozważymy przypadek, gdy własność, której chcemy dowieść, dotyczy tylko pewnego skończonego podzbioru zbioru liczb naturalnych. Mówimy wtedy o zasadzie skończonej indukcji.

Zadanie 9.3.2  Udowodnij, że n! > 2ⁿ dla wszystkich n naturalnych ≥ 4. Którą z wersji zasady indukcji trzeba zastosować?

Podpowiedź: Trzeba zastosować zasadę sformułowaną w twierdzeniu 9.3.2. Rzeczywiście, 4! = 24 >2⁴ =16. Ponadto, jeśli k!> 2^k , to (k+1)!= k! (k+1)>(k+1) 2^k . Ponieważ k+1 jest na mocy założenia większe od 3, zatem (k+1) 2^k >2_*2^k. Ostatecznie, (k+1)! > 2^k+1.