Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Zasadaindukcjimatematycznej
Tooznacza,że
x1+x2+x3+x4+x5=41
ijednocześnie
x1+x2+x3+x4+x5<40,
cooczywiściejestfałszem.
13
1.2.Zasadaindukcjimatematycznej
Rozpocznijmyodprostegoprzykładu.Rozważmynastępującewyrażenie:
p(n):
1·2·...·n>2n,
któredlakażdegoustalonegonnaturalnego(n∈N)jestzdaniem.Łatwo
stwierdzić,iżzdaniap(1),p(2)ip(3)sąfałszywe,natomiastzdaniap(4),
p(5)ip(6)sąprawdziwe.Czyjestzatemprawdą,żedlakażdegonatural~
negon,n>4,rozpatrywanezdaniep(n)jestprawdziwe?wydajesię,że
tak,gdyżwartośćwyrażeniastojącegopolewejstronienierównościrośnie,
wrazzewzrostemn,owieleszybciejaniżeliwartość2n.Trzebatojednak
formalnieudowodnić.Okazujesię,żetegotypuproblemynajłatwiejwyka~
zywać,stosujączasadęindukcjimatematycznej,którąmożnasformułować
wnastępującysposób:
Niechdlakażdegonnaturalnegop(n)będziezdaniem?któremożebyć
prawdziwelubfałszywe.Abyudowodnić?żedlakażdegonaturalnegon?
n>no?zdaniep(n)jestprawdziwe?wystarczypokazać?że
(a)zdaniep(no)jestprawdziwe?
(b)dlakażdegok>no?
p(k)⇒p(k+1),
(1.1)
tzn.zdaniep(k+1)jestprawdziwe?jeżelitylkozdaniep(k)jest
prawdziwe.
Stwierdzenie(a)nazywasięwarunkiempoczątkowym.Założenie,żep(k)jest
prawdziwe,nazywasięzałożeniemindukcyjnym,ap(k+1)teząindukcyjną,
zaśsamaimplikacja(1.1)krokiemindukcyjnym.
Powracającdonaszegoprzykładu,wiemy,żep(4)jestprawdziwe(jest
tonaszwarunekpoczątkowy).Zatemno=4.Należyterazpokazać,żejeżeli
