Tehtävä:
Todistaminen induktiolla

Lyhyt MathCheck-ohje (uuteen välilehteen)

Induktio on usein käytetty menetelmä todistaa, että jokin väite pätee jokaisella luonnollisella luvulla `n`. Tietojen­käsittely­tieteessä käytetään usein rakenteellista induk­tiota, jossa todistetaan, että jokin väite pätee kaikille tietyn­laisille rakenteille. Sen periaate on sama kuin induktion ja siitä on jäljempänä esimerkki.

Induktio­todistuksessa todistetaan kaksi asiaa:

Induktio­todistus osoittaa, että ei ole olemassa pienintä luonnollista lukua, jolla väite ei päde. Nolla ei ole sellainen, koska erikseen todistetaan, että väite pätee nollalle. Jos nollaa suurempi luonnollinen luku `i` olisi sellainen, niin väite pätisi `(i-1)`:lle (koska `i` on pienin, jolle väite ei päde) mutta ei `i`:lle. Se on risti­riidassa induktio­askeleen kanssa kun `n = i-1`.

Induktio­todistus ei siis yritäkään todistaa, että ei ole olemassa toiseksi pienintä eikä kolmanneksi pienintä luonnollista lukua, jolla väite ei päde. Se todistaa vain, että ei ole pienintä. Mutta maalais­järki sanoo, että jos ei ole pienintä, ei voi olla toiseksi eikä kolmanneksi pienintä. Tämä pätee myös matematiikassa ja siksi induktio on pätevä todistu­menetelmä.

Induktioaskeleessa oletetaan, että se pätee, mikä koko induktio­todistuksella halutaan todistaa. Tämä saattaa näyttää päättely­virheeltä, joka tunnetaan nimellä kehä­päätelmä. Induktio­askeleen tavoitteena ei kuitenkaan ole todistaa alku­peräistä väitettä vaan sen muunnos, jossa `n` on korvattu `(n+1)`:llä. Siksi kyseessä ei ole kehä­päätelmä. Alku­peräistä väitettä kutsutaan tässä yhtey­dessä induktio-oletukseksi.

Induktio­askeleessa on syytä olla tarkkana mitä käyttää oletuksena ja mitä todistaa. Jos tässä on huolimaton, niin tekee helposti oikeasti kehä­päätelmän. Silloin induktio­askeleen todistus menee näennäisen helposti läpi, mutta tentti­vastaukseksi se ei kelpaa.

Jos halutaan todistaa, että väite pätee jokaisella positiivisella kokonais­luvulla, pohja­tapauksena käytetään `n=1`. Pohja­tapaukseksi voidaan valita mikä tahansa kokonais­luku, jolloin väite tulee todistetuksi siitä alkaen.

Todistamme esimerkin vuoksi, että jos `n in NN`, niin

`sum_(i=0)^n i^2 = 1/6 n(n+1)(2n+1)` .

Pohjatapaus on `n = 0`. Silloin vasen puoli on

`sum_(i=0)^0 i^2 = 0^2 = 0`

ja oikea puoli on

`1/6*0(0+1)(2*0+1) = 0`.

Molemmilta puolilta tuli sama tulos, joten pohjatapaus pätee. Pohja­tapaus on usein hyvin helppo todistaa, ja niin oli tälläkin kertaa.

Induktioaskeleessa oletetaan

`sum_(i=0)^n i^2 = 1/6 n(n+1)(2n+1)`

ja tulee todistaa

`sum_(i=0)^(n+1) i^2 = 1/6 (n+1)((n+1)+1)(2(n+1)+1)`

eli

`sum_(i=0)^(n+1) i^2 = 1/6 (n+1)(n+2)(2n+3)` .

Koska `sum` tarkoittaa summaa, pätee

`sum_(i=0)^(n+1) i^2``=``(sum_(i=0)^n i^2) + (n+1)^2`.

Soveltamalla induktio-oletusta se saadaan muotoon

`1/6 n(n+1)(2n+1) + (n+1)^2`.

Ottamalla `1/6 (n+1)` yhteiseksi tekijäksi saadaan

`1/6 (n+1)(n(2n+1) + 6(n+1))`.

Siis

`sum_(i=0)^(n+1) i^2``=``1/6 (n+1)(n(2n+1) + 6(n+1))`.

Koska `n(2n+1) + 6(n+1)``=``2n^2 + 7n + 6``=``2n^2 + 3n + 4n + 6``=``(n+2)(2n+3)`, pätee

`sum_(i=0)^(n+1) i^2``=``1/6 (n+1)(n+2)(2n+3)`,

mikä oli todistettava.


Nyt pääset vihdoin tekemään itse! Tavoitteena on todistaa, että jos `n in NN`, niin `sum_(i=0)^n i``=``(n(n+1))/2`. Pohja­tapauksessa vasen puoli on `sum_(i=0)^0 i``=` ja oikea puoli on (älä sievennä) `=`(nyt sievennä) . Tuli yhtä­suuret, eikö vain?
tai

