Matemaattinen induktio

Matemaattinen induktio on matematiikassa usein käytetty todistusmenetelmä, yleisimmin silloin, kun työskentelemme positiivisten kokonaislukujen tai jonkin muun lukujonon kanssa.

Periaate

Perusperiaate on, että todistamme väitteen jollekin ensimmäiselle alkiolle, positiivisilla kokonaisluvuilla useimmiten arvolle n = 1. Sen todistamme yksinkertaisella sijoituksella. Seuraavassa, induktioaskeleessa, todistamme implikaation ”jos väite pätee arvolla n = a, niin se pätee myös arvolla n = a + 1”.

Näistä kahdesta askeleesta voimme päätellä, että annettu lauseke pätee kaikilla n:n arvoilla (jostakin joukosta, jonka kanssa kulloinkin työskentelemme). Miksi näin on? Alussa todistamme, että lauseke pätee arvolla n = 1. Samalla tiedämme, että jos lauseke pätee arvolla n = a, se pätee myös arvolla n = a + 1. Valitsemme siis a = 1. Tiedämme, että arvolla a = 1 lauseke pätee, ja tiedämme myös, että se pätee arvolla a + 1 = 2. Nyt tiedämme, että lauseke pätee arvolla a = 2. Mutta koska se pätee myös arvolla a + 1, sen täytyy päteä arvolla 2 + 1 = 3. Ja niin edelleen.

Ensimmäinen esimerkki

Ensimmäinen esimerkki on triviaali. Todistamme, että jos mihin tahansa parilliseen lukuun lisätään kaksi, saadaan jälleen parillinen luku. Koska liikumme positiivisissa kokonaisluvuissa, kirjoitamme parillisen luvun yleisesti muodossa 2n, missä n on positiivinen kokonaisluku. Jos n:n paikalle sijoitetaan mikä tahansa positiivinen kokonaisluku, tuloksena on parillinen luku, mikä näkyy ensi silmäyksellä. Jaollisuus kirjoitetaan pystyviivalla näin:

$$2\mid 2n$$

Tämä merkintä tarkoittaa, että kaksi jakaa lausekkeen 2n tasan. Kun osaamme jo kirjoittaa jaollisuuden, voimme kirjoittaa myös sen, mikä meidän pitää todistaa matemaattisella induktiolla.

$$2\mid 2n+2;n\in {\mathbb{Z}}^{+}$$

Tämä meidän pitää todistaa ensimmäisessä esimerkissä, eli että kaksi jakaa lausekkeen 2n + 2. Se vastaa täsmälleen alkuperäistä sanallista tehtävänantoa ”jos mihin tahansa parilliseen lukuun lisätään kaksi, saadaan jälleen parillinen luku”.

Induktion ensimmäisessä askeleessa todistamme sen ensimmäiselle alkiolle eli ykköselle. Sijoitamme lausekkeeseen n = 1:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Kaksi jakaa neljän tasan, joten ensimmäiselle alkiolle väite pätee. Seuraavaksi tulee vuoroon induktioaskel, jossa meidän täytyy todistaa, että jos väite pätee a:nnelle alkiolle, se pätee myös (a + 1):nnelle. Aluksi oletamme, että oletuksemme pätee, eli n = a:

$$2\mid 2a+2$$

Oletamme tämän lausekkeen olevan tosi, ja käytämme sitä todistuksen rakentamisessa. Haluamme nyt todistaa, että

$$2\mid 2(a+1)+2.$$

Mitä teimme? Kirjoitimme a:n paikalle (a + 1). Sulut ovat tärkeät, tämä lauseke olisi väärin: 2a + 1 + 2. Emme lisää ykköstä koko lausekkeeseen, vaan todella teemme a:sta yhtä suuremman lausekkeen eli (a + 1). Muokkaamme lauseketta kertomalla sulut auki.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Nyt pieni sivupolku jaollisuuteen. Jos meillä on kaksi lukua, sanotaan p ja q, jotka ovat jaollisia jollakin luvulla, vaikkapa r:llä, niin pätee, että myös niiden summa on jaollinen luvulla r. Siis pätee:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Voimme sijoittaa siihen esimerkiksi luvut p = 8, q = 20 ja r = 4. Näemme, että neljä jakaa sekä kahdeksan että kaksikymmentä. Ja samoin se jakaa myös niiden summan 8 + 20 = 28.

Miten tätä hyödynnetään esimerkissämme? Jaamme oikean puolen luvuiksi p ja q näin:

$$p=2a+2;q=2$$

Luku q eli kaksi on triviaalisti jaollinen kahdella. Myös lauseke p on jaollinen kahdella, koska oletus kertoo sen. Lauseke p vastaa täsmälleen oletustamme, jonka oletamme todeksi. Ja jos p on jaollinen kahdella ja samalla q on jaollinen kahdella, niin myös niiden summa on jaollinen kahdella.

Vielä kerran tästä oletuksesta. Alussa sanoimme, että oletamme pätevän

$$2\mid 2a+2.$$

