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

Retki tehtiin Solmussa 2. Nyt on vielä tehtävä

C Jälkikatsaus

eli tuolloin selityksettä tai ratkaisutta jääneiden kohtien tai tehtävien selittäminen.

3

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

[kaava]

Aloitetaan induktio arvosta n = 0. Selvästikin 1 + 0·x = 1 = (1 + x)0. Oletetaan sitten, että k >= 0 ja että 1 + kx <= (1 + x)^k. Koska 1 + x >= 0 ja x^2 >= 0, on myös

[kaava]

Induktioaskel on otettu ja väite todistettu.

5.

Osoita, että

[kaava]

Vihjeen mukaan osoitetaan ensin, että

[kaava]

Olkoon n >= 1 ja 0 <= k < n. Silloin todellakin

[kaava]

Binomikaavan induktiotodistuksen aluksi havaitaan, että (a + b)^1 = a + b = (1 yli 0)a^0 b^1 + (1 yli 1)a^1 b^0. Otetaan sitten induktioaskel, jonka pohjaksi oletetaan, että n >= 1 ja että

[kaava]

Silloin

[kaava]

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?

Merkitään n:n suoran synnyttämien jako-osien määrää f(n):llä. Jos suoria on n + 1, ja näistä yksi, suora l, poistetaan, jako-osia on siis f(n) kappaletta. Suora l leikkaa n muuta suoraa, ja se kulkee n + 1:n jako-osan läpi jakaen kunkin näistä kahteen osaan. (Tämä perustuu siihen, että jako-osat ovat kuperia monikulmioita; syntyvät uudet jako-osat ovat edelleen tällaisia.) Siten f(n + 1) = f(n) + n + 1. Väitetään, että f(n) = n(n + 1)/2 + 1. Tämä on totta, kun n = 0 (f(0) = 1). Jos f(n) = n(n+1)/2 + 1, niin f(n + 1) = f(n) + n + 1 = n(n + 1)/2 + n + 2 = (n + 1)(n/2 + 1) + 1 = (n + 1)(n + 2)/2 + 1.

8.

Todista: jokainen kokonaisluku n>1 on joko alkuluku tai alkulukujen tulo.

Todistus. Kokonaisluku 2 on alkuluku. Oletetaan, että jokainen n <= k on joko alkuluku tai alkulukujen tulo. Luku k + 1 on joko alkuluku tai yhdistetty luku. Jos se on yhdistetty luku, se on tulo k = ab, missä a ja b ovat >= 2 ja siis <= (k + 1)/2 < (k + k)/2 = k. Induktio-oletuksen mukaan a ja b ovat alkulukuja tai alkulukujen tuloja. Siis k + 1 on alkuluku tai alkulukujen tulo.

9.

Olkoon n > 1 ja M positiivinen kokonaisluku. Todista, että on olemassa yksikäsitteisesti määrätyt kokonaisluvut [kaava] ja a0, a1, ..., am siten, että am > 0, [kaava], kun j=0, 1, ..., m, ja

M = amnm + am-1nm-1 + ... + a0.

On olemassa m = m(M) siten, että n^m < M < n^(m+1). Suoritetaan induktio m:n suhteen. Jos m = 0, voidaan valita a0 = M, ja väite pätee. Oletetaan, että väite pätee kaikille M, joille m(M) <= k. Olkoon sitten M luku, jolle m(M) = k + 1. Siis n^(k+1) <= M < n^(k+2). Olkoon vielä p < n suurin kokonaisluku, jolla pn^(k+1) <= M. Silloin joko M = pnk+1 tai 0 < M - pnk+1 < nk+1. Edellisessä tapauksessa M:llä on vaaditunlainen esitys, ja jälkimmäisessä tapauksessa m(M - pn^(k+1)) <= k, joten M - pnk+1:llä on haluttua muotoa oleva esitys n:n korkeintaan astetta k olevana polynomina. Kun valitaan ak+1 = p, saadaan M:lle esitys n:n astetta k + 1 olevana polynomina.

11.

Määritä x2:n kerroin polynomissa (1 + x + x2 + ... + xn)n.

Olkoon (1 + x + x2 + ... + xn)n = 1 + anx + bnx2 + ... + xn2, n >= 2. Silloin

[kaava]

Siis an+1 = an + 1 ja bn+1 = an + bn + 1. Koska (1 + x + x2)2=1 + x2 + x4 + 2x + 2x2 + 2x3, a2 = 2 ja b2 = 3. Tästä seuraa, että an = n ja bn+1 = bn + n + 1 eli bn on n:n ensimmäisen positiivisen kokonaisluvun summa, siis bn = n(n + 1)/2.

12.

Montako kaksialkioista osajoukkoa on n-alkioisella joukolla?

