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 [kaava puuttuu], jos seuraavat kaksi ehtoa ovat voimassa:

  1. P(a) on tosi.
  2. Kaikilla [kaava puuttuu] 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 [kaava puuttuu], 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 [kaava puuttuu]: 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 [kaava puuttuu] pätee

[kaava puuttuu]

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

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

[kaava puuttuu]

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

[kaava puuttuu]

Mutta tällöin

[kaava puuttuu]

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

[kaava puuttuu]

4 Induktiivinen määrittely.

Induktioperiaate tekee mahdolliseksi määritellä täsmällisesti kokonaislukujen funktioita. Esimerkiksi merkinnän [kaava puuttuu], 'kerrotaan a n kertaa itsellään", täsmällisempi määrittely olisi Samoin n-kertoman n! määritelmä olisi Induktiivisesti voimme määritellä myös summamerkin: jos [kaava puuttuu], [kaava puuttuu], [kaava puuttuu], ..., on lukujono, niin

[kaava puuttuu]

5* Binomikaava.

Merkitään

[kaava puuttuu]

Osoita, että

[kaava puuttuu]

Vihje: Luvut [kaava puuttuu] löytyvät tunnetusti "Pascalin kolmion"

[kaava puuttuu]

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

[kaava puuttuu]

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 [kaava puuttuu] on tietysti tasan yksi epätyhjä osajoukko, se itse. Kaksialkioisella joukolla [kaava puuttuu] on kolme osajoukkoa, [kaava puuttuu], [kaava puuttuu] ja [kaava puuttuu]. Kolmialkioisella joukolla [kaava puuttuu] on kolme yksialkioista osajoukkoa, kaksialkioiset osajoukot [kaava puuttuu], [kaava puuttuu] ja [kaava puuttuu] sekä kolmialkioinen osajoukko [kaava puuttuu], yhteensä seitsemän joukkoa. Muotoillaan väite P(n):

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

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ä [kaava puuttuu], 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 [kaava puuttuu] ja [kaava puuttuu], [kaava puuttuu], ..., [kaava puuttuu] siten, että [kaava puuttuu], [kaava puuttuu], kun j=0, 1, ..., m, ja

[kaava puuttuu]

10.

Joskus induktiotodistus vaatii onnistuakseen, että todistetaan tavallaan enemmän, kuin oikeastaan vaaditaankaan. Unohdetaan kohta 5 ja väitetään, että [kaava puuttuu]:n kerroin polynomissa [kaava puuttuu] on aina [kaava puuttuu]. 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ä [kaava puuttuu] on. Mutta katsotaan vahvempaa väitettä Q(n), jonka mukaan [kaava puuttuu]:ssä potenssien [kaava puuttuu], [kaava puuttuu] ja [kaava puuttuu] kertoimet ovat 1, n ja [kaava puuttuu]. Se on tosi, kun n=2. Jos Q(k) on tosi, niin yhtälöissä (1) voidaan kirjoittaa [kaava puuttuu] ja [kaava puuttuu]. Yhtälö (1) kertoo silloin heti, että Q(k+1) on tosi.

11*.

Määritä [kaava puuttuu]:n kerroin polynomissa [kaava puuttuu].

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 [kaava puuttuu], [kaava puuttuu], ..., [kaava puuttuu] voidaan kirjoittaa jonoon niin, että jonon k:s luku on aina eri kuin [kaava puuttuu], k=1, 2, ..., n. Osoita, että f(n+1)=n(f(n)+f(n-1)).

16*.

Todista:

[kaava puuttuu]

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

17*.

Osoita: jos n on positiivinen kokonaisluku, niin

[kaava puuttuu]

on kokonaisluku.

18*.

Olkoon [kaava puuttuu]. Osoita, että

[kaava puuttuu]

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