<< >> Ylös Otsikko Hakemisto Kommunikaatio

Täydellinen induktio

Esitiedot:jonot, sarjat

Tutkiessaan ympärillään olevaa maailmaa ihminen pyrkii löytämään siitä yleisiä lainalaisuuksia. Induktiolla tarkoitetaan sellaista tiedonhankintamenetelmää, jossa jokin yleinen sääntö päätellään yksittäistapauksista tehtyjen havaintojen perusteella.

Olkoon tutkimuskohteena joukko E. Otetaan tarkasteltavaksi muutamia sen alkioita. Oletetaan, että kaikilla tähän otokseen kuuluvilla alkioilla havaitaan olevan jokin yhteinen ominaisuus. Jos tämän perusteella väitetään, että joukon E kaikilla alkioilla on mainittu ominaisuus, niin ollaan turvauduttu induktioon. Kyseessä on niin sanottu epätäydellinen induktio, joka ei ole loogisesti pätevää päättelyä. Voihan nimittäin käydä niin, että jollain tämän otoksen ulkopuolelle jääneellä E:n alkiolla ei olekaan tätä ominaisuutta. Luonnontieteissä joudutaan usein tyytymään induktion avulla saatuihin tuloksiin.

Esimerkki 4. Jonon an alkiot ovat muotoa (n + 1)! - 1, jossa n  Z+. Väitetään, että jonon alkiot ovat alkulukuja. Koska sarjan ensimmäiset kolme alkiota toteuttavat ehdon, eli

a1 = (1 + 1)! - 1 = 1,
a2 = (2 + 1)! - 1 = 5,
a3 = (3 + 1)! - 1 = 23,

voisimme tehdä päätelmän, että väitös pitää paikkansa. Todistus on kuitenkin epätäydellinen, sillä heti seuraava alkio ei toteuta ehtoa, eli

a5 = (4 + 1)! - 1 = 119 = 717.

Matematiikassa tarkoitetaan täydellisellä induktiolla todistusmenetelmää, jonka avulla voidaan todistaa positiivisten kokonaislukujen yleisiä ominaisuuksia. Menetelmä perustuu siihen, että positiiviset kokonaisluvut muodostavat päättymättömän jonon, missä jonon kullakin jäsenellä on välittömänä seuraajanaan sitä yhtä suurempi positiivinen kokonaisluku.

Tarkastellaan täydellisen induktion periaatetta:

Määritelmä 13. Olkoon p(n) jokin joukossa Z+ määritelty avoin lause. Lause p(n) on induktioperiaatteen nojalla identtisesti tosi joukossa Z+, jos voidaan osoittaa, että

Ehto 1. lause p(1) on tosi,

Ehto 2. implikaatio p(k p(k + 1) on tosi.

Induktioehto 1 takaa sen, että luvulla 1 on lauseen p ilmoittama ominaisuus. Induktioehdon 2 nojalla tämä ominaisuus voidaan "siirtää" luvulta k sen seuraajalle k + 1. Antamalla tässä k:lle peräkkäiset arvot 1, 2, 3, ... toteamme, että lauseesta p(1) seuraa lause p(2), lauseesta p(2) lause p(3), tästä puolestaan p(4), ja niin edelleen. Ominaisuus p voidaan siis askel askeleelta ulottaa koskemaan mitä hyvänsä positiivista kokonaislukua.

Täydellisen induktion periaate on itse asiassa aksiooman luontoinen positiivisten kokonaislukujen ominaisuus. Italialainen matemaatikko Giuseppe Peano määritteli viime vuosisadan lopulla aksiomaattisesti positiivisten kokonaislukujen joukon. Hänen seuraaja-käsitteeseen perustuvassa aksioomajärjestelmässään on eräänä aksioomana täydellisen induktion periaate. Näistä aksioomeista käytetään nimitystä Peanon aksioomat.

Esimerkki 5. Todistetaan täydellisellä induktiolla kuutiosarjan kaava.

Siis todistetaan että yhtälö

on voimassa kaikilla positiivisilla kokonaisluvuilla.

Ehto 1. Osoitetaan, että kaava pätee kun n = 1. Näin on, koska

.

Ehto 2. Osoitetaan, että implikaatio p(k p(k + 1) on tosi.

Tehdään induktio-oletus eli oletetaan, että p(k) on tosi ja silloin yhtälö

on voimassa.

Väitetään, että p(k + 1) on tosi. Väite yhtälöksi kirjoitettuna saa muodon

Väite osoitetaan todeksi yhtälöketjun



avulla. Ensimmäisessä yhtälössä on käytetty apuna aiemmin tehtyä induktio-oletusta.

Näin on osoitettu, että tarkasteltava implikaatio on voimassa. Siis induktioperiaatteen mukaan väite on todistettu oikeaksi.

Animaatio 1.Induktiotodistus

Tehtävä 10. Osoita, että Fibonaccin luvuille on voimassa

Tehtävä 11. Lucasin luvut määritellään seuraavasti: L1 = 2, L2 = 1 ja Ln+2 = Ln+1 + Ln, n  Z+. Osoita, että näille luvuille on voimassa


<< >> Ylös Otsikko Hakemisto Kommunikaatio