Matematika v šoli XIX. [2013] 045-053 Povzetek V članku opišemo predstavitev matematične indukcije pri dodatnem pouku matematike v 1. letniku srednje šole. Najprej z dijaki ugotav- ljamo razliko med deduktivnim in induktivnim načinom sklepanja, nato z različnimi primeri pokažemo, da z indukcijo ne dobimo vedno pravilne trditve. Po predstavitvi matematične indukcije pokažemo še nekaj primerov njene uporabe pri različnih nalogah: pri seštevanju končnih vsot, pri dokazovanju deljivosti in pri nekaj nalogah z geomet- rijsko vsebino. Na koncu sledi izbor praktičnih nalog za utrjevanje. Ključne besede: matematična indukcija, končne vsote, deljivost, geometrija Matematina indukcija Željka Zori Naravoslovno- matematina fakulteta, Split Mathematical Induction Abstract In the article we describe a presentation of mathematical induction during additional mathematical lessons in the first grade of secon- dary school. First the teacher and pupils jointly determine the dif- ference between the deductive and inductive methods of reasoning, after which we demonstrate with the help of various examples that induction doesn’t always lead to the right solution. After presenting mathematical induction, we demonstrate some additional examples of how to use mathematical induction on various types of exercises, such as addition of final amounts, proofing of divisibility, as well as with some exercises featuring geometrical content. In the end we offer a selection of practical exercises for revising the subject. Key words: mathematical induction, final amounts, divisibility, geometry Matematina indukcija 46 α Uvod Splitsko matematično društvo (SMD) jev šolskem letu 2011/2012 uvedlo projekt »Mladi matematičari SMD-a«, v okviru ka- terega so organizirana sobotna predavanja za učence srednjih in osnovnih šol. Želja društva je bila, da zbere vse učence, ki jih za- nima dodatno delo pri matematiki. Učence smo razvrstili v tri skupine: 5. in 6. razred osnovne šole, 7. in 8. razred osnovne šole ter 1. in 2. letnik srednje šole. Teme, ki smo jih obravnavali, so bile povezane z obravnava- no tematiko pri matematiki v šoli, pogosto pa tudi vsebine iz matematičnih tekmovanj. Kolegica Blaženka Kunac je vodila in koor- dinirala predavanja osnovnih šol, jaz pa sem vodila srednješolce. Ena izmed tem, ki smo jih obravnavali, je bila tudi matematična in- dukcija. V članku opisujem, kako in na kak- šen način smo jo obravnavali. β Predstavitev induktivnega in deduktivnega naina sklepanja V življenju pogosto uporabljamo dva osnovna načina sklepanja oz. razmiš lja nja: deduktivni in induktivni način sklepanja. Deduktivni način sklepanja izhaja iz neke splošne resnice, iz katere se potem razvijejo resnice, ki so vezane na konkreten, posamez- ni primer. Splošni primer: Vsi ljudje so umrljivi. Peter je človek. Peter je umrljiv. Matematični primer: V paralelogramu se diagonali razpolavljata. Pravokotnik je para- lelogram. Diagonali pravokotnika se razpolav- ljata. Za razliko od deduktivnega načina skle- panja, induktivni način sklepanja izhaja iz resničnih, konkretnih primerov, na podlagi katerih skušamo izvesti sklep o resnici, ki vel ja za nek splošni primer. Splošni primer: Ivan je manjši od 2 metrov. Jakob je manjši od 2 metrov. Ante je manjši od 2 metrov. Vsi moški so manjši od 2 metrov. Matematični primer: Število 1 ·2 je sodo število. Število 2 · 2 je sodo število. Število 3 · 2 je sodo število. Na splošno velja, da je število n · 2 sodo število. Zapišite svoj primer deduktivnega in in- duktivnega sklepanja. Poglejmo zgoraj zapisane primere. Pri deduktivnem načinu sklepanja uporabljamo pravila sklepanja, sklepi so pravilni, a nam v večini primerov ne dajo novih informacij. Pri induktivnem načinu pa iz resničnih dejstev ne moremo dobiti resnične, splošne trditve. Vsakdo od nas zagotovo pozna vsaj eno ose- bo moškega spola, ki je višja od dveh metrov. Takšna indukcija se v matematiki imenuje nepopolna indukcija, in ta nima »moči do- kaza«. Kljub tej ugotovitvi nismo zmanjšali vrednosti nepopolne indukcije, ker nam ta pomaga, da dobimo različne hipoteze, med katerimi so ene resnične druge ne. γ Nepopolna indukcija Navajamo še nekaj primerov, ki nam pri- kazujejo, kako lahko z nepopolno indukcijo pridemo do neresničnih zaključkov. Primer 1: f(x) = x 2 – x + 41. Kaj lahko povemo o številu f(x), če je x na- ravno število? Rešitev: Vstavimo po vrstnem redu na- ravna števila v polinom f(x) = x 2 – x + 41. Dobimo: 47 Iz preglednice je razvidno, da so vrednosti tega polinoma za x = 1, ..., 20 vedno prašte- vila. Z nepopolno indukcijo bi lahko sklepali, da to velja za vsako naravno število n, t.j., da je število f(n) = n 2 – n + 41 praštevilo za vsako naravno število n. Ali to res drži? Ne! Ko vstavimo x = 41, dobimo f(41) = 41 2 – 41 + 41 = 41 2 , kar ni praštevilo, saj je deljivo z 41. Primer 2: Dan je polinom f(x) = 991x 2 + 1. Naj bo x naravno število. Ali imajo števila f(x) kakšne zanimive lastnosti? Rešitev: Vstavimo nekaj števil v polinom. Dobimo: x f(x) x f(x) x f(x) x f(x) 1 992 2 3965 3 8920 4 15857 5 24776 6 35677 7 48560 8 63425 Ne opazimo posebnih lastnosti števi- la f(x): niso praštevila, niti niso kvadra- ti naravnih števil. Lahko bi zaključili, da f(n) = 991n 2 + 1 ni popolni kvadrat, ne glede na to, kolikšen je n. Izkazalo se je, da to ni res. Najmanjši n, pri katerem je f(n) = 991n 2 + 1 popolni kvadrat, je število n = 12055735790331359447442538767. Tudi največji matematiki so se na ta način ujeli v zanko nepopolne indukcije. Primer 3: Opazujmo števila oblike f(n) = 2 2 n-1 + 1 za naravna števila n. Rešitev: n f(n) n f(n) n f(n) n f(n) n f(n) 132531 742 5 7565637 Vsa dobljena števila so praštevila. Veliki francoski matematik Pierre de Fermat je po- stavil hipotezo, da so števila take oblike pra- števila. Šele v 18. stoletju je švicarski mate- matik Leonhard Euler dokazal, da to ne drži. Dokazal je, da za n = 6 velja f(6) = 2 2 6-1 + 1 = 225 + 1 = 4294967297 = 641 6700417, to pa je sestavljeno število. δ Matematina indukcija Induktivni način sklepanja je odlično sredstvo za postavljanje novih hipotez, kar je idealno za znanost. Ni nujno, da so take trditve resnične, zato jih je treba preveriti in dokazati. V matematiki pa obstaja metoda, ki nam pomaga dokazati, ali je neka trditev pravilna ali ne. Metodo imenujemo matema- tična indukcija. Princip matematine indukcije Če poljubna matematična trditev, ki je od- visna od naravnega števila n, x f(x) x f(x) x f(x) x f(x) 1 41 6 71 11 151 16 281 2 43 7 83 12 173 17 313 3 47 8 97 13 197 18 347 4 53 9 113 14 223 19 383 5 61 10 131 15 251 20 421 48 - velja za število n 0 N in - če izhajamo iz predpostavke, da ta tr- ditev velja za naravno število k, iz tega sledi, da ta velja tudi za naslednje število k + 1, takrat ta trditev velja za vsako naravno število n ≥ n 0 . ε Uporaba matematine indukcije pri seštevanju konnih vsot Pokažimo na nekaj primerih, kako pri se- števanju končnih vsot uporabljamo princip matematične indukcije. Primer 4: Dokažimo, da za vsako naravno število n velja enakost: 1 + 2 + 3 + ... + n = n (n + 1) . 2 Rešitev: Matematično indukcijo izvedemo v več korakih: 1. Osnova indukcije Preverimo, ali velja enakost za nekaj prvih naravnih števil: Naj bo n = 1. Takrat je 1 = 1 (1 + 1) tj. 1 = 1. 2 Preverimo 1 še za n = 2. Takrat je 1 + 2 = 2 (2 + 1) tj. 3 = 3. 2 2. Predpostavka Predpostavimo, da enakost velja za narav- no število n = k, to je da velja 1 + 2 + 3 + ... + k = k (k + 1) . 2 1 Preverjanje v primeru n = 2 je sicer matematično od- več, je pa včasih koristno za boljše razumevanje prob- lema in za pridobitev ideje, kako preiti iz n na n + 1. 3. Korak indukcije Z uporabo te predpostavke želimo poka- zati, da trditev velja tudi za naravno število n = k + 1, tj. da velja hipoteza (H) 1 + 2 + 3 + ... + k + (k + 1) = (k + 1) (k + 2) . 2 Začnimo z vsoto 1 + 2 + 3 + ... + k + (k + 1) = k (k + 1) + (k + 1) 2 predpostavka = k (k + 1) + 2 (k + 1) 2 = (k + 1)(k + 2) 2 To smo tudi želeli pokazati. 4. Zaključek Z matematično indukcijo smo dokazali, da trditev velja za vsako naravno število . Primer 5: Izračunajte vsoto prvih n lihih naravnih števil. Rešitev: V tem primeru bomo uporabili hevris- tično lastnost nepopolne indukcije. Z njo bomo dobili hipotezo, s katero bomo nato dokazali matematično indukcijo. Na začetku zapišimo splošni zapis n–tega lihega števila. Poglejmo preglednico: n1234 2n + 1 3 5 7 9 2n – 1 1 3 5 7 Vsako liho naravno število je oblike 2n-1 za primerno naravno število n. V nadaljevan- ju nas zanima, kolikšna je vsota: S n = 1 + 3 + 5 + ... + (2n – 1) Matematina indukcija 49 Za n = 1, 2, 3, 4 izračunajmo vsoto: S 1 = 1 S 2 = 1 + 3 = 4 S 3 = 1 + 3 + 5 = 9 S 4 = 1 + 3 + 5 + 7 = 16 Iz teh konkretnih primerov lahko pred- postavimo, da za vsa naravna števila velja enakost 1 + 3 + 5 + ... + (2n – 1) = n 2 . Dokažimo, da je to res. Videli smo, da tr- ditev velja za n = 1 (osnova indukcije je del iskanja hipoteze). Predpostavimo, da trditev velja za n = k, tj. da je : 1 + 3 + 5 + ... + (2k – 1) = k 2 . Preverimo, ali iz predpostavke sledi, da velja trditev tudi za naravno število n = k + 1, tj. da velja hipoteza: (H) 1 + 3 + 5 + ... + (2k – 1) + (2k + 1) = (k + 1) 2 . Po indukcijski predpostavki imamo 1 + 3 + 5 + ... + (2k – 1) + (2k + 1) = k 2 + (2k + 1) predpostavka = (k + 1) 2 Z matematično indukcijo smo pokazali, da trditev velja za vsa naravna števila. Primer 6: Če bi lahko v dokazovanju z matematično indukcijo izpustili preverjanje osnove induk- cije, pokažite, da bi se dalo dokazati, da za vsa- ko naravno število n velja enakost: n = n + 1. Rešitev: Usmerimo se na predpostavko indukcije. Predpostavimo, da trditev velja za neko naravno število n = k, tj. naj bo k = k +1. Preverimo, ali velja trditev za naravno šte- vilo k = k +1, tj. ali velja hipoteza (H) k + 1 = k + 2 S predpostavko imamo k + 1 = (k + 1) + 1 = k + 2 , predpostavka kar smo tudi želeli pokazati. Kaj smo pravzaprav dokazovali? S »skraj- šano« verzijo principa matematične induk- cije smo dokazali, da so vsa naravna števila med seboj enaka, za kar pa vemo, da ni res. Torej lahko zaključimo, da je pomembno preveriti osnovo indukcije. γ Uporaba matematine indukcije pri dokazovanju deljivosti Primer 7: Število 2 deli izraz n 2 – n tj., 2|(n 2 – n) za vsako naravno število n. Dokažite. Rešitev: Za n = 1 trditev velja, ker je 1 2 – 1 = 1 – 1 = 0, kar je deljivo z 2. Zaradi boljšega občutka lahko preveri- mo 2 trditev še za n = 2. Trditev velja, ker je 2 2 – 2 = 4 – 2 = 2, kar je deljivo z 2. Predpostavimo, da trditev velja za neko na- ravno število n = k, torej je k 2 – k deljivo z 2. To dejstvo lahko zapišemo tudi na drug način k 2 – k = 2x, x N. 2 Preverjanje v primeru n = 2 je sicer matematično od- več, je pa včasih koristno za boljše razumevanje prob- lema in za pridobitev ideje, kako preiti iz n na n + 1. 50 Dokazali smo, da je izraz deljiv s 665. S principom matematične indukcije smo do- kazali, da trditev velja za vsa naravna števila. Pokazali smo primere uporabe matema- tične indukcije za dokazovanje enakosti in deljivosti. η Uporaba matematine indukcije v geometriji V naslednjih primerih bomo prikazali, kako matematično indukcijo uporabljamo v geometriji. Primer 9: Dokažite, da n krožnic v splošni legi (no- bena od treh krožnic ne gre skozi isto toč- ko in vsaki dve se sekata) deli ravnino na n 2 – n + 2 področij. Rešitev: Naj bo P(n) = n 2 – n + 2 število področij, na katere n krožnic v splošni legi deli ravnino. Za n = 1 imamo P(1) = 2. Ena krožnica deli ravnino na dve področji, s čimer smo dokazali osnovo indukcije. Poglejmo še za n = 2. Dve krožnici delita ravnino na štiri področja (slika 1 in slika 2). Dobimo P(2) = 4. [Slika 1] n = 1 Preverimo, ali trditev velja tudi za narav- no število n = k + 1 tj. da velja hipoteza (H) 2|((k + 1) 2 – (k + 1)). Poglejmo sedaj (k + 1) 2 – (k + 1) = k 2 + 2k + 1 – k –1 = ((k 2 – k)+2k = 2x + 2k predpostavka = 2(x + k) Pokazali smo, da je izraz deljiv z 2, kar je bil tudi naš namen. S principom matematič- ne indukcije smo dokazali, da trditev velja za vsa naravna števila. Primer 8: Za vsako naravno število n je število 3 6n – 2 6n deljivo z 665. Dokažite. Rešitev: Za n = 1 trditev velja. To pomeni, da je 3 6 – 2 6 = 729 – 64 = 665, deljivo s 665. Predpostavimo, da je trditev resnična za neko naravno število n = k, torej, da je 3 6k – 2 6k deljivo s 665. T o lahko zapišemo tudi drugače: 3 6k – 2 6k = 665x, x N. Preverimo še, da trditev velja tudi za na- ravno število n = k + 1 tj. da velja hipoteza (H) 665|(3 6(k+1) – 2 6(k+1) ). Poglejmo sedaj, predpostavka 3 6(k+1) – 2 6(k+1) = 3 6k+6 – 2 6k+6 = 3 6 3 6k – 2 6k+6 = 729(665x+2 6k )-64 2 6k = 665 729x + 729 2 6k – 64 2 6k = 665 729x + 665 2 6k = 665 (729x + 2 6k ) Matematina indukcija 51 [Slika 2] n = 2 Predpostavimo, da trditev velja za neko na- ravno število n = k , tj. da velja P(k) = k 2 – k + 2. Preveriti moramo še, če trditev velja tudi za naravno število n = k + 1, tj.: (H) P(k + 1) = (k + 1) 2 – (k + 1) + 2 = k 2 + k + 2. Kaj se zgodi, če dodamo (k + 1) - to krož- nico? Ta krožnica seka obstoječe krožnice v 2k točkah. Teh 2k točk razdeli (k + 1) krožnico na 2k lokov. Vsak lok deli obstoječe območje, v ka- terem leži, na dva dela. Z dodajanjem nove krožnice smo tako dobili novih 2k delov. [Slika 3] n = 3 Torej imamo P(k+1) = P(k) + 2k = k 2 – k + 2 + 2k = k 2 + k + 2 Potrdili smo, da trditev velja za vsako na- ravno število n. Primer 10: Danih je n kvadratov. Dokažimo, da jih lahko razrežemo na dele, s katerimi sestavi- mo nov kvadrat. Rešitev: Dovolj je, če pokažemo, da iz dveh kvad- ratov lahko sestavimo nov kvadrat. Pri tej nalogi začnemo z n = 2. Na sliki 4 je pokazano, kako s pomočjo Pitagorovega iz- reka iz dveh kvadratov sestavimo nov kvad- rat. Če smo na n-tem koraku iz n + 1 kvad- ratov sestavili nov kvadrat, v (n + 1) koraku nov sestavljen kvadrat na enak način kot v primeru n = 2 dopolnimo z (n + 2) kvadra- tom do naslednjega kvadrata. [Slika 4] Iz dveh kvadratov nov kvadrat 52 ϕ Zakljuek Za konec povejmo še, kako je množica naravnih števil definirana s Peanovimi aksi- omi (1889): - 1 je naravno število, tj. 1 N. - Vsako naravno število n ima natančno enega naslednika n + v množici naravnih števil. - Vedno velja n + ≠ 1, tj. 1 ni naslednik no- benega naravnega števila. - Iz n + = m + sledi n = m, tj. če sta nasledni- ka enaka, sta tudi števili enaki. Aksiom indukcije. Vsaka množica narav- nih števil, v kateri je 1 in ki z vsakim številom n vsebuje tudi n + ,vsebuje vsa naravna števil. Z aksiomi lahko dokažemo vsa tista dej- stva in lastnosti, ki jih imajo množice na- ravnih števil. Na matematičnih tekmovanjih (na Hrvaškem) se pogosto pojavljajo naloge, ki opisujejo neko lastnost, ki je odvisna (na nek način) od naravnih števil, zato je dobro in koristno pri dodatnem pouku matematike izvesti princip matematične indukcije. λ Naloge za utrjevanje 1. Dokažite, da za vsako naravno število n velja: a. 1 2 + 2 2 + 3 2 + ... + n 2 = b. 1 2 + 3 2 + 5 2 + ... + (2n–1) 2 = 2. Postavite hipotezo in dokažite: a. b. 3. Ali za vsako naravno število n velja ena- kost: a. 1 4 + 2 7 + ... + n (3n + 1) = n (n + 1) 2 b. c. d. 4. Dokažite, da za vsako naravno številon- velja: a. 48|(5n + 2) 2 – (2 – n) 2 b. 19| 7n + 2 + 8 2n + 1 c. 225|16 n – 15n – 1 d. 17|2 5n + 3 + 5 n 3 n + 2 5. Dokažite, da je za vsako naravno število n, število celo število. 6. Naj bo na ravnini n premic, od katerih niti dve nista vzporedni in niti tri ne gredo skozi isto točko. Dokažite, da te delijo ravnino na delov. 7. Naj bo q ≠ 1. Dokažite, da je 8. Pokvarjena dxd šahovska plošča je dxd šahovska plošča z enim skritim poljem (poljubnim). Dokažite, da se vsaka po- kvarjena šahovska 2 n x 2 n , n N plošča lahko prekrije z triominimi, to je figura- mi s tremi polji v obliki črke L. (Držav- no tekmovanje iz predmeta matematike Republika Hrvaška, 1992.) Matematina indukcija 53 δ Viri in literatura: 1. B. Dakić, N. Elezović, Matematika 4, 1. dio, udžbenik za 4 razred gimnazije, Element, Zagreb, 2009. 2. B. Pavković, B. Dakić, Ž. Hanjš, P. Mladinić, Male teme iz matematike, Element, Zagreb, 1994. 3. Luka Čeliković, Princip matematičke indukcije, Pita- gorinimaterijali za mlade matematičare 24, Beli Ma- nastir, 1990. 4. S. Antoliš, A. Copić, Matematika 4, 1. dio, udžbenik za 4 razred gimnazije, Školska knjiga, Zagreb, 2005. 5. D. Blanuša, Viša matematika, 1 dio, Tehnička knjiga, Zagreb, 1963.