984501247

2. LICZBY NATURALNE. INDUKCJA MATEMATYCZNA

Powyższa zasada, choć nie można jej udowodnić, wydaje się intuicyjnie jasna, a jej prawdziwość nie budzi wątpliwości. Jednak wynikające z niej wnioski, a w szczególności Zasada Indukcji Matematycznej, już nie zawsze są tak łatwe do zaakceptowania.

Twierdzenie 2.1 (Zasada Indukcji Matematycznej). Jeśli A jest takim podzbiorem zbioru liczb naturalnych, że:

(I) 1 e A,

(II) jeśli n G A, to także n + 1 G A, to wówczas każda liczba naturalna należy do A, tzn. A = N.

Twierdzenie to można łatwo uzasadnić przy pomocy Zasady Minimum. Istotnie, gdyby zbiór A zawarty w zbiorze N liczb naturalnych spełniał warunki (I) oraz (II), a był od niego różny, to na mocy Zasady Minimum musiałaby istnieć najmniejsza taka liczba, powiedzmy no, która do niego nie należy. Oczywiście no > 1, bo 1 E A. Skoro jednak no jest liczbą najmniejszą wśród tych, które nie należą do A, to no — 1 G A. To jednak przeczy określeniu liczby no, bo na mocy warunku (II), no = (no — 1) + 1 G A.

Często wygodniej jest posługiwać się Zasadą Indukcji Matematycznej w wersji uogólnionej:

Twierdzenie 2.2 (Zasada Indukcji Matematycznej *). Niech W będzie własnością przysługującą liczbom naturalnym, a W(n) niech oznacza, że liczba n ma własność W. Wówczas, jeśli spełnione są dwa warunki:

(I*) zachodzi W(l),

(II*) jeśli zachodzi W(n), to zachodzi również W(n + 1), to własność W zachodzi dla wszystkich liczb naturalnych.

Zasada Indukcji Matematycznej jest jednym z najważniejszych narzędzi, przy pomocy których dowodzi się twierdzeń. Zilustrujemy to na kilku przykładach.

Przykład 2.1. Dla każdej liczby naturalnej n suma wszystkich kolejnych liczb naturalnych od 1 aż do n włącznie jest równa |n(n + 1), tzn.

n(n + 1) 2

(i)

1 + 2 + 3 H----+ n —

przy czym po lewej stronie równości występuje suma n składników, tzn. dokładnie tyle ile wynosi liczba n.

Aby udowodnić powyższy wzór rozważmy własność W(n) mówiącą, że zachodzi równość (1). Wówczas oczywiście zachodzi W(l), bo po lewej stronie równości mamy 1, a po prawej ułamek ¹    . Zatem spełniony jest warunek (I*) Zasady Indukcji

Matematycznej. Aby sprawdzić warunek (II*) wystarczy do obydwu stron równości (1) dodać liczbę n + 1. Wówczas otrzymujemy

1 + 2 + 3 +----\-n + {n + 1) —

n(n + 1)

2

+ (n+ 1) =

n(n + 1) + 2(n + 1) _ (n + l)(n + 2)

2

2