Induktioaskeleen vasen puoli on `sum_(i=0)^(n+1) i``=``(sum_(i=0)^n i) +`(). Induktio-oletuksella se saadaan muotoon (älä sievennä) `=``(n+1)``=``1/2(n+1)`.
tai

Induktioaskeleen oikea puoli on (älä sievennä) `=`(nyt sievennä) `1/2`. Toi­vot­tavasti tuli yhtä­suuret!
tai

Seuraava kohde on ”Bernoullin epäyhtälö”: jos `x >= -1` ja `n in NN`, niin `(1+x)^n >= 1 + n x`. Pohjatapaus on (älä sievennä) `>=`. Molemmat puolet sieven­tämällä siitä tulee `=`, joka on totta.
tai

Merkitsemme induktioaskeleen vasenta puolta symbolilla (v). Se on (v)`=`. Jotta voisimme soveltaa induktio-oletusta, kirjoitamme sen muotoon . Tässä esiintyvä potenssilasku on aina määritelty, koska
`x >= -1`.
`n > 0`.
`n >= 0`.
tai

Induktio-oletuksen soveltaminen tuottaa . Merkitsemme sitä (i). Onko (v)`>=`(i) vai (v)`<=`(i) riippuu siitä, onko edellä kerto­merkin * perässä oleva osuus ei-nega­tii­vinen vai ei-positiivinen. Se on ei-negatii­vinen, koska
`x >= -1`.
`n > 0`.
`n >= 0`.
Siksi (v) (i).
tai

(i) sievenee helposti muotoon `1 +``x + n x^2`. Tämä on muuten se muoto mihin pitää päästäkin, mutta osuus on liikaa. Koska kyseessä on operaat­torilla `>=` muodostettu epäyhtälö, pääsemme tavoit­teeseen, jos voimme osoittaa, että liika osuus`>= 0`. Se pätee, koska
`x >= -1`
`n >= 0`
Induktio-oletuksen saa olettaa.
Neliö on aina ei-negatiivinen.
Neliö on aina positiivinen.
tai

Kirjoita vielä yhteenvedon vuoksi se väittämä, mikä induktio­askeleessa todistettiin.
tai

Tarvitaan digitaalii­piiri, jolla on `2^n` syötebittiä ja jonka tulos kertoo, montako syöte­bittiä on arvoltaan 1. Koska tulos voi olla välillä `0, ..., 2^n`, sen esittämiseen riittää `(n+1)`-bittinen luku. Piiri voidaan rakentaa kahdesta piiristä, joista kumpikin ratkaisee saman tehtävän `2^(n-1)` syöte­bitille sekä yksiköstä, joka laskee em. kahden piirin tuottamat `n`-bittiset luvut yhteen. Yhteenlasku­piirin tekemiseen riittää `c n` porttia, missä `c` on jokin vakio. Jos merkitsemme kaiken kaikkiaan tarvittavien porttien määrää `f(n)`:llä, saamme `f(0) = 0` (koska silloin syöte­bittejä on yksi, joten sen arvo sellaisenaan kertoo, montako syöte­bittiä on arvoltaan 1) ja `f(n)``=``2f(n-1) + c n`. Haluamme todistaa, että jos `n in NN`, niin `f(n)``=``c(2^(n+1) - n - 2)`.

Pohja­tapauksessa `f(n)`:n lauseke (se, joka alkaa `c`:llä) on sieventä­mättömänä ja sievennettynä . Tulihan se mikä pitikin?
tai

Induktioaskeleen saa tehdä paitsi siten, että tulos oletetaan `n`:lle (joka on vähintään `0`) ja todistetaan `(n+1)`:lle, myös siten, että tulos oletetaan `(n-1)`:lle (joka on vähintään `0` eli `n >= 1`) ja todistetaan `n`:lle. Tällä kertaa jälkimmäinen on kätevämpi, koska käytettä­vissämme on tieto `f(n)``=``2f(n-1) + c n`. Sovel­tamalla tämän oikeaan puoleen induktio-oletusta saadaan (älä sievennä)

Sitten sievennä.
.
Induktio­askel on nyt valmis, onhan?
tai

Jos `n in NN`, niin `n!` tarkoittaa `1 * 2 * ... * n`. Pätee `0! = 1! = 1` ja `(n+1)! = (n+1)n!`.

Oletamme, että ruudukossa voi kulkea vain alaspäin ja oikealle. Esimerkiksi paikkaan, joka on yhden ruudun alempana ja kaksi ruutua enemmän oikealla kuin lähtö­paikka on kolme reittiä: askel alas­päin voidaan ottaa heti, yhden oikealle suuntautuneen askeleen jälkeen tai kahden oikealle suuntautuneen askeleen jälkeen.

