Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Twierdzenie1.1(zasadaindukcji)
Jeśli
Tn
()
,
nENjestfunkcjązdaniowątaką,że:
Z1:
T
()
1
jestprawdziwei
Z2:
vE
n
N
,
Tn
()
3
Tn
(
+
1
)
jestprawdziwe,
tozdanie
vEN
n
,
Tn
()
jestprawdziwe.
Komentarz.Dowódprzeprowadzonymetodąindukcjinazywamydowodem
indukcyjnym.Zgodniezregułąodrywania(1.19),polegaonnawykazaniupraw-
dziwościdwóchzałożeńzasady:Z1(tzw.krokupoczątkowegolubinicjacji)-
sprawdzenia,czytwierdzeniejestprawdziwedla
n±
1
iZ2(tzw.krokuinduk-
cyjnego)-dowodutzw.przesłankiindukcyjnej:
vE
n
N
,
Tn
()
3
Tn
(
+
1
)
,
czylidladowolnej,ustalonejliczbynaturalnejnzprawdziwościtwierdzeniadla
nwynikaprawdziwośćtwierdzeniadla
n+.
1
Prawdziwesąogólniejszesformułowaniatwierdzenia1.1wprzypadkufunk-
cjizdaniowej
Tk,którejzakresemzmiennościjestzbiórliczbcałkowitychnie
()
mniejszychniżpewnaliczba(początkowa)
k:
0
f
L
Z1:
Tk
()
0
^
Z2:
vE
k
Z
k
2
kTk
0
,
()
3
Tk
(
+
1
)
1
J
3vE
k
Z
k
2
kTk
0
,
()
;
,
,
(1.22)
f
|
|
L
Z1:
Z2:
vE
Tk
k
()
0
Z
^
k
Tk
2
(
k
0
0
+
,
(
1
Tk
)
(
-
1
)
^
Tk
()
)
3
Tk
(
+
1
)
1
|
|
J
3vE
k
Z
k
2
kTk
0
,
()
.
,
,
(1.23)
Napodstawietejzasadymożnapodaćtzw.definicjęindukcyjną(rekuren-
cyjną)funkcjizdaniowej
Tk
()
,
k
E
Z
^
k
2
k
0
wnastępującysposób:
Z1:określeniezdania
Tk
()
0
,
Z2:określenie,wjakisposóbzezdania
Tkotrzymujesięzdanie
()
Tk+
(
1
)
dladowolnego
k
2
k
0
(podanieprzepisurekurencyjnegonaprzejścieod
Tkdo
()
Tk+
(
1
)
).
Uwaga.Możliwesąinnesposobydefiniowaniaindukcyjnego,np.równoważ-
nezZ2określenie,wjakisposóbzezdania
Tk-
(
1
)
otrzymujesięzdanie
Tk
()
dladowolnego
k
>
k
0
.WprzypadkupodaniawZ2związku(rekurencji)między
Tka
()
Tk-
(
1
)
i
Tk-
(
2
)
należyzmodyfikowaćZ1przezokreśleniedwóch
początkowychzdań
Tk
()
0
i
Tk+
(
0
1
)
.
35
