Loading [MathJax]/jax/output/CommonHTML/jax.js
This course has already ended.

Induktiotodistus

Kuvitellaan pitkä jono dominopalikoita. Milloin ne kaikki saadaan kaatumaan koskemalla vain jonon ensimmäiseen palikkaan? Videon perusteella voitaisiin muotoilla seuraavat ehdot.

  1. Ensimmäinen palikka saadaan kaadettua.
  2. Jokainen kaatuva palikka kaataa myös seuraavan palikan.

Näistä molempien on toteuduttava, jotta kaikki palikat kaatuvat. Tulkitaan nyt jokainen dominopalikka väitteeksi p(n), jonka sisältö riippuu palikan järjestysnumerosta n jonossa. Jos jonon k. palikka kaatuu, lause p(k) on tosi. Jos puolestaan k. palikka kaatuessaan kaataa myös palikan k+1, lause p(k)p(k+1).

Mitä tapahtuu, jos lause p(1) on tosi ja lause p(k)p(k+1) on tosi jokaisella luonnollisella luvulla k?

Lause.

Olkoon n luonnollinen luku ja p(n) sitä koskeva väite. Jos

  1. lause p(1) on tosi
  2. aina, kun kN, lause p(k)p(k+1) on tosi,

niin lause p(n) on tosi jokaisella nN. Tämä on induktioperiaate.

Matemaattinen induktio, eli induktioperiaate perustelee hyvin erityisen todistusmenetelmän. Induktiotodistus on mahdollinen silloin, kun todistettava väite p(n) koskee peräkkäisiä luonnollisia lukuja. Sillä on myös seuraava, yksinkertainen rakenne.

Todistus.

Todistetaan väite induktiolla.

  1. Alkuaskel. Osoitetaan, että lause p(1) on tosi.
  2. Induktioaskel. Osoitetaan, että lause p(k)p(k+1) on tosi, kun k on luonnollinen luku. Tämä tapahtuu olettamalla, että lause p(k) on tosi (induktio-oletus, io) ja sen jälkeen todistamalla, että lause p(k+1) on tosi (induktioväite).

Edellä osoitetun ja induktioperiaatteen nojalla väite p(n) on tosi kaikilla luonnollisilla luvuilla n.

Esimerkki.

Osoita, että 1+2+3++n=n(n+1)2, kun nN.

Todistus.

Todistetaan väite induktiolla.

  1. Alkuaskel. Kun n=1, väite tulee muotoon

    1=1(1+1)2=1,

    mikä on tosi.

  2. Induktioaskel. Tehdään induktio-oletus, jonka mukaan

    1+2+3++k=k(k+1)2,

    kun k on luonnollinen luku. Pyritään osoittamaan, että

    1+2+3++k+(k+1)=(k+1)(k+2)2.

    Induktio-oletuksen nojalla voidaan kirjoittaa

    1+2+3++k+(k+1)=(1+2+3++k)+(k+1)io=(k(k+1)2)+k+1=k(k+1)+2(k+1)2=(k+1)(k+2)2,

    eli induktioväite on tosi.

Induktioperiaatteen nojalla siis

1+2+3++n=n(n+1)2

kaikilla luonnollisilla luvuilla n.

Esimerkki.

Todista Bernoullin epäyhtälö: jos 1+x0, missä xR,

(1+x)n1+nx

jokaiselle luonnolliselle luvulle n.

Todistus.

Olkoon 1+x0. Todistetaan väite induktiolla.

  1. Alkuaskel. Kun n=1, väite tulee muotoon (1+x)11+x, mikä on tosi.

  2. Induktioaskel. Tehdään induktio-oletus, jonka mukaan (1+x)k1+kx, kun k on luonnollinen luku. Pyritään osoittamaan, että (1+x)k+11+(k+1)x. Induktio-oletuksen ja luvun x määrittelyn nojalla voidaan kirjoittaa

    (1+x)k+1=(1+x)k(1+x)io(1+kx)(1+x)=1+x+kx+kx2=1+(k+1)x+kx201+(k+1)x,

    eli induktioväite on tosi.

Induktioperiaatteen nojalla siis (1+x)n1+nx kaikilla luonnollisilla luvuilla n.

Induktiotodistuksen alkuaskeleessa voidaan valita myös mikä tahansa muu luonnollinen luku kuin 1, mutta tällöin väite tulee todistetuksi vain kaikille tätä suuremmille luonnollisille luvuille.

Esimerkki.

Tutki, mistä luonnollisen luvun n arvosta alkaen 2nn!, ja todista väitteesi induktiolla. Luvun n kertoma (factorial) n! määritellään asettamalla

n!=123n.
Ratkaisu.

Tutkitaan lausekkeita 2n ja n!, kun n=1,2,3,.

21=2>1=1!22=4>2=12=2!23=8>6=123=3!24=1624=1234=4!

Siis kun n=4, lause 2nn! on tosi. Todistetaan induktiolla, että 2nn! aina, kun luonnollinen luku n4.

  1. Alkuaskel. Tapaus n=4 käsiteltiin jo.

  2. Induktioaskel. Tehdään induktio-oletus, jonka mukaan 2kk!, kun k4 on luonnollinen luku. Pyritään osoittamaan, että 2k+1(k+1)!. Koska k4, niin 2<k+1, jolloin induktio-oletuksen nojalla voidaan kirjoittaa

    2k+1=22kio2k!<k!(k+1)=(k+1)!,

    eli induktioväite on tosi.

Induktioperiaatteen nojalla siis 2nn! kaikilla luonnollisilla luvuilla n4.

Posting submission...