Todis­tamme, että paikkaan, joka on `k` ruutua alempana ja `h` ruutua enemmän oikealla kuin lähtö­paikka, on kaiken kaikkiaan `((k+h)!)/(k! h!)` eri reittiä. Tällä kertaa induktio ei käytä yhtä muuttujaa vaan kahta. Pohja­tapauksia on yhden sijaan äärettömästi, ja induktio-oletuksena käytetään yhden sijaan kahta tapausta. Silti nytkään ei syyllistytä kehä­päätelmään, koska induktio­askel tehdään siten, että `k+h` kasvaa yhdellä. Tälläkin kertaa pohja­tapaukset ovat eri muotoa ja induktio­askeleen todistama tulos samaa muotoa kuin alku­peräinen väittämä.

Jos `k=0`, niin reittejä on vain yksi, nimittäin `h` askelta oikealle. Tämä täsmää, koska silloin `((k+h)!)/(k!h!)``=``((0+h)!)/(0!h!)``=``(h!)/(1*h!)``=``1`.
Kuinka monta reittiä on olemassa, jos `h=0`?
Kuinka paljon `((k+h)!)/(k!h!)` on silloin?
Tämän todistuksen pohjatapaus oli tässä.
tai

Induktioaskel perustuu havaintoon, että jos `k > 0` ja `h > 0`, niin määränpäähän voidaan tulla kahdella tavalla, ylhäältä tai vasemmalta. Määränpäätä lähinnä ylempään kohtaan tulee näin monta eri reittiä:
`y =`
Määränpäätä lähinnä vasemmalla olevaan kohtaan tulee näin monta eri reittiä:
`v =`
tai

Kaikkiaan reittejä on `y+v`, eli nuo kaksi kertoma­häkkyrää pitää laskea yhteen. Sitä varten niiden nimittäjät pitää saada samaksi. Se onnistuu vähimmällä vaivalla, kun kerrot `y`:n osoittajan ja nimittäjän :lla ja `v`:n osoittajan ja nimittäjän :lla. Näin saatu yhteinen nimittäjä on .
tai

Nyt kun nimittäjät ovat samat, yhteen­lasku tapahtuu laskemalla osoittajat yhteen. Päästäksemme helpolla tunnistamme osoittajista yhteisen tekijän. Se on . Osoittajien loppuosista tulee yhteen­laskussa . Mutta nämähän on helppo kertoa keskenään! Siten saadaan koko osoittajaksi .
tai

Kaiken kaikkiaan summaksi `y+v` tuli siis
. tai

Lupasin havainnollistaa esimerkillä, mitä on raken­teel­linen induktio. Olkoon `f(P)` totuus­funktio, joka on rakennettu vain muuttujista, totuus­arvoisista vakioista ja operaattoreista `^^` ja `vv`. Sillä voi olla muitakin argu­ment­teja kuin `P`, mutta `P` on se jonka suhteen teemme tarkastelumme.

Todistamme rakenteellisella induktiolla, että `f(P)` on kasvava `P`:n suhteen, siis että jos `P` kasvaa, niin `f(P)` säilyy ennallaan tai kasvaa.

Pohja­tapauksena ovat totuus­arvoiset vakiot ja muuttujat. On selvää, että `P` kasvaa kun `P` kasvaa. Myös on selvää, että totuus­arvoiset vakiot ja muut muuttujat kuin `P` (esimerkiksi `Q`) säilyvät ennallaan kun `P` kasvaa.

Induktio­askeleessa pitää todistaa, että jos `f(P)` ja `g(P)` ovat kasvavia `P`:n suhteen, niin myös `f(P) ^^ g(P)` ja `f(P) vv g(P)` ovat kasvavia `P`:n suhteen. Rakenteellisen induktion iduktio­askeleessa siis oletetaan, että tavoite pätee kaikille jonkin kokoisille rakenteille, ja todistetaan, että tavoite pätee kaikille hieman isommille rakenteille. Operaattoreiden `^^` ja `vv` totuus­tauluista on helppo tarkastaa, että jos toinen tai molemmat argumentit kasvavat, niin tulos säilyy ennallaan tai kasvaa. Niinpä, jos `P` kasvaa, niin `f(P)` ja `g(P)` kasvavat tai säilyvät ennallaan, joten `f(P) ^^ g(P)` ja `f(P) vv g(P)` kasvavat tai säilyvät ennallaan.

Rakenteellinen induktio kuulostaa hienolta, mutta on todelisuudessa näin yksin­kertaista! Olennaista siinä on ymmärtää, miten isompi rakenne muodostuu pienem­mistä, sekä induktion perus­periaate, eli että osoitetaan väite pienimmille tarkasteltaville tapauksille ja että väite säilyy voimassa, kun siirrytään tapauksesta suurempaan. Pienimmät tapaukset ja siirtyminen suurempaan tulee valita siten, että niillä saadaan kaikki tapaukset, joille väite halutaan todistaa.