Lähdekoodi sivulle Satunnainen esimerkki induktiotodistuksesta

Jos ihan periaate on hukassa, katso ensin [http://fi.wikipedia.org/wiki/P%C3%A4%C3%A4ttely#Induktiivinen_p.C3.A4.C3.A4ttely Induktiivisen päättelyn periaate filosofiassa], ja [http://fi.wikipedia.org/wiki/Matemaattinen_induktio matemaattisen induktion määritelmä].

<pre>
Pohditaan, miten todistetaan induktiolla että sigma ( k = 0, n ) = n(n+1)(n+2) / 3, 
oli n mitä tahansa.
</pre>

Induktiossa on aina kaksi vaihetta: ykkösvaiheessa todistetaan että väite pätee jollain
oikealla numerolla, joka valitaan sopivasti. Kakkosvaiheessa todistetaan, että väite
voidaan pumpata aina yhdestä numerosta sitä seuraavaan - eli todistetaan, että jos 
induktio-oletetaan että väite pätee numerolla x (matemaatikot vaihtelevat kirjaimiaan), 
silloin voidaan todistaa että väite pätee numerolla x+1 myös. Näistä kahdesta seuraa, 
että väite pätee siitä alkunumerosta lähtien jokaisella numerolla, ja induktioperiaatteen
mukaan se silloin pätee kaikilla numeroilla.

Itse induktioperiaate on huijaus, jolla pärjätään äärettömyyden kanssa. Kun kukaan ei oikein
tiennyt, voiko jotain sanoa "kaikista (tiettyä suuremmista)" vain sen perusteella että 
"aina yhtä isompi" on jonkinlainen, sovittiin matematiikassa että tästä seuraa että kaikista
voidaan sanoa jotain, koska se kuulostaakin jokseenkin järkevältä valtaosalle väestöstä. :)
Induktiota on selitetty mukavasti [http://solmu.math.helsinki.fi/1997/1/retki.html Turistina matematiikassa] -kiertueella, kunhan formaaliin ilmaisuun tottuu.

<pre>
Ykkösvaihe: todistetaan että toimii kun n=0 (0 valittiin siksi että se oli tossa summassa k:n 
lähtöarvo, "k=0", eli pienin millä tän on pakko päteä - sitä pienemmillä tosta summasta ei 
saa mitään irti):
sigma ( k = 0, 0 ) { k(k+1) } = 0(0+1)(0+2) / 3
                     0(0+1)   = 0/3
                            0 = 0

Kakkosvaihe: oletetaan että toimii kun n = x jollekin x (ja me tiedetään että 
jollakin x se toimii koska just todistettiin että vaikkapa x = 0 toimii). 
Todistetaan tän pohjalta että toimii myös kun n = x + 1 eli yhtä isompi.

Oletuksen perusteella me tiedetään että (korvataan n = x) 

sigma ( k = 0, x ) { k(k+1) } = x(x+1)(x+2) / 3   ilman mitään ongelmia, ei tarvi ees siivota.

Nyt me halutaan todistaa että (korvataan n = x+1)

sigma ( k = 0, x+1 ) { k(k+1) } = (x+1)((x+1) + 1)((x+1) + 2) / 3

Tavoite: jaetaan sigma kahteen palaan (sen saa aina jakaa kahtia niin, että ensin 
juoksutetaan juoksutusnumeroa johonkin välietappiin, ja sitten etappi+1:stä loppuun asti),
esmers
   sigma ( k = 0, y ) { k(k+1) } on sama kuin (oletetaan että z < y on hyvä välietappi)
   sigma ( k = 0, z ) { k(k+1) } + sigma ( k = z+1, y ) { k(k+1) }
Ja jaetaan se niin, että se toinen jäljelle jäävä sigma on ton oletuksen sigma, jotta
me voidaan annihiloida se korvaamalla se oletuksesta saadun kaavan oikealla puolella, 
jota on paljon helpompi käpistellä.

Tehtiin jako:

sigma ( k = 0, x ) { k(k+1) } + sigma ( k = x+1, x+1 ) { k(k+1) } :ksi.

Koska tehtiin aiemmin oletus tosta sigma(k=0,x):stä, ja tehdyt oletukset pitää aina 
maailman tappiin, me voidaan nyt heittää se mäkeen ja korvata se sillä mitä me 
oletettiin sen olevan, eli x(x+1)(x+2)/3:lla. Saadaan

x(x+1)(x+2)/3 + sigma ( k = x+1, x+1 ) { k(k+1) }.

Kakkosvaiheen väite oli siis että tämä hirviö olisi sama kuin (x+1)((x+1) + 1)((x+1) + 2) / 3.

Meillä on vielä riesanamme yksi sigma, mutta onneksi se on helppo - k menee x+1:stä x+1:een 
itseensä, mikä tarkoittaa sitä ettei sigmaa tarvita - sijoitetaan vain k = x+1. Saadaan
toissarivistä:

x(x+1)(x+2)/3 + (x+1)((x+1) + 1)

ja meidän pitäis todistaa että se on sama kuin 

(x+1)((x+1) + 1)((x+1) + 2) / 3, joka on kakkosvaiheen väitteen oikea puoli.

Tässä vaiheessa ollaan käytetty induktiotodistuksen peukalosäännöt loppuun ja siirrytään ihan perusveivaukseen, miten yhdestä saadaan toisen näköinen.

Helpointa on siivota molemmat puolet ihan perusmuotoonsa, jolloin niitä yleensä voi 
vaan verrata ja todeta että ne on samat. Matemaatikot tosin arvostaa enemmän, jos 
veivaa koko ajan konsistentisti vain yhtä puolta, ja lopulta näyttää ta-daa että se on 
sama kuin se toinen puoli, koska tällöin ne voi helpommin vakuuttua siitä ettei niitä oo 
huijattu jollain oikean puolen vääränlaisella puliveivauksella (kuten kertomalla kaikki 
nollalla). Nekin tosin salaa voi tehdä sen niin että siivoaa molemmat ensin perusmuotoonsa
ja sitten vertaa että ne on samat, ja tekee sen "oikean puolen" siivoamisen takaperin parissa 
nopeutetussa askeleessa vasemmalle puolelle jotta se näyttää suoraan siltä oikealta puolelta.

Loppuun on tyylikästä sanoa että ykkös- ja kakkosvaiheen sekä induktioperiaatteen nojalla
alkuperäinen väite on todistettu, jotta kaikki tietävät mihin asti päästiin. 

</pre>