Lyhyt MathCheck-ohje (uuteen välilehteen)
Induktio on usein käytetty menetelmä todistaa, että jokin väite pätee jokaisella luonnollisella luvulla `n`. Tietojenkäsittelytieteessä käytetään usein rakenteellista induktiota, jossa todistetaan, että jokin väite pätee kaikille tietynlaisille rakenteille. Sen periaate on sama kuin induktion ja siitä on jäljempänä esimerkki.
Induktiotodistuksessa todistetaan kaksi asiaa:
Induktiotodistus 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 ristiriidassa induktioaskeleen kanssa kun `n = i-1`.
Induktiotodistus 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 maalaisjä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ä todistusmenetelmä.
Induktioaskeleessa oletetaan, että se pätee, mikä koko induktiotodistuksella halutaan todistaa. Tämä saattaa näyttää päättelyvirheeltä, joka tunnetaan nimellä kehäpäätelmä. Induktioaskeleen tavoitteena ei kuitenkaan ole todistaa alkuperäistä väitettä vaan sen muunnos, jossa `n` on korvattu `(n+1)`:llä. Siksi kyseessä ei ole kehäpäätelmä. Alkuperäistä väitettä kutsutaan tässä yhteydessä induktio-oletukseksi.
Esimerkin pohjatapaus on helppo lasku. Mieti ensin itse ja sitten kurkista tästäPitää todistaa, että `0+1 <= 2^0`. Koska `0+1 = 1`, vasemmasta puolesta tulee `1`. Koska `2^0 = 1`, oikeasta puolesta tulee `1`. Pätee `1 <= 1`, joten `0+1 <= 2^0`. .
Induktioaskeleessa 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 induktioaskeleen todistus menee näennäisen helposti läpi, mutta tenttivastaukseksi se ei kelpaa.
Jos halutaan todistaa, että väite pätee jokaisella positiivisella kokonaisluvulla, pohjatapauksena käytetään `n=1`. Pohjatapaukseksi voidaan valita mikä tahansa kokonaisluku, jolloin väite tulee todistetuksi siitä alkaen.
Todistamme, että jos `n in NN`, niin
`sum_(i=0)^n i^2 = 1/6 n(n+1)(2n+1)` .
Pohjatapauksessa `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. Pohjatapaus 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))` .
Vertaamalla tätä yllä violetilla esitettyyn tavoitteeseen huomaamme, että pääsemme tavoitteeseen, jos onnistumme osoittamaan, että
`n(2n+1) + 6(n+1)``=``(n+2)(2n+3)` .
Niinpä
`sum_(i=0)^(n+1) i^2``=``1/6 (n+1)(n+2)(2n+3)` ,
mikä oli todistettava.
Seuraavaksi tavoitteena on todistaa, että jos `n in NN`, niin
`sum_(i=0)^n i``=``(n(n+1))/2` .
Tarvitaan digitaalipiiri, jolla on `2^n` syötebittiä ja jonka tulos kertoo, montako syötebittiä 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ötebitille sekä yksiköstä, joka laskee em. kahden piirin tuottamat `n`-bittiset luvut yhteen. Yhteenlaskupiirin 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ötebittejä on yksi, joten sen arvo sellaisenaan kertoo, montako syötebittiä 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)`.
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 alaspäin voidaan ottaa heti, yhden oikealle suuntautuneen askeleen jälkeen tai kahden oikealle suuntautuneen askeleen jälkeen.
• → • → • → • ↓ ↓ ↓ ↓ • → • → • → • ↓ ↓ ↓ ↓ • → • → • → •
Todistamme, 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. Pohjatapauksia 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 induktioaskel tehdään siten, että `k+h` kasvaa yhdellä. Tälläkin kertaa pohjatapaukset ovat eri muotoa ja induktioaskeleen todistama tulos samaa muotoa kuin alkuperäinen väittämä.
Lupasin havainnollistaa esimerkillä, mitä on rakenteellinen induktio. Olkoon `f(P)` totuusfunktio. Sillä voi olla muitakin argumentteja kuin `P`, mutta `P` on se jonka suhteen teemme tarkastelumme. Sanomme, että `f(P)` on kasvava `P`:n suhteen jos ja vain jos kaikilla muiden argumenttien arvoyhdistelmillä `f(sf"F") hArr sf"F"` tai `f(sf"T") hArr sf"T"` (tai sekä että). Siis jos `P` kasvaa, niin `f(P)` säilyy ennallaan tai kasvaa. Toisin sanoen, kasvavuus ei päde jos ja vain jos jollakin muiden argumenttien arvoyhdistelmällä `f(sf"F") hArr sf"T"` ja `f(sf"T") hArr sf"F"`.
Todistamme rakenteellisella induktiolla, että jos `f(P)` on rakennettu vain muuttujista, totuusarvoisista vakioista ja operaattoreista `^^` ja `vv`, niin se on kasvava `P`:n suhteen.
Pohjatapauksena ovat totuusarvoiset vakiot ja muuttujat. On selvää, että `P` kasvaa kun `P` kasvaa. Myös on selvää, että totuusarvoiset vakiot ja muut muuttujat kuin `P` (esimerkiksi `Q`) säilyvät ennallaan kun `P` kasvaa.
Induktioaskeleessa 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. Siis induktio-oletus on, että jos `P` kasvaa, niin `f(P)` ja `g(P)` kasvavat tai säilyvät ennallaan. Operaattoreiden `^^` ja `vv` totuustauluista on helppo tarkastaa, että jos toinen tai molemmat argumentit kasvavat, niin tulos säilyy ennallaan tai kasvaa: mikään rivi ja mikään sarake ei sisällä ensin `sf"T"` ja sitten `sf"F"`. 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.
Rakenteellisen induktion induktioaskeleessa siis oletetaan, että tavoite pätee kaikille jonkin kokoisille rakenteille, ja todistetaan, että tavoite pätee kaikille hieman isommille rakenteille. Rakenteellinen induktio kuulostaa hienolta, mutta on todellisuudessa näin yksinkertaista! Olennaista siinä on ymmärtää, miten isompi rakenne muodostuu pienemmistä, sekä induktion perusperiaate, 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.