Olkoon kysytty lukumäärä f(n). Silloin f(1) = 0 ja f(2) = 1. Joukolla {a1, a2, ..., an, b} on f(n) kaksialkioista osajoukkoa {ai, aj} ja n kaksialkioista osajoukkoa {ai, b}. Siis f(n + 1) = f(n) + n. Väitetään, että f(n) = n(n - 1)/2. Tämä on totta, kun n = 1 ja n = 2. Jos f(k) = k(k - 1)/2, niin f(k + 1) = k(k - 1)/2 + k = k(k + 1)/2, niin kuin pitääkin.

13.

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

Monikulmion kärkiä yhdistäviä janoja on yhtä monta kuin n-alkioisella joukolla on 2-alkioisia osajoukkoja, eli edellisen mukaan n(n - 1)/2 kappaletta. Näistä janoista n kappaletta, monikulmion sivut siis, ei ole lävistäjiä, joten lävistäjiä on n(n - 1)/2 - n = n(n - 3)/2 kappaletta.

14.

Monellako eri tavalla n lukua voidaan kirjoittaa jonoon?

Todistetaan induktiolla, että kysytty lukumäärä on n! = 1·2···n. Näin on varmasti, kun n = 1. Oletamme, että k lukua a1, a2, ..., ak voidaan kirjoittaa jonoon k! eri tavalla. Jokainen näistä järjestyksistä tuottaa k + 1 eri järjestystä luvuille a1, a2, ..., ak+1, koska ak+1 voidaan sijoittaa jo olemassa olevaan k:n luvun jonoon ensimmäiseksi tai minkä hyvänsä luvun aj, j = 1, 2, ..., k, jälkeen.

15.

Olkoon f(n) luku, joka ilmoittaa, kuinka monella eri tavalla n lukua a1, a2, ..., an voidaan kirjoittaa jonoon niin, että jonon k:s luku on aina eri kuin ak, k = 1, 2, ..., n. Osoita, että f(n + 1) = n(f(n) + f(n - 1)).

Luvut a1, a2, ..., an ja an+1 voidaan sekoittaa tehtävässä ilmoitetuin ehdoin kahdella eri menetelmällä. Voidaan sekoittaa ensin n ensimmäistä lukua niin, että k:s luku on aina eri kuin ak, ja vaihtaa sitten an+1 ja jokin ak. Tällaisia sekoituksia on yhteensä nf(n) kappaletta; an+1 ei koskaan ole k:s luku. Toinen tapa on vaihtaa ensin ak ja an+1 ja sekoittaa sitten loput n - 1 lukua. Tällaisia sekoituksia on kaikkiaan nf(n - 1) kappaletta. Kaikki mahdolliset sekoitukset on tässä tullut otetuksi huomioon, sillä joka tapauksessa n + 1:lle paikalle tulee joko se luku, jonka an+1 korvaa (jälkimmäinen tapaus) tai jokin muu luku (edellinen tapaus). Siis f(n + 1) = n(f(n) + f(n - 1)).

16.

Todista: 2!·4!···(2n)! > ((n + 1)!)n - 1.

Koska 2! = (1 + 1)!1, induktio pääsee alkuun. Oletetaan, että 2!·4!···(2k)!>((k + 1)!)n - 1. Silloin 2!·4!···(2k)!·(2(k + 1))! + 1 > ((k+1)!)k(2k+2)! = ((k + 1)!)k+1·(k + 2)(k + 3)···(2k + 2) > ((k + 1)!)k+1(k+2)k+1 = ((k+2)!)k+1.

17.

Osoita: jos n on positiivinen kokonaisluku, niin f(n) = (n5)/5 + (n4)/2 + (n3)/3 - n/30 on kokonaisluku.

Selvästi f(0) = 0 ja f(1) = 1. Oletetaan, että f(k) on kokonaisluku. Silloin f(k + 1) = (k + 1)5/5 + (k + 1)4/2 + (k + 1)3/3 - (k + 1)/30 = f(k) + f(1) + (5k4 + 10k3 + 10k2 + 5k)/5 + (4k3 + 6k2 + 4k)/2 + (3k2 + 3k)/3; siis f(k + 1) on kokonaisluku.

18.

Olkoon [kaava]. Osoita, että

[kaava
   ]

kaikilla positiivisilla kokonaisluvuilla n.

Selvästi sin x>0 ja |cos y| <= 1 kaikilla y. Tehtävän väite on tosi, kun n = 1. Oletetaan, että |sin(kx)| <= k sin x. Silloin

[kaava]

19.

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?

