5600235771

4 Indukcja matematyczna 9

wszystkich liczb dla, których wzór (1) nie zachodzi. Jest to podzbiór N, a więc korzystając z zasady minimum musi w nim być element najmniejszy, nazwijmy go k. Nie może on być równy 0, 1,2, 3, 4, bo dla tych wartości sprawdziliśmy, że wzór (1) jest prawdziwy. Tak, czy inaczej dla A; — 1 wzór (1) jest prawdziwy, bo k — 1 ^ S jako, że k jest w S elementem najmniejszym. Zatem

1 + 3 + 5 + ■ • • + (2(fc - 1) - 1) = 1 + 3 + 5 + ■ • • + (2k - 3) = (k - l)².

Dodajmy do obu stron kolejną liczbę nieparzystą, czyli 2k — 1. Dostaniemy

1 + 3 + 5 H-----1- (2k — 3) + (2k — 1) = (k - l)² + (2k - 1) = fc²-2A;+l + 2A;-l = k²,

ale to oznacza, że dla k nasz wzór (1) jest prawdziwy. Nasze przypuszczenie było więc fałszywe i wzór (1) jest prawdziwy dla wszystkich liczb naturalnych różnych od 0.

4.2 Zasada indukcji

Twierdzenie 4.3. Niech S C N, n € N spełniają dwa warunki:

(i)    n G S oraz

(ii)    jeśli k € S, to również k + 1 € S.

Wówszas {n,n + l,n + 2,...}C5.

Przykład 4.4. Wykażemy, że wzór

2n + 1 < 2ⁿ.    (2)

jest prawdziwy dla n > 3. Niech

S = {keN: 2i + l<2‘}

będzie zbiorem wszystkich takich liczb naturalnych, dla których zachodzi wzór (2). Zauważmy, że n = 3 € S bo

2-3+l = 7<8=2³.

Załóżmy teraz, że k € S. Sprawdzimy, czy k + 1 € S. Mamy 2(k + 1) + 1 = 2k + 1 + 2 < 2^k + 2 < 2^fe + 2^fe = 2 ■ 2^k = 2^k+1. Zatem k + 1 € S. Na mocy zasady indukcji S = {3,4,5,...}, co kończy dowód. Przykład 4.5. Zbadamy dla jakich n e N zachodzi wzór

n² < 2”.    (3)

Dla małych n mamy