70
muokkausta
Ei muokkausyhteenvetoa |
p (Lisätty luokkaan Matematiikka) |
||
(18 välissä olevaa versiota 2 käyttäjän tekeminä ei näytetä) | |||
Rivi 1: | Rivi 1: | ||
[[Category:Matematiikka]] | |||
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> | <pre> | ||
Ykkösvaihe: todistetaan että toimii kun n=0: | Ykkösvaihe: todistetaan että toimii kun n=0 (0 valittiin siksi että se oli tossa summassa k:n | ||
sigma ( k = 0, 0 ) { k(k+1) } = 0(0+1)(0+ | lähtöarvo, "k=0", eli pienin millä tän on pakko päteä - sitä pienemmillä tosta summasta ei | ||
0(0+1) = 3/3 | 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> | </pre> |