Merkitään renkaiden siirtämiseen tarvittavien siirtojen vähimmäismäärää f(n):llä. Silloin f(1) = 1. Koska alinta rengasta ei voi liikuttaa, ennen kuin kaikki sen päällä olevat n - 1 rengasta on siirretty, alin rengas voidaan siirtää paikalleen pylvääseen C aikaisintaan silloin, kun muut renkaat on siirretty pylvääseen B. Tähän tarvitaan vähintään f(n - 1) siirtoa. Jotta muut renkaat tämän jälkeen saataisiin siirretyiksi pylvääseen C, tarvitaan taas ainakin f(n - 1) siirtoa. Siis f(n) >= 2f(n - 1) + 1. Kuvattu menetelmä mahdollistaa siirtojen tekemisen niin, että f(n) = 2f(n - 1) + 1. Osoitetaan vielä, että f(n) = 2n - 1. Kaava on tosi, kun n = 1. Oletetaan, että f(n - 1) = 2n-1 - 1. Silloin f(n) = 2f(n - 1) + 1 = 2n - 2 + 1 = 2n - 1.

Toinen retki. Nuo mainiot binomikertoimet.

A Kertoimet ja kaava

1.

Binomikertoimet liitetään tavallisesti ranskalaiseen Blaise Pascaliin (1623-62). "Pascalin kolmio"
1
11
121
1331
14641
15101051
1615201561
. . .

oli tuttu jo keskiajan kiinalaisille samoin kuin muutamille Pascalin eurooppalaisille edeltäjille.

Binomikertoimien (n yli k) = n!/((n-k)!k!), (n yli 0) = (n yli n) = 1 eli Pascalin kolmion lukujen perusominaisuus on kolmiosta näkyvä yhteenlaskukaava
(1) [kaava]

Lukujen (n yli k) määritelmästä seuraavat heti kaavat
(2) [kaava]

ja
(3) [kaava]

Induktiolla on helppo todistaa (ks. Retki 1) oikeaksi binomikaava
(4) (a + b)^n = summa(k = 0 ... n) (n yli k) a^k b^(n-k)

Binomikertoimien merkitys todennäköisyyslaskennassa ja kombinaatio-opissa perustuu siihen, että sellaisella joukolla, jolla on tasan n alkiota, on (n yli k) kappaletta k-alkioisia osajoukkoja. Tätä lukumäärää oli aikaisemmin tapana kutsua n:n alkion k:ttain otettujen kombinaatioiden lukumääräksi. - Joskus on tarkoituksenmukaista määritellä, että (n yli k) = 0, kun k < 0 tai n < k.

2*.

Todista oikeiksi yhteenlaskukaavat

[kaava]

3.

Nämä yhteenlaskukaavat luovat näppärän keinon laskea peräkkäisten kokonaislukujen potenssien summia. Yksinkertaisin tapaus perustuu havaintoon k = (k yli 1). Tämän nojalla

[kaava]

Laskeaksemme summan 12+22+...+n2 huomaamme ensin, että kun n >= 2, niin 2(n yli 2) = n(n - 1) = n^2 - n. Niinpä

[kaava]

4*.

Osoita, että 12+22+...+n2 voidaan laskea myös käyttämällä hyväksi kaavaa (k+1)3 - k3 = 3k2 + 3k + 1. Keksitkö vielä muita tapoja summan laskemiseksi?

5*.

Laske

[kaava]

6*.

Tällaisten summien laskeminen oli tärkeää integraalilaskennan syntyvaiheiden aikaan 1600-luvulla. Käyrän y = xp, 0 <= x <= 1, kuvaajan alle jäävä pinta-ala eli

[kaava]

on suurilla n:n arvoilla suunnilleen sama kuin

[kaava]

Määritä edellisten tulosten perusteella

[kaava]

7.

Binomikaavan perusteella on selvää, että

[kaava]

Samalla periaatteella saadaan monia muitakin kaavoja, kuten esimerkiksi

[kaava]

Kaavan (2) avulla voidaan laskea
(5) summa(k = 1 ... n) k(n yli k) = ... = n2^(n-1)

Vastaavalla tavalla saadaan
(6) [kaava]

8.

Kaavojen (5) ja (6) tapaiset kaavat voidaan johtaa aivan toisenlaisella menetelmällä, käyttämällä binomikaavaa ja differentiaali- ja integraalilaskentaa. Derivoidaan kaava

[kaava]

jolloin saadaan

[kaava]

asetetaan x = 1, ja on saatu kaava (5).

9*.

Johda kaava (6) integroimalla binomikaava.

10*.

Määritä

[kaava]

11.

