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|4

n

+ 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 4

n

+ 2 = 4

2

+ 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|4

k

+ 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 4

k+1

+ 2 w taki sposób, żeby

wyłączyć z niego 4

k

+ 2. Zauważmy, że 4

(k+1)

+ 2 można zapisać jako

4 · 4

k

+ 2, a to z kolei jako 3 · 4

k

+ 4

k

+ 2. Druga część wzoru (po znaku +)

to założenie indukcyjne, a zatem jest podzielne przez 3. Pierwsza część,
to 3 · 4

k

. 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) = n

2

.

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 = 4

2

= 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) = k

2

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)
|

{z

}

przepisane

+ (2(k + 1) − 1)

|

{z

}

dopisane

= (k + 1)

2

.

4. Dowód:

Obliczamy lewą stronę:

L

=

1 + 3 + 5 + · · · + (2k − 1)
|

{z

}

lewa strona założenia

+(2(k + 1) − 1)

=

k

2

|{z}

prawa strona założenia

+(2(k + 1) − 1)

=

k

2

+ 2k + 1

P

=

(k + 1)

2

= k

2

+ 2k + 1

L

=

P



c

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

2