Siksi kun törmäsimme todistusta rakentaessamme lausekkeeseen 2a + 2, saatoimme sanoa, että se on jaollinen kahdella. Juuri siksi, että se on oletuksemme. Tämä on yleensä matemaattisen induktion vaikein vaihe: ymmärtää, milloin ja miksi induktio-oletusta voi käyttää.

Näin induktio päättyy, todistus on onnistuneesti tehty, väite pätee.

Jos haluaisit, voisit jakaa sen toisin etkä tarvitsisi oletusta. p = 2n ja q = 2 + 2. Luku q = 4 on triviaalisti jaollinen kahdella, ja samoin p = 2n, koska kahdella jaettaessa jää luku n, joka on positiivinen kokonaisluku. Saimme jälleen kaksi lauseketta, jotka ovat molemmat jaollisia kahdella, joten myös niiden summa on jaollinen kahdella.

Molemmissa tapauksissa todistimme kuitenkin, että

1. annettu lauseke pätee arvolla n = 1,
2. jos lauseke pätee arvolla n, niin se pätee myös arvolla n + 1.

Tästä voimme jo päätellä:

• Tiedämme, että lauseke pätee arvolla n = 1.
• Jos se pätee arvolla n, sen täytyy päteä myös arvolla n + 1, eli myös arvolla 1 + 1, eli lauseke pätee myös arvolla n = 2.
• Jos se pätee arvolla n, sen täytyy päteä myös arvolla n + 1, eli myös arvolla 2 + 1, eli lauseke pätee myös arvolla n = 3.
• Jos se pätee arvolla n, sen täytyy päteä myös arvolla n + 1, eli myös arvolla 3 + 1, eli lauseke pätee myös arvolla n = 4.
• Jos se pätee arvolla n, sen täytyy päteä myös arvolla n + 1, eli myös arvolla 4 + 1, eli lauseke pätee myös arvolla n = 5.
• …

Toinen esimerkki

Seuraavaksi todistamme matemaattisella induktiolla yksinkertaisen väitteen:

$$2^n\ge 2n;n\in {\mathbb{Z}}^{+}.$$

Ensin ensimmäinen askel: selvitämme, päteekö väite arvolla n = 1, positiivisten kokonaislukujen ensimmäisellä alkiolla, joista n valitaan.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Se pätee triviaalisti. Nyt siirrymme induktioaskeleeseen, jossa meidän täytyy selvittää, päteekö väite arvolla n = a + 1, kun se pätee arvolla n = a. Oletuksemme on siis, että pätee

$$2^a\ge 2a$$

ja haluamme todistaa:

$$2^{a+1}\ge 2(a+1)$$

Kirjoitamme vasemman puolen ensin auki potenssien laskusääntöjen avulla ja kerromme oikean puolen yksinkertaisesti auki.

$$2\cdot 2^a\ge 2a+2$$

Vasemmalla puolella käytämme kertolaskun sijaan yhteenlaskua, oikean puolen jätämme ennalleen.

$$2^a+2^a\ge 2a+2$$

Nyt hyödynnämme oletusta. Oletus on väite, jonka oletamme pätevän. Epäyhtälön kummallakin puolella on kaksi termiä, jotka ovat summana. Samalla kuitenkin tiedämme, että

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Ensimmäinen rivi on oletus ja toinen väite on triviaali (pienin 2^a saadaan arvolla a = 1, ja se on juuri kaksi). Tiedämme siis, että vasemmalla puolella molemmat termit ovat suurempia tai yhtä suuria kuin molemmat termit oikealla puolella. Näin olemme todistaneet induktiolla, että jos lauseke pätee arvolla a, se pätee myös arvolla (a + 1), ja koska lauseke pätee myös ykkösellä, annettu lauseke on tosi.

Kolmas esimerkki

Yritetään todistaa seuraava väite:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{Z}}^{+}$$

Sanallisesti: jos n on jaollinen kolmella, niin myös n² on jaollinen kolmella. Jos n ei ole jaollinen kolmella, lauseke pätee triviaalisti (implikaation määritelmän mukaan), joten käsittelemme tapauksia, joissa n on jaollinen kolmella. Se tuottaa positiivisten kokonaislukujen jonon a_i=3, 6, 9, 12, 15… Tästä lähtien liikumme tässä jonossa a_i.

Induktiotodistuksen aloitamme ensimmäisellä askeleella eli sillä, päteekö väite ensimmäiselle alkiolle. Muistutan, että liikumme jonossa a_i, joten otamme tämän jonon ensimmäisen alkion eli alkion a₁, joka on kolme. Kolmoselle lauseke pätee:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Nyt siirrymme induktioaskeleeseen. Näemme, että jonon a_i voisi kirjoittaa muodossa 3n, missä n on positiivinen kokonaisluku. Toinen alkio on siis kolme suurempi kuin edellinen ja niin edelleen. Oletetaan nyt, että lauseke pätee arvolla n ja meidän täytyy varmistaa, että se pätee myös arvolla (n + 3), sillä tämä sääntö tuottaa sen jonon seuraavan alkion, jossa liikumme. Kirjoitamme ensin oletuksen:

$$3\mid n\Rightarrow 3\mid n^2$$

