Indukcja matematyczna
Dowody indukcyjne przeprowadza się według jednego schematu - prawidłowo
skonstruowany dowód uwzględnia WSZYSTKIE kroki tego schematu. Oto ko-
lejne punkty:
1. Sprawdzamy, czy twierdzenie zachodzi dla dowolnej ustalonej liczby natu-
ralnej. W tym celu wybieramy dowolną liczbę spełniającą założenia twier-
dzenia (to znaczy, jeśli w twierdzeniu mamy, że zachodzi ono dla wszyst-
kich liczb naturalnych większych lub równych 5 to nie możemy wybrać 3
tylko co najmniej 5). Na ogół wybieramy 1 lub 2.
2. Drugi punkt to tak zwane założenie indukcyjne. Piszemy: n = k i przepi-
sujemy treść twierdzenia, zastępując znaczki n znaczkami k.
3. Trzeci punkt to teza indukcyjna. Piszemy: n = k + 1 i przepisujemy treść
twierdzenia zastępując znaczki n znaczkami (k + 1)  uwaga! wpisać w
nawiasie!!!
4. Czwarty punkt to właściwy dowód. Cała trudność polega na tym, żeby
tak przekształcić tezę indukcyjną, żeby  wyłączyć z niej założenie induk-
cyjne i pewną  resztę . Dla założenia indukcyjnego twierdzenie zachodzi.
Pozostaje udowodnić, że zachodzi dla wyłączonej  reszty . Na ogół jest to
łatwo zauważyć.
Przykład 1. (Typ 1: udowodnić podzielność liczby) Wykazać, że 3|4n +2
(czytamy: trzy jest dzielnikiem cztery do n-tej plus 2).
1. Sprawdzamy dla n = 2 (można wybrać dowolną rozsądną liczbę natural-
nÄ…). Obliczamy 4n + 2 = 42 + 2 = 18, a jak wiadomo, 18 jest podzielne
przez 3. Jak na razie, twierdzenie zachodzi. Nie wiadomo, czy zachodzi dla
WSZYSTKICH liczb naturalnych.
2. Piszemy:  Założenie indukcyjne: n = k i przepisujemy treść twierdzenia,
zmieniajÄ…c n na k: 3|4k + 2.
3. Piszemy:  Teza indukcyjna: n = (k + 1) i przepisujemy treść twierdzenia,
zmieniajÄ…c n na (k + 1): 3|4(k+1) + 2.
4. Piszemy:  Dowód: i przekształcamy wzór 4k+1 + 2 w taki sposób, żeby
wyłączyć z niego 4k + 2. Zauważmy, że 4(k+1) + 2 można zapisać jako
4 · 4k + 2, a to z kolei jako 3 · 4k + 4k + 2. Druga część wzoru (po znaku +)
to założenie indukcyjne, a zatem jest podzielne przez 3. Pierwsza część,
to 3 · 4k. Ale iloczyn liczby 3 i jakiejkolwiek innej liczby jest podzielny
przez 3. Suma liczb podzielnych przez 3 też jest podzielna przez 3. Dowód
zakończony (zwykle zapisujemy z prawej strony symbol ).
1
Przykład 2. (Typ 2: Wzory na sumy n wyrazów ciągu)
Udowodnić, że 1 + 3 + · · · + (2n - 1) = n2.
UWAGA! W tym typie dowodów n oraz k oznaczają numer, ale też ILOŚĆ
kolejnych wyrazów ciągu.
1. Sprawdzamy np. dla n = 4. W twierdzeniach, że jakiś wzór jest równy
innemu, możemy mówić o LEWEJ i PRAWEJ stronie równania. Stąd
piszemy:
L = 1 + 3 + 5 + 7 = 16, (bierzemy 4 pierwsze wyrazy ciÄ…gu po lewej
stronie).
P = 42 = 16
L = P  dla wybranej liczby wzór zachodzi.
2. Założenie ind.: n = k
Przepisujemy twierdzenie, zastępując literkę n literką k:
1 + 3 + 5 + · · · + (2k - 1) = k2
3. Teza ind.: n = (k+1). Przepisujemy twierdzenie w ten sposób, że lewą stro-
nę przepisujemy z założenia indukcyjnego i DOPISUJEMY k + pierwszy
wyraz, zastępując literkę n we wzorze symbolem (k + 1)
1 + 3 + 5 + · · · + (2k - 1) + (2(k + 1) - 1) = (k + 1)2.

przepisane dopisane
4. Dowód:
Obliczamy lewÄ… stronÄ™:
L = 1 + 3 + 5 + · · · + (2k - 1) +(2(k + 1) - 1)

lewa strona założenia
= k2 +(2(k + 1) - 1)

prawa strona założenia
= k2 + 2k + 1
P = (k + 1)2 = k2 + 2k + 1
L = P

©Piotr Sojka ([e-mail]), Ostatnia aktualizacja: 8 listopada 2006
2