Zasada indukcji matematycznej (zupełnej)

Ważną własność zbioru liczb naturalnych wyraża następująca zasada indukcji matematycznej
(zupełnej):

Niech W(n) oznacza pewną formę zdaniową (np. własność/wzór), w której występuje zmienna

.

n

∈

ℕ

Jeżeli

1.

jest ono prawdziwe dla pewnego naturalnego n

0

oraz

2.

z tego, że W(k) jest prawdziwa dla każdego

0

k

n

≥

, wynika, że W(k+1) też jest prawdziwa

to W(n) jest prawdziwa dla każdej liczby naturalnej

0

n

n

≥

.

W praktyce wykorzystujemy indukcję matematyczną jako metodę dowodzenia twierdzeń i wzorów
dotyczących liczb naturalnych. Są to tak zwane dowody indukcyjne. Postępujemy przy tym w
następujący sposób:

1.

sprawdzamy prawdziwość twierdzenia (wzoru) dla liczby n =1

i

.

2.

zakładamy prawdziwość twierdzenia (wzoru) dla k = n, gdzie k jest dowolnie ustaloną liczbą
naturalną (jest to tak zwane założenie indukcyjne)

3.

dowodzimy prawdziwości twierdzenia (wzoru) dla n = k+1 (teza indukcyjna).

Stąd, na mocy zasady indukcji, wnosimy, że twierdzenie jest prawdziwe dla każdej liczby naturalnej.


Przykład
Wykazać, że

(

)(

)

3

2

2

2

2

1 2

1

1

2

...

3

2

6

6

n

n

n

n n

n

n

+

+

+

+ +

=

+

+ =

Rozwiązanie

Sprawdzamy wzór dla n=1

2

1

1

1

L

1 P=

1

L=P

3

2

6

=

+ + =

⇒

Założenie indukcyjne:

3

2

2

2

2

1

2

...

3

2

6

k

k

k

k

+

+ +

=

+

+

Teza indukcyjna:

(

)

(

)

(

)

(

)

3

2

2

2

2

2

1

1

1

1

2

...

1

3

2

6

k

k

k

k

k

+

+

+

+

+ +

+ +

=

+

+

Dowód indukcyjny:

(

)

(

)

(

)

2

3

2

3

2

3

2

2

2

2

2

2

2

3

6

1

2

9

13

6

L

1

2

...

1

1

3

2

6

6

6

k

k

k

k

k

k

k

k

k

k

k

k

k

+

+ +

+

+

+

+

= +

+ +

+ +

=

+

+ + +

=

=

(

)

(

)

(

)

(

)

(

)

3

2

3

2

3

2

2

3

2

1

1

1

2

1

3

1

1

2

6

6

2 3

6

3

1

2

9

13

6

P=

3

2

6

6

6

6

k

k

k

k

k

k

k

k

k

k

k

k

k

k

k

+

+

+

+

+

+

+ +

+

+

+ +

+

+ + +

+

+

+

+

+

=

=

=

a stąd otrzymujemy, że

L=P.

Co kończy dowód indukcyjny.

i

Czasami w pierwszym kroku zamiast sprawdzenia dla n =1 bierze się jakąś większą wartość n

0

.

Wtedy w wyniku przeprowadzenia dowodu indukcyjnego otrzymujemy prawdziwość twierdzenia dla
wszystkich liczb naturalnych n

≥

n

0