Zasada indukcji matematycznej, studia, matematyka dyskretna
[ Pobierz całość w formacie PDF ]
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
k n
³
0
, wynika, Ŝe
W
(
k
+1) teŜ jest prawdziwa
to
W
(
n
) jest prawdziwa dla kaŜdej liczby naturalnej
n n
³
0
.
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
1 2 ...
+ + + =
2
n
2
n
3
+
n
2
+ =
n n n
(
+
1 2 1
)(
n
+
)
3
2 6
6
Rozwiązanie
Sprawdzamy wzór dla
n
=1
L 1 P=
=
2
1 1 1
3 2 6
+ + =
1 L=P
⇒
Zało
Ŝ
enie indukcyjne
:
1 2 ...
2
+ + + =
2
k
2
k
3
+
k
2
+
k
3
2 6
Teza indukcyjna
:
1 2 ...
2
+ + + + +
2
k
2
(
k
1
)
2
=
(
k
+
1
)
3
+
(
k
+
1
)
2
+
(
k
+
1
3
2
6
Dowód indukcyjny
:
L 1 2 ...
= + + + + +
2
2
k
2
(
k
1
)
2
=
k
3
+
k
2
+ + +
k
(
k
1
)
2
=
2
k
3
+
3
k k
2
+ +
6
(
k
+
1
2
=
2
k
3
+
9
k
2
+
13 6
k
+
3
2 6
6
6
(
k
+
1
)
3
(
k
+
1
)
2
(
k
+
1 2
)
(
k
+ +
1
)
3
3
(
k
+ + +
1
)
2
k
1 2
k
3
+
6
k
2
+ + +
6 2 3
k
k
2
+ + + +
6 3
k
k
1 2
k
3
+
9
k
2
+
13 6
+
P=
+
+
=
=
=
3
2
6
6
6
6
a stąd otrzymujemy, Ŝe L=P. Co kończy dowód indukcyjny.
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
2
)
)
k
i
[ Pobierz całość w formacie PDF ]