Turistina matematiikassa

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

Aloitetaan induktio arvosta n = 0. Selvästikin 1 + 0·x = 1 = (1 + x)⁰. Oletetaan sitten, että ja että . Koska ja , on myös

Induktioaskel on otettu ja väite todistettu.

5.

Osoita, että

Vihjeen mukaan osoitetaan ensin, että

Olkoon ja . Silloin todellakin

Binomikaavan induktiotodistuksen aluksi havaitaan, että . Otetaan sitten induktioaskel, jonka pohjaksi oletetaan, että ja että

Silloin

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 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 ja siis . 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 ja a₀, a₁, ..., a_m siten, että a_m > 0, , kun j=0, 1, ..., m, ja

M = a_mn^m + a_m-1n^m-1 + ... + a₀.

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

11.

Määritä x²:n kerroin polynomissa (1 + x + x² + ... + xⁿ)ⁿ.

Olkoon (1 + x + x² + ... + xⁿ)ⁿ = 1 + a_nx + b_nx² + ... + xⁿ², . Silloin

Siis a_n+1 = a_n + 1 ja b_n+1 = a_n + b_n + 1. Koska (1 + x + x²)²=1 + x² + x⁴ + 2x + 2x² + 2x³, a₂ = 2 ja b₂ = 3. Tästä seuraa, että a_n = n ja b_n+1 = b_n + n + 1 eli b_n on n:n ensimmäisen positiivisen kokonaisluvun summa, siis b_n = 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 {a₁, a₂, ..., a_n, b} on f(n) kaksialkioista osajoukkoa {a_i, a_j} ja n kaksialkioista osajoukkoa {a_i, 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 a₁, a₂, ..., a_k voidaan kirjoittaa jonoon k! eri tavalla. Jokainen näistä järjestyksistä tuottaa k + 1 eri järjestystä luvuille a₁, a₂, ..., a_k+1, koska a_k+1 voidaan sijoittaa jo olemassa olevaan k:n luvun jonoon ensimmäiseksi tai minkä hyvänsä luvun a_j, j = 1, 2, ..., k, jälkeen.

15.

Olkoon f(n) luku, joka ilmoittaa, kuinka monella eri tavalla n lukua a₁, a₂, ..., a_n voidaan kirjoittaa jonoon niin, että jonon k:s luku on aina eri kuin a_k, k = 1, 2, ..., n. Osoita, että f(n + 1) = n(f(n) + f(n - 1)).

Luvut a₁, a₂, ..., a_n ja a_n+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 a_k, ja vaihtaa sitten a_n+1 ja jokin a_k. Tällaisia sekoituksia on yhteensä nf(n) kappaletta; a_n+1 ei koskaan ole k:s luku. Toinen tapa on vaihtaa ensin a_k ja a_n+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 a_n+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)!)ⁿ - 1.

Koska 2! = (1 + 1)!¹, induktio pääsee alkuun. Oletetaan, että 2!·4!···(2k)!>((k + 1)!)ⁿ - 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) = (n⁵)/5 + (n⁴)/2 + (n³)/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 + (k + 1)⁴/2 + (k + 1)³/3 - (k + 1)/30 = f(k) + f(1) + (5k⁴ + 10k³ + 10k² + 5k)/5 + (4k³ + 6k² + 4k)/2 + (3k² + 3k)/3; siis f(k + 1) on kokonaisluku.

18.

Olkoon . Osoita, että

Selvästi sin x>0 ja kaikilla y. Tehtävän väite on tosi, kun n = 1. Oletetaan, että . Silloin

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 . Kuvattu menetelmä mahdollistaa siirtojen tekemisen niin, että f(n) = 2f(n - 1) + 1. Osoitetaan vielä, että f(n) = 2ⁿ - 1. Kaava on tosi, kun n = 1. Oletetaan, että f(n - 1) = 2^n-1 - 1. Silloin f(n) = 2f(n - 1) + 1 = 2ⁿ - 2 + 1 = 2ⁿ - 1.

Toinen retki. Nuo mainiot binomikertoimet.

A Kertoimet ja kaava

1.

Binomikertoimet liitetään tavallisesti ranskalaiseen Blaise Pascaliin (1623-62). "Pascalin kolmio"

						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1
1		6		15		20		15		6		1
. . .

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

Binomikertoimien , eli Pascalin kolmion lukujen perusominaisuus on kolmiosta näkyvä yhteenlaskukaava

(1)

Lukujen määritelmästä seuraavat heti kaavat

(2)

ja

(3)

Induktiolla on helppo todistaa (ks. Retki 1) oikeaksi binomikaava

(4)

Binomikertoimien merkitys todennäköisyyslaskennassa ja kombinaatio-opissa perustuu siihen, että sellaisella joukolla, jolla on tasan n alkiota, on 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ä , kun k < 0 tai n < k.

2*.

Todista oikeiksi yhteenlaskukaavat

3.

Nämä yhteenlaskukaavat luovat näppärän keinon laskea peräkkäisten kokonaislukujen potenssien summia. Yksinkertaisin tapaus perustuu havaintoon . Tämän nojalla

Laskeaksemme summan 1²+2²+...+n² huomaamme ensin, että kun , niin . Niinpä

4*.

5*.

Laske

6*.

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

on suurilla n:n arvoilla suunnilleen sama kuin

Määritä edellisten tulosten perusteella

7.

Binomikaavan perusteella on selvää, että

Samalla periaatteella saadaan monia muitakin kaavoja, kuten esimerkiksi

Kaavan (2) avulla voidaan laskea

(5)

Vastaavalla tavalla saadaan

(6)

8.

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

jolloin saadaan

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

9*.

Johda kaava (6) integroimalla binomikaava.

10*.

Määritä

11.

Eräs merkitys binomikertoimille 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 . Että näin on, voidaan todistaa induktiolla luvun n + k suhteen. Väite on varmasti tosi, kun n + k = 1: selvästikin on vain 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 ja . Todistuksen viimeistelee peruskaava (1).

12*.

Osoita, että

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ä , missä B on n-alkioinen ja C k-alkioinen (niin että on tyhjä). Nyt jokainen j-alkioinen , () voidaan jakaa osiksi . Osassa on, sanokaamme, r alkiota ja osassa 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

Toisaalta A:n j-alkioisten osajoukkojen määrä on . Olemme saaneet kaavan

(8)

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 aⁿ lopulta päihittää potenssifunktion n^k. Asetetaan a = 1 + b, b > 0 ja valitaan n > 2k + 1 eli n - k > n/2. Verrataan nyt aⁿ:ää vain yhteen binomikaavan summan yhteenlaskettavaan:

Kun nyt valitaan vielä n suuremmaksi kuin (2^k(k + 1)!)/(b^k + 1), niin saadaan aⁿ>n^k.

15.

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

olisi oltava

Yhtälö toteutuu varmasti, jos potenssien x^k kertoimet ovat samat yhtälön molemmin puolin. Kokeillaan siis valintoja A² = 1 eli (voidaan vielä valita) A = 1, 2AB = 1 eli B = 1/2, 0 = 2AC + B² = 2C + 1/4 eli C = -1/8, 0 = AD + BC = D - 1/16 eli D = 1/16, 0 = 2AE + 2BD + C² = 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:

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

20*.

Laske

21*.

Laske

22*.

Laske

23*.

Laske

24*.

Laske

25*.

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

Matti Lehtinen