Ero sivun ”Satunnainen esimerkki induktiotodistuksesta” versioiden välillä
Ei muokkausyhteenvetoa |
Ei muokkausyhteenvetoa |
||
Rivi 37: | Rivi 37: | ||
x(x+1)(x+2)/3 + sigma ( k = x+1, x+1 ) { k(k+1) }. | 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. | |||
</pre> | </pre> |
Versio 5. syyskuuta 2007 kello 21.50
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.