[#] Sisällön pääryhmät --> Diskreettiä matematiikkaa --> Matemaattinen induktio [ 1 2 ]
ESITIEDOT:
KATSO MYÖS: [#] logiikka
[#] Kansisivu
[#] Sisältö
[#] Hakemisto

Esimerkki matemaattisesta induktiosta

Todistetaan induktiolla luonnollisten lukujen 1, 2, ..., n neliöiden summaa koskeva väittämä P (n) eli

sum n k=1k2 = 1 6- n(n + 1)(2n + 1).

oikeaksi kaikilla luonnollisilla luvuilla n.

1) Arvolla n = 1 on

sum n k=1k2 = sum 1 k=1k2 = 1 ja
1- 6 n(n + 1)(2n + 1) = 1- 6 1(1 + 1)(2 . 1 + 1) = 1.

Väittämä P (1) on siis tosi. 2) Induktioaskel. Oletetaan, että P (n) on tosi ja osoitetaan tätä hyväksi käyttäen, että myös P (n + 1) on tosi. Väittämän P (n + 1) vasen puoli on

n sum +1 sum n k2 = k2 + (n + 1)2 = 1-n(n + 1)(2n + 1) + (n + 1)2 k=1 k=1 6 = 1-(n + 1)(2n2 + 7n + 6). 6

Toisen yhtäläisyysmerkin kohdalla on käytetty oletusta, että P (n) on tosi. Toisaalta väittämän P (n + 1) oikea puoli on

1 -- 6 (n + 1)[(n + 1) + 1][2(n + 1) + 1] = 1 -- 6 (n + 1)(2n2 + 7n + 6).

P (n + 1) on siis tosi, koska sen vasen ja oikea puoli ovat samat.

  [#] luonnollinen luku
 [#] summamerkintä

Kivelä, M niinkuin matematiikka, versio 1.12