Turistina matematiikassa

Lomakohteen ympäristöön on tapa tehdä tutustumisretkiä. Matematiikkaankin voi tehdä opintomatkoja. Retkellä pysähdytään tarkastelemaan muutamia kohteita. Osa kohteista esitellään, osaan saa tutustua omin päin. Kohteet on numeroitu, ja omin päin tutustumiseen tarkoitetut on merkitty *:llä. Retken päätteeksi voi vielä tutustua muutamaan lisäkohteeseen. - Seuraavan retken yhteydessä julkaistaan sitten niiden kohteiden esittelyt, jotka nyt jäävät retkeilijän omatoimisuuden varaan.

Ensimmäinen retki. Induktio - todistamisen työkalu

A Peruskierros

1 Induktioperiaate.

Varsin monet matemaattiset väittämät ovat erikoistapauksia lauseesta, jonka yleinen muoto on 'kaikilla joukon A alkioilla x on ominaisuus P(x)'. Jos A on pieni, väittämän totuudesta voi vakuuttua vaikkapa tarkastelemalla jokaista A:n alkiota erikseen. Esimerkiksi lauseen 'kaikkien kaksinumeroisten yhdeksällä jaollisten lukujen numeroiden summa on jaollinen yhdeksällä' totuudesta vakuuttuu tarkastelemalla lukuja 18, 27, 36, 45, 54, 63, 72, 81, 90 ja 99.

Jos joukko A on ääretön, esimerkiksi jokin kokonaislukujen joukon ääretön osajoukko, niin A:ta koskevien väitteiden todistaminen on mahdotonta sillä tavoin, että A:n lukuja tarkastellaan kutakin erikseen. Tällaisissa tapauksissa induktio on usein käyttökelpoinen menetelmä. Matemaattinen induktio on ehdottoman varma todistusmenetelmä, toisin kuin yleisen filosofisen kielenkäytön mukainen induktio, joka on erikoistapauksista yleisiä lainalaisuuksia päättelevä menetelmä. Toisinaan matemaattista induktiota kutsutaan myös täydelliseksi induktioksi.

Olkoon a kokonaisluku ja P(n) jokin kokonaislukua n koskeva väite. Silloin P(n) on tosi kaikilla , jos seuraavat kaksi ehtoa ovat voimassa:

P(a) on tosi.
Kaikilla siitä, että väite P(k) on tosi seuraa, että väite P(k+1) on tosi.

Induktiotodistus etenee kahdesssa vaiheessa: ensin vakuuttaudutaan siitä, että P(a) on tosi. Tämä on usein triviaalia. Toisessa vaiheessa oletetaan, vaikka ei varmasti tiedetäkään, että P(k) on tosi mielivaltaisella luvulla k, joka on , ja nojautumalla tähän olettamukseen, ns. induktio-oletukseen, osoitetaan, että P(k+1) on tosi. Yhdessä (1) ja (2) takaavat, että P(n) todella pätee kaikilla : koska P(a) pätee, ja P:n pätemisaluetta voidaan laajentaa askel kerrallaan aina yhtä suurempiin lukuihin, niin myös P(n) nähdään todeksi.

2.

Osoitetaan, että kaikilla luonnollisilla luvuilla

pätee

Annetaan tälle väitteelle nimi P(n).

Induktiotodistuksessa on kaksi vaihetta. Ensin havaitaan, että P(1) eli

on varmasti tosi väite. Oletetaan sitten, että P(k) on tosi väite eli että

Mutta tällöin

Koska k+2=(k+1)+1, olemme saaneet väitteen P(k+1), ja induktiotodistus on valmis.

3* Bernoullin epäyhtälö.

Osoita, että kaikilla luonnollisilla luvuilla n ja kaikilla reaaliluvuilla x>-1 pätee

4 Induktiivinen määrittely.

Induktioperiaate tekee mahdolliseksi määritellä täsmällisesti kokonaislukujen funktioita. Esimerkiksi merkinnän

, 'kerrotaan a n kertaa itsellään", täsmällisempi määrittely olisi

,
, kun n on kokonaisluku, .

Samoin n-kertoman n! määritelmä olisi

0!=1,
.

Induktiivisesti voimme määritellä myös summamerkin: jos

, ..., on lukujono, niin

5* Binomikaava.

Merkitään

Osoita, että

Vihje: Luvut

löytyvät tunnetusti "Pascalin kolmion"

[kaava puuttuu]

n:nneltä riviltä. Todista ensin Pascalin kolmion ominaisuus

6.

Induktiotodistus on mekaaninen, jos väittämän P(n) täsmällinen muoto on tiedossa. Yleensä kuitenkin P(n) on ensin arvattava ja sitten vasta todistettava. Luonnollinen tapa löytää hyvä arvaus on tutkia ensin yksinkertaisia erikoistapauksia.

Joukossa A on n alkiota. Montako epätyhjää osajoukkoa joukolla A on? Yksialkioisella joukolla on tietysti tasan yksi epätyhjä osajoukko, se itse. Kaksialkioisella joukolla on kolme osajoukkoa, , ja . Kolmialkioisella joukolla on kolme yksialkioista osajoukkoa, kaksialkioiset osajoukot , ja sekä kolmialkioinen osajoukko , yhteensä seitsemän joukkoa. Muotoillaan väite P(n):