Eräs merkitys binomikertoimille (n yli k) samoin kuin koko joukko niiden ominaisuuksia voidaan johtaa seuraavan havainnon nojalla. Tarkastellaan tason niitä koordinaattipisteitä, joiden koordinaatit ovat ei-negatiivisia kokonaislukuja (ruutupaperi on hyvä malli), ja pisteestä (0,0) alkavia reittejä, jotka koostuvat vain muotoa (p,q) -> (p+1,q) ja (p,q) -> (p,q+1) olevista askeleista. Pisteeseen (n,k) päättyvien eri reittien lukumäärä on (n+k yli k) = (n+k yli n). Että näin on, voidaan todistaa induktiolla luvun n + k suhteen. Väite on varmasti tosi, kun n + k = 1: selvästikin on vain (1 yli 0) reittiä pisteisiin (1,0) ja (0,1). Oletetaan sitten, että kaava pitää paikkansa arvolla n + k - 1 ja jaetaan pisteeseen (n,k) johtavat reitit kahteen luokkaan, pisteen (n-1,k) kautta kulkeviin ja pisteen (n,k-1) kautta kulkeviin. Jos n = 0 tai k = 0, niin toinen näistä luokista on tyhjä; muissa tapauksissa näissä luokissa olevien reittien määrä on induktio-oletuksen nojalla (n+k-1 yli k) ja (n+k-1 yli k-1). Todistuksen viimeistelee peruskaava (1).

12*.

Osoita, että

[kaava]

13.

Toinen menetelmä binomikertoimia koskevien kaavojen löytämiseksi on osajoukkojen lukumäärän laskeminen. Oletetaan, että A on joukko, jossa on n + k alkiota. Olkoon vielä A = B yhdiste C, missä B on n-alkioinen ja C k-alkioinen (niin että B leikkaus C on tyhjä). Nyt jokainen j-alkioinen A:n osajoukko D, (j <= k) voidaan jakaa osiksi D = (B leikkaus D) yhdiste (C leikkaus D). Osassa (B leikkaus D) on, sanokaamme, r alkiota ja osassa (C leikkaus D) j - r alkiota. Toisaalta jokainen yhdiste B:n r-alkioisesta osajoukosta ja C:n j - r-alkioisesta osajoukosta on A:n j-alkioinen osajoukko. Kun r saa kaikki arvot 0:sta j:hin, tullaan tällä tavalla läpikäyneeksi kaikki A:n j-alkioiset osajoukot. Osajoukkojen lukumääräksi tulee

[kaava]

Toisaalta A:n j-alkioisten osajoukkojen määrä on (n+k yli j). Olemme saaneet kaavan
(8) [kaava]

14.

Binomikaavalla on paljon sovelluksia matemaattisessa analyysissä. Käytämme sitä nyt vakuuttautuaksemme "tunnetusta tosiseikasta", jonka mukaan aina kun a > 1 ja k on kiinteä positiivinen kokonaisluku, niin eksponenttifunktio an lopulta päihittää potenssifunktion nk. Asetetaan a = 1 + b, b > 0 ja valitaan n > 2k + 1 eli n - k > n/2. Verrataan nyt an:ää vain yhteen binomikaavan summan yhteenlaskettavaan:

[kaava]

Kun nyt valitaan vielä n suuremmaksi kuin (2k(k + 1)!)/(bk + 1), niin saadaan an>nk.

15.

Mitä tapahtuu, jos eksponentti kaavassa (4) ei ole positiivinen kokonaisluku? Kokeillaan tapausta n = 1/2. Jotta olisi

[kaava]

olisi oltava

[kaava]

Yhtälö toteutuu varmasti, jos potenssien xk kertoimet ovat samat yhtälön molemmin puolin. Kokeillaan siis valintoja A2 = 1 eli (voidaan vielä valita) A = 1, 2AB = 1 eli B = 1/2, 0 = 2AC + B2 = 2C + 1/4 eli C = -1/8, 0 = AD + BC = D - 1/16 eli D = 1/16, 0 = 2AE + 2BD + C2 = 2E + 1/16 + 1/64 eli E = 5/128 jne.

16*.

Miten alkaisivat vastaavat kehitelmät funktioiden (1 + x)2/3 ja (1 + x)-2 tapauksissa?

17.

Kaava (4) pitää muodollisesti paikkansa mille hyvänsä eksponentille:

[kaava]

Tietysti meidän tulisi varmistua, että yhtälön vasen puoli on kunnolla määritelty ja että oikealla puolella esiintyvän päättymättömän sarjan olemus tulee oikein ymmärrettyä. On mahdollista osoittaa, että kaava pätee, kun |x| < 1. Mutta se on jo toisen retken aihe.

***

B Vielä muutama kerroin

18*.

Voitko johtaa kaavan (8) käyttämällä origosta lähtevien reittien lukumääriä?

19*.

Laske

[kaava]

20*.

Laske

[kaava]

21*.

Laske

[kaava]

22*.

Laske

[kaava]

23*.

Laske

[kaava]

24*.

Laske

[kaava]

25*.

Minkälainen olisi binomikaavan vastine tapauksessa (x + y + z)n?

Matti Lehtinen


Solmu 1/1997-1998
Viimeksi muutettu: 2.6.1998 klo 15.35.19