Matemaatiline induktsioon on matemaatilise tõestuse meetod, mis põhineb tingimuslike väidete vahelisel seosel. Näiteks alustame tingimusliku väitega: “Kui on pühapäev, siis ma vaatan jalgpalli.” Võite teha järgmise avalduse: “Kui ma jalgpalli vaatan, siis tellin kaasa.” Sellele väitele võiks järgneda veel üks: “Kui ma tellin kaasa, siis ma süüa ei tee.” Nende põhjal võiksite nende tingimuslike väidete loogilise seose tõttu järeldada, et: “Kui on pühapäev, siis ma süüa ei tee.” Kui suudate tõestada, et implikatsioonide ahela esimene väide on tõene ja iga väide eeldab järgmist, järeldub sellest loomulikult, et ka ahela viimane väide on tõene. Nii toimib matemaatiline induktsioon ja alltoodud sammud illustreerivad formaalse induktsioonitõendi koostamist.
1
Hinnake probleemi. Oletame, et teil palutakse arvutada esimese “n” paaritu arvu summa, mis on kirjutatud kui [1 + 3 + 5 + . . . + (2n – 1)], induktsiooni teel. (Viimane termin tuleneb sellest, et kui kahekordistate mis tahes arvu ja lahutate sellest väärtusest 1, on tulemuseks olev arv alati paaritu.) Alguses võite märgata, et järjestikuste paaritute arvude summa näib järgivat mustrit. (nt 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16; 1 + 3 + 5 + 7 + 9 = 25). Summa näib olevat paaritute arvude arv, mille lisate ruudus, eks? Nüüd, kui meil on siin mängitavast mustrist aimu, võime alustada oma tõestust.
2
Märkige omadus, mida induktsiooni abil tõestatakse. Meie näites oleme märganud mustrit, mis on seotud esimese “n” paaritu arvu summaga. Meile määratud ülesande täitmiseks (st esimese “n” paaritu arvu summa arvutamiseks) võiksime tegelikult võtta aega, et kirjutada välja kõik paaritud arvud, alustades 1-st kuni “n”-ni, ja lisada need üles. Kuid on lihtsam viis. Selle põhjal, mida me esimeste summeerimiste kohta täheldasime, võiksime pakkuda seda omadust, mida proovime tõestada induktsiooni abil: 1 + 3 + . . . + (2n – 1) = n^2 Nimetame seda omadust kui P(n), sest “n” on ülalpool kasutatud muutuja. Võrrandi vasakpoolne märk tähistab esimese paaritu “n” summat. numbrid, mis algavad 1-st.
3
Mõistke matemaatilise induktsiooni kontseptsiooni. Kasulik on mõelda induktsioonile doominovormina, mis tuletab meelde ülaltoodud sissejuhatuses käsitletud “mõjude ahelat”. Mõelge igale “n” väärtusele ülaltoodud atribuudis P(n) kui individuaalsele doominole, mis on paigutatud reale. Kui suudame näidata, et P(1) ahela esimene väärtus on tõene, tähendab see, et saame esimese doomino üle lüüa. Lisaks, kui eeldame, et suvalise doomino saab ümber lükata (st P(n) kehtib mingi suvalise “n” väärtuse korral) ja selle eeldusega, et ka järgmise doomino saab ümber lükata (st P (st P) (n + 1) on samuti tõsi), see tähendab, et saame kõik doominoklotsid oma märgitud omadusega ümber lükata. See tähendab, et omadus on kõigil juhtudel tõene ja oleme saavutanud oma eesmärgi induktsiooniga.
4
Tõestage, et atribuudi põhijuhtum on tõene. Konkreetse atribuudi “alusjuhtum” on väike väärtus, mida kasutatakse näitamaks, et omaduse esimene väide kehtib. Sel juhul kasutame numbrit 1, kuna see on esimene paaritu arv ja sellega on lihtne töötada. Kui omadus kehtib põhijuhtumi puhul, oleme näidanud, et suudame esimese doomino üle lüüa ja saame liikuda järgmise sammu juurde.P(1): 1 = 1^2P(1): 1 = 1 (See käes, oleme tublid. Esimene doomino maha.)
5
Esitage induktiivne hüpotees. Induktsiooni järgmine samm hõlmab oletuse tegemist. Meie näites eeldame, et mingi suvalise “n” väärtuse puhul oletame “k”, et väide on tõene. See tähendab, et me usume, et meie vara säilib sõltumata väärtusest, mida kasutatakse “n” jaoks. Kui see poleks tõsi, poleks meie omadusest (st meie lahendusest esimese “n” paaritu arvu summa arvutamise algsele probleemile) palju kasu. Kuigi me pole veel midagi tõestanud, on see eeldus oluline ja on järgmisel kujul: P(k): 1 + 3 + . . . + (2k – 1) = k^2Pidage meeles, et me eeldame, et see on tõestuses edasi liikudes tõene (st et me võime ahelas iga üksiku doominoklotsiga ümber lükata).
6
Tõestage, et induktiivne hüpotees kehtib ahela järgmise väärtuse kohta. Teisisõnu eeldame, et P(k) kehtib, ja proovime seda eeldust kasutades tõestada, et ka P(k + 1) kehtib. Kui suudame seda teha, oleme tõestanud, et meie teooria kehtib induktsiooni abil, sest kui ühe doomino mahalöömine (eeldusel, et P(k) on tõene), kukutakse maha järgmine doomino (selle eelduse abil on ka P(k + 1) tõestamine. tõsi), kõik doominoklotsid kukuvad ja meie vara kehtivaks tunnistatakse. Proovime siis seda: P(k): 1 + 3 + . . . + (2k – 1) = k^2 on tõene.P(k + 1): 1 + 3 + . . . + (2k – 1) + (2(k + 1) – 1) = (k + 1)^2 Ülalpool olev kaldkirjas olev osa võrrandi vasakus servas tähistab jada järgmise paaritu numbriga termini liitmist , k + 1. Kui suudame selle vasaku külje võrdseks parema poolega, on see meil õnnestunud. Meie oletuse põhjal teame, et ülaltoodud kaldkirjata osa võrdub k^2, nii et teeme selle asendus. P(k + 1): k^2 + (2(k + 1) – 1) = (k + 1)^2P(k + 1): k^2 + 2k + 1 = (k + 1)^2P (k + 1): (k + 1)^2 = (k + 1)^2
7
Järeldage, et omadus on õigesti tõestatud matemaatilise induktsiooniga. Väikese algebra abil oleme tõestanud, et meie omadus kehtib mitte ainult mingi suvalise “n” väärtuse, vaid ka sellele väärtusele järgneva väärtuse kohta. Oleme näidanud, et P(1) on tõene, eeldanud, et P(k) on tõene, ja tõestanud, et selle eelduse põhjal on tõene ka P(k + 1). Kasutades meie jätkuvat doomino analoogiat, lõime edukalt maha esimese doomino, näidates, et meie varal on väärtust. Seejärel, eeldades, et ahela suvaline doomino saab ümber lükata, tõestasime, et see kukutab tingimata maha järgmise doomino, ad infinitum kogu ülejäänud ahela. Seega oleme näidanud, et meie omadus üldiselt kehtib, ja oleme edukalt lõpetanud oma tõestuse matemaatilise induktsiooniga.
8
Mõistke kahe induktsioonivormi erinevust. Ülaltoodud näide on nn “nõrk” induktsioon, mida ei nimetata nii kahe induktsioonimeetodi kvaliteedierinevuse tõttu, vaid pigem selleks, et illustreerida erinevust selle vahel, mis on eeldatud igat tüüpi tõendite induktiivses hüpoteesis. Need kaks tõestustehnikat on tegelikult samaväärsed, lihtsalt mõnikord on vaja induktiivses hüpoteesis eeldada rohkem, et tõestada käsilolevat väidet. Kui naasta meie doomino analoogia juurde, siis mõnikord ei piisa P(k) tõeks olemise kaalust, et P(k + 1) kujutatud doomino maha lüüa. Mõnikord peate suutma enne seda kõik doominoklotsid maha lüüa, et tõestada, et teie ettepanek kehtib.
9
Esitage tõestatav väide tugeva induktsiooni abil. Selle illustreerimiseks vaatleme teistsugust näidet. Oletame, et teil palutakse tõestada väide, et kõik täisarvud, mis on suuremad kui 1, saab kirjutada algarvude korrutisena. Nagu varemgi, viitame sellele väitele kui P(n), kus “n” on arv, mida saab väljendada algarvude korrutisena. Kuna me räägime kõigist täisarvudest, mis on suuremad kui 1, siis “n” peab olema suurem kui 2 või võrdne sellega. Pidage meeles, et algarv on 1-st suurem positiivne täisarv, mida saab ilma jäägita jagada ainult iseenda ja 1-ga.
10
Tõestage, et põhijuhtum on tõene. Nagu varemgi, on iga induktsioonitõenduse esimene samm tõestada, et põhijuhtum kehtib. Sel juhul kasutame arvu 2. Kuna 2 on algarv (jagub ainult iseenda ja 1-ga), võime järeldada, et põhijuht on tõene.
11
Esitage (tugev) induktiivne hüpotees. Siin ilmneb kõige selgemalt erinevus “nõrga” ja “tugeva” induktsiooni vahel, kuna see samm on ainus erinevus kahe induktiivse tõestuse vormi vahel. Induktiivne hüpotees “nõrga” induktsiooni kohta eeldaks, et mingi suvalise “n” väärtuse korral kasutame jälle lauses kehtivat “k”. Seejärel kasutaksime seda eeldust, et tõestada, et ahela järgmine väärtus on tõene, võimaldades meil järeldada, et meie ettepanek on üldiselt kehtiv. Kuid selle väite puhul ei ütle P(k) tõene olemine meile midagi P(k + 1 kohta). Seda tüüpi “nõrk” eeldus on siin ebapiisav, seega peame eeldama rohkem. Induktiivne hüpotees “tugeva” induktsiooni kohta, selle asemel, et eeldada, et P(k) on tõene, eeldab, et väide on tõene kõigi “n” väärtuste puhul põhijuhtumi ja “k” vahel. Me kasutame seda suhteliselt tugevamat eeldust (st eeldame rohkem), et tõestada, et väide on tõene. Seda tüüpi “tugev” oletus on see, mis eristab kaht tõestusvormi. Sel juhul eeldame, et teatud väärtuse korral k ≥ 2, et iga täisarv “n”, nii et 2 ≤ n ≤ k võib kirjutada algarvude korrutisena.
12
Tõestage, et “tugev” induktiivne hüpotees kehtib ahela järgmise väärtuse kohta. Nüüd kasutame seda tugevat eeldust tõestamaks, et ka P(k + 1) kehtib, tõestades sellega meie väite paikapidavust üldiselt. “K + 1” jaoks on kaks asjakohast tulemust. Kui “k + 1” on algarv, kehtib meie väide ja oleme valmis. Kui “k + 1” ei ole algarv, on sellel väikseim algtegur, mida tähistame kui “p”. Seetõttu saab “k + 1” väljendada “p” ja mõne muu arvu “x” korrutisena. Kuna “x” on tingimata väiksem kui “k”, ütleb meie induktiivne hüpotees meile, et “x” saab kirjutada algarvude korrutisena, mis lõppkokkuvõttes tähendab, et olenemata sellest, kas “k + 1” on algarvud või mitte, saab seda kirjutada algarvude korrutis.
13
Järeldage, et väide on usaldusväärselt tõestatud tugeva matemaatilise induktsiooniga. Kasutades meie “tugevat” induktiivset hüpoteesi, suutsime tõestada oma väidet, kui “nõrk” induktsioon poleks olnud selleks piisav. Proovige esmalt “nõrga” induktsiooni, sest asjaolu, et te eeldate teoreetiliselt vähem, muudab tõestuse taga oleva loogika tugevamaks, vastupidiselt nende kahe tõestuse puhul kasutatavatele nimetamiskokkulepetele. Matemaatiliselt on need kaks induktsiooni vormi aga samaväärsed.