n-alkioisella joukolla on epätyhjää osajoukkoa.

Induktiotodistus:

P(1) on tosi, kuten edellä nähtiin.
Oletetaan, että P(k) on tosi eli että jokaisella k-alkioisella joukolla on epätyhjää osajoukkoa. Olkoon A joukko, jossa on k+1 alkiota; olkoon . Silloin joukossa on k alkiota. Joukon A osajoukot ovat joukon B osajoukot C, joukot ja joukko A itse. Induktio-oletuksen mukaan joukkoja C ja siten myös joukkoja on kappaletta. Näin ollen A:lla on yhteensä osajoukkoa.

Induktiotodistus on valmis, P(n) on tosi kaikilla

7*.

Tasoon piirretään n suoraa; näistä mitkään kaksi eivät ole yhdensuuntaisia eivätkä mitkään kolme leikkaa toisiaan samassa pisteessä. Moneenko osaan suorat jakavat tason?

8*.

Induktiotodistuksen toinen vaihe saattaa esiintyä myös muodossa (2'): jos P(a), P(a+1), ..., P(k) ovat tosia, niin P(k+1) on tosi. Tunnetusti positiivinen kokonaisluku n on alkuluku, jos jokaisessa esityksessä

, missä p ja q ovat positiivisia kokonaislukuja, on joko p=1 tai p=n. Todista: jokainen kokonaisluku n>1 on joko alkuluku tai alkulukujen tulo.

9*.

Totuttu tapamme kirjoittaa kokonaislukuja kymmenjärjestelmässä tuntuu itsestään selvältä. Entä jos kantaluku on mielivaltainen? Lukujen kirjoittaminen n-kantaisessa jarjestelmässä on asia, joka voidaan todistaa induktiolla. Olkoon n>1 ja M positiivinen kokonaisluku. Todista, että on olemassa yksikäsitteisesti määrätyt kokonaisluvut

, ...,

siten, että

, kun j=0, 1, ..., m, ja

10.

Joskus induktiotodistus vaatii onnistuakseen, että todistetaan tavallaan enemmän, kuin oikeastaan vaaditaankaan. Unohdetaan kohta 5 ja väitetään, että

:n kerroin polynomissa

on aina

. Tämä väite P(n) on tunnetusti tosi, kun n=2. Oletetaan, että P(k) on tosi. Silloin

[kaava puuttuu]

Emme voi sanoa, että P(k+1) olisi tosi, koska emme tiedä, mikä

on. Mutta katsotaan vahvempaa väitettä Q(n), jonka mukaan

:ssä potenssien

kertoimet ovat 1, n ja

. Se on tosi, kun n=2. Jos Q(k) on tosi, niin yhtälöissä (1) voidaan kirjoittaa

. Yhtälö (1) kertoo silloin heti, että Q(k+1) on tosi.

11*.

Määritä

:n kerroin polynomissa

B Lisäkierros

12*.

Montako kaksialkioista osajoukkoa on n-alkioisella joukolla?

13*.

Montako lävistäjää on kuperalla n-kulmiolla?

14*.

Monellako eri tavalla n lukua voidaan kirjoittaa jonoon?

15*.

Olkoon f(n) luku, joka ilmoittaa, kuinka monella eri tavalla n lukua

, ...,

voidaan kirjoittaa jonoon niin, että jonon k:s luku on aina eri kuin

, k=1, 2, ..., n. Osoita, että f(n+1)=n(f(n)+f(n-1)).

16*.

Todista:

. [Nämä luvut kasvavat n:n mukana nopeasti taskulaskimen ulottumattomiin.]

17*.

Osoita: jos n on positiivinen kokonaisluku, niin

[kaava puuttuu]

on kokonaisluku.

18*.

Olkoon

. Osoita, että

kaikilla positiivisilla kokonaisluvuilla n.

19* Hanoin torni.

Kolmen pylvään A, B ja C ympärille voidaan pinota erikokoisia renkaita. Alkuasetelmassa pylväässä A on n rengasta, suuruusjärjestyksessä pienin päällimmäisenä, ja ne on siirrettävä torniin C samaan järjestykseen. Vain yhtä rengasta kerrallaan saa siirtää, eikä missään pylväässä saa koskaan olla pienempi rengas suuremman alla. Montako siirtoa vähintään tarvitaan? [Vanhan tarinan mukaan Hanoissa on luostari, jossa munkit jatkuvasti siirtävät 30:tä kultaista rengasta edellä kuvatun menetelmän mukaan; kun työ tulee valmiiksi, tulee maailmanloppu. Nykyään munkit ovat tiettävästi suunnilleen työnsä puolivälissä.]

Matti Lehtinen, Helsingin yliopisto
<Matti.Lehtinen@Helsinki.FI>

Solmu 2/1996-1997
Viimeksi muutettu: 12. toukokuuta 1997 klo 00:41:49