ja sitten sen, mitä haluamme todistaa

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Kerromme toisen puolen sulun auki kaavalla:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Ja olemme jo melkein perillä. Vasemmalla puolella on lauseke, joka on varmasti jaollinen kolmella, koska n on oletuksen mukaan jaollinen kolmella (liikumme vain jonon a_i luvuissa) ja kolmonenkin on jaollinen kolmella. Oikealla puolella on ensin n², joka on oletuksen mukaan jaollinen kolmella. Tiedämme nimittäin, että n on jaollinen kolmella, ja oletus kertoo, että jos n on jaollinen kolmella, niin myös n² on jaollinen kolmella:

$$3\mid n\Rightarrow 3\mid n^2$$

Seuraavaksi tulee lauseke 6n, joka on triviaalisti jaollinen kolmella. Voit ajatella sitä murtoluvun supistamisena:

$$\frac{6n}{3}=2n$$

Muuttuja n on jokin positiivinen kokonaisluku, joten myös tulo 2n on positiivinen kokonaisluku, eli kolmella jaettaessa saimme positiivisen kokonaisluvun, ja lausekkeen 6n täytyy siis olla jaollinen kolmella. Ja lopun yhdeksän on jälleen jaollinen kolmella. Lauseke pätee ensimmäiselle alkiolle ja induktioaskel on todistettu, joten lauseke on tosi.

Sulkujen määrä lausekkeessa

Viimeinen esimerkki on hieman epätyypillinen. Yritämme todistaa väitteen, että sulkujen määrä yksinkertaisessa lausekkeessa on aina parillinen, jotta näet, että matemaattista induktiota voi käyttää aivan toisenlaisessakin yhteydessä kuin pelkissä positiivisissa kokonaisluvuissa. Alussa meidän täytyy määritellä, mikä on yksinkertainen lauseke. Yksinkertainen lauseke on:

• positiivinen kokonaisluku,
• jos p on yksinkertainen lauseke, niin myös (p²) on yksinkertainen lauseke,
• jos p ja q ovat yksinkertaisia lausekkeita, niin myös (p + q) on yksinkertainen lauseke.

Mitä ovat siis yksinkertaiset lausekkeet: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Ja nämä taas eivät ole yksinkertaisia lausekkeita:

• 1 + 2 → ulommat sulut puuttuvat,
• (1 + 2 → oikea sulku puuttuu,
• 13² → ulommat sulut puuttuvat,
• (1 + 2 + 3) → sulut puuttuvat, oikea merkintä olisi (1 + (2 + 3))

Yksinkertainen lauseke voi syntyä esimerkiksi näin. Valitaan aluksi yksinkertainen lauseke (a + b). Nyt sijoitamme a:n tilalle yksinkertaisen lausekkeen a = (c + d), jolloin saamme ((c + d) + b), ja b:n tilalle sijoitamme kolmosen: ((c + d) + 3). c:n tilalle sijoitamme kymmenen: ((10 + d) + 3) ja lopuksi d:n tilalle sijoitamme (5²): ((10 + (5²)) + 3). On tärkeää noudattaa sulkuja, muuten se ei toimi.

Nyt todistamme, että yksinkertaisessa lausekkeessa on parillinen määrä sulkuja (parillisiin lukuihin kuuluu myös nolla).

Induktion ensimmäisessä askeleessa valitsemme jonkin ensimmäisen alkion. Tässä tapauksessa ensimmäinen alkio on triviaalein yksinkertainen lauseke eli mikä tahansa positiivinen kokonaisluku. Asetamme siis

$$j=n;n\in {\mathbb{Z}}^{+}.$$

Lausekkeelle j pätee, että sulkujen määrä on nolla, joten ensimmäinen alkio kelpaa. Induktioaskeleessa oletamme, että meillä on kaksi yksinkertaista lauseketta p ja q ja että kummassakin on parillinen määrä sulkuja. Silloin meidän täytyy todistaa, että myös yksinkertaisissa lausekkeissa (p + q) ja (p²) on parillinen määrä sulkuja.

Ensin yhteenlasku. Määrittelemme vielä funktion z(q), joka palauttaa lausekkeen q sulkujen määrän. Silloin pätee, että lausekkeessa (p + q) on z(p) + z(q) + 2 sulkua. Siinä on siis kaksi sulkua enemmän kuin lausekkeiden p ja q sulkujen summa. Oletuksen mukaan sekä z(p) että z(q) ovat parillisia, joten kun lasketaan yhteen kolme parillista lukua, saadaan jälleen parillinen luku. Tässä tapauksessa väite pätee.

Sitten potenssi. Jälleen pätee oletus, että yksinkertaisessa lausekkeessa p on parillinen määrä sulkuja. Lausekkeessa (p²) on silloin z(p) + 2 sulkua, eli taas kaksi sulkua enemmän kuin lausekkeessa p. Tässäkin tapauksessa lasketaan yhteen parillisia lukuja, joten tulos on parillinen.

Väite pätee ensimmäiselle alkiolle ja myös induktioaskeleessa, joten väite on tosi.