Bibliografski opis: Badanin AS, Sizova M. Yu. Uporaba metode matematične indukcije pri reševanju problemov o deljivosti naravnih števil // Mladi znanstvenik. - 2015. - Št. 2. — S. 84-86..04.2019).

Na matematičnih olimpijadah se pogosto srečujemo s precej težkimi težavami pri dokazovanju deljivosti naravnih števil. Šolarji se soočajo s problemom: kako najti univerzalno matematično metodo, ki omogoča reševanje takšnih problemov?

Izkazalo se je, da je večino problemov deljivosti mogoče rešiti z matematično indukcijo, vendar je v šolskih učbenikih tej metodi posvečeno zelo malo pozornosti, največkrat je podan kratek teoretični opis in analiziranih več problemov.

Metodo matematične indukcije najdemo v teoriji števil. Na zori teorije števil so matematiki induktivno odkrili mnoga dejstva: L. Euler in K. Gauss sta včasih razmišljala na tisoče primerov, preden sta opazila številčni vzorec in vanj verjela. A hkrati so razumeli, kako zavajajoče so lahko hipoteze, če opravijo »končni« test. Za induktivni prehod iz izjave, preverjene za končno podmnožico, na podobno izjavo za celotno neskončno množico, je potreben dokaz. To metodo je predlagal Blaise Pascal, ki je našel splošen algoritem za iskanje meril za deljivost katerega koli celega števila s katerim koli drugim celim številom (traktat »O naravi deljivosti števil«).

Metoda matematične indukcije se uporablja za dokazovanje resnice določene trditve za vsa naravna števila ali resnice izjave, ki izhaja iz nekega števila n.

Reševanje problemov za dokazovanje resničnosti določene trditve po metodi matematične indukcije je sestavljeno iz štirih stopenj (slika 1):

riž. 1. Shema za reševanje problema

1. Osnova indukcije . Preverite veljavnost izjave za najmanjše naravno število, za katero je trditev smiselna.

2. Induktivna predpostavka . Predpostavljamo, da je trditev resnična za neko vrednost k.

3. induktivni prehod . Dokažemo, da je trditev resnična za k+1.

4. Izhod . Če je bil tak dokaz opravljen, potem lahko na podlagi načela matematične indukcije trdimo, da je trditev resnična za katero koli naravno število n.

Razmislite o uporabi metode matematične indukcije pri reševanju problemov za dokazovanje deljivosti naravnih števil.

Primer 1. Dokaži, da je število 5 večkratnik 19, kjer je n naravno število.

Dokaz:

1) Preverimo, ali ta formula velja za n = 1: število =19 je večkratnik 19.

2) Naj ta formula velja za n = k, to pomeni, da je število večkratnik 19.

Deljivo z 19. Dejansko je prvi člen zaradi predpostavke (2) deljiv z 19; drugi člen je prav tako deljiv z 19, ker vsebuje faktor 19.

Primer 2 Dokaži, da je vsota kock treh zaporednih naravnih števil deljiva z 9.

Dokaz:

Dokažimo trditev: »Za katero koli naravno število n je izraz n 3 +(n+1) 3 +(n+2) 3 večkratnik 9.

1) Preverite, ali je ta formula pravilna za n = 1: 1 3 +2 3 +3 3 =1+8+27=36 je večkratnik 9.

2) Naj ta formula velja za n = k, to pomeni, da je k 3 +(k+1) 3 +(k+2) 3 večkratnik 9.

3) Dokažimo, da formula velja tudi za n = k + 1, tj. (k+1) 3 +(k+2) 3 +(k+3) 3 je večkratnik 9. (k+1) 3 +( k+2) 3 +(k+3) 3 =(k+1) 3 +(k+2) 3 + k 3 + 9k 2 +27 k+ 27=(k 3 +(k+1) 3 +(k +2) 3)+9(k 2 +3k+ 3).

Nastali izraz vsebuje dva člena, od katerih je vsak deljiv z 9, torej je vsota deljiva z 9.

4) Oba pogoja načela matematične indukcije sta izpolnjena, zato je trditev resnična za vse vrednosti n.

Primer 3 Dokaži, da je za katero koli naravno n število 3 2n+1 +2 n+2 deljivo s 7.

Dokaz:

1) Preverite, ali je ta formula pravilna za n = 1: 3 2*1+1 +2 1+2 = 3 3 +2 3 =35, 35 je večkratnik 7.

2) Naj ta formula velja za n = k, to pomeni, da je 3 2 k +1 +2 k +2 deljivo s 7.

3) Dokažimo, da formula velja tudi za n = k + 1, t.j.

3 2(k +1)+1 +2 (k +1)+2 =3 2 k +1 3 2 +2 k +2 2 1 =3 2 k +1 9+2 k +2 2 =3 2 k +1 9+2 k +2 (9–7)=(3 2 k +1 +2 k +2) 9–7 2 k +2 .T. Ker je (3 2 k +1 +2 k +2) 9 deljivo s 7 in je 7 2 k +2 deljivo s 7, je tudi njihova razlika deljiva s 7.

4) Oba pogoja načela matematične indukcije sta izpolnjena, zato je trditev resnična za vse vrednosti n.

Številne dokazne probleme v teoriji deljivosti naravnih števil je priročno rešiti z metodo matematične indukcije, lahko celo rečemo, da je reševanje problemov s to metodo precej algoritemično, dovolj je izvesti 4 osnovne korake. Toda te metode ni mogoče imenovati univerzalne, saj obstajajo tudi slabosti: prvič, mogoče je dokazati samo na množici naravnih števil, in drugič, dokazati je mogoče samo za eno spremenljivko.

Za razvoj logičnega mišljenja, matematične kulture je ta metoda potrebno orodje, saj je celo veliki ruski matematik AN Kolmogorov dejal: »Razumevanje in sposobnost pravilne uporabe načela matematične indukcije je dobro merilo za logično zrelost, ki je nujno potrebno za matematiko."

Literatura:

1. Vilenkin N. Ya. Indukcija. Kombinatorika. - M.: Razsvetljenje, 1976. - 48 str.

2. Genkin L. O matematični indukciji. - M., 1962. - 36 str.

3. Solominsky I. S. Metoda matematične indukcije. - M.: Nauka, 1974. - 63 str.

4. Sharygin I. F. Izbirni predmet matematike: Reševanje problemov: Učbenik za 10 celic. Srednja šola - M.: Razsvetljenje, 1989. - 252 str.

5. Shen A. Matematična indukcija. - M.: MTSNMO, 2007.- 32 str.

METODA MATEMATIČNE INDUKCIJE

Beseda indukcija v ruščini pomeni usmerjanje, induktivnim pa rečemo sklepe, ki temeljijo na opazovanjih, poskusih, t.j. pridobljeno s sklepanjem od posebnega do splošnega.

Vsak dan na primer opazujemo, da Sonce vzhaja z vzhoda. Zato ste lahko prepričani, da se bo jutri pojavil na vzhodu in ne na zahodu. Ta sklep sklepamo, ne da bi se zatekli k kakršnim koli domnevam o vzroku gibanja Sonca po nebu (poleg tega se to gibanje izkaže za očitno, saj se globus dejansko premika). In vendar ta induktivna izpeljava pravilno opisuje opažanja, ki jih bomo naredili jutri.

Vloga induktivnih sklepov v eksperimentalnih znanostih je zelo velika. Navedejo te določbe, iz katerih se nato z odbitkom naredijo nadaljnji sklepi. In čeprav teoretična mehanika temelji na Newtonovih treh zakonih gibanja, so bili ti zakoni rezultat globokega razmišljanja o eksperimentalnih podatkih, zlasti o Keplerjevih zakonih gibanja planetov, ki jih je izpeljal med obdelavo dolgotrajnih opazovanj danskega astronoma. Tycho Brahe. Izkazalo se je, da sta opazovanje in indukcija koristna v prihodnosti za izboljšanje predpostavk. Po Michelsonovih poskusih merjenja svetlobne hitrosti v gibljivem mediju se je izkazalo, da je treba razjasniti zakone fizike in ustvariti teorijo relativnosti.

V matematiki je vloga indukcije v veliki meri v tem, da je osnova izbrane aksiomatike. Potem ko je dolga praksa pokazala, da je ravna pot vedno krajša od ukrivljene ali prelomljene, je bilo naravno formulirati aksiom: za katere koli tri točke A, B in C velja neenakost

Temeljni pojem aritmetike, ki mu je treba slediti, se je pojavil tudi iz opazovanja oblikovanja vojakov, ladij in drugih urejenih nizov.

Ne smemo pa misliti, da je s tem konec vloge indukcije v matematiki. Seveda ne bi smeli eksperimentalno preverjati izrekov, ki so logično izpeljani iz aksiomov: če pri izpeljavi ni bilo nobenih logičnih napak, potem so resnični, kolikor so aksiomi, ki smo jih sprejeli, resnični. Toda iz tega sistema aksiomov je mogoče razbrati veliko trditev. In izbor tistih trditev, ki jih je treba dokazati, ponovno predlaga indukcija. Prav ona nam omogoča, da ločimo koristne izreke od neuporabnih, nakazuje, kateri izreki se lahko izkažejo za resnične, in celo pomaga orisati pot dokaza.

Bistvo metode matematične indukcije

V mnogih delih aritmetike, algebre, geometrije, analize je treba dokazati resničnost stavkov A(n), ki so odvisni od naravne spremenljivke. Dokaz resničnosti predloga A(n) za vse vrednosti spremenljivke je pogosto mogoče izvesti z metodo matematične indukcije, ki temelji na naslednjem načelu.

Stavek A(n) velja za resničnega za vse naravne vrednosti spremenljivke, če sta izpolnjena naslednja dva pogoja:

Predlog A(n) velja za n=1.

Iz predpostavke, da A(n) velja za n=k (kjer je k poljubno naravno število), sledi, da velja za naslednjo vrednost n=k+1.

To načelo se imenuje načelo matematične indukcije. Običajno je izbran kot eden od aksiomov, ki opredeljujejo naravne vrste števil, in je zato sprejet brez dokaza.

Metoda matematične indukcije se razume kot naslednja dokazna metoda. Če je treba dokazati resničnost stavka A(n) za vse naravne n, potem je treba najprej preveriti resničnost stavka A(1) in, drugič, predpostaviti resnico stavka A(k) , poskusite dokazati, da je trditev A(k +1) resnična. Če je to mogoče dokazati in dokaz ostane veljaven za vsako naravno vrednost k, potem je v skladu z načelom matematične indukcije trditev A(n) priznana kot resnična za vse vrednosti n.

Metoda matematične indukcije se široko uporablja pri dokazovanju izrekov, istovetnosti, neenakosti, pri reševanju problemov deljivosti, pri reševanju nekaterih geometrijskih in mnogih drugih problemov.

Metoda matematične indukcije pri reševanju problemov na

deljivost

Z uporabo metode matematične indukcije je mogoče dokazati različne trditve o deljivosti naravnih števil.

Naslednjo trditev je mogoče relativno enostavno dokazati. Pokažimo, kako ga pridobimo z metodo matematične indukcije.

Primer 1. Če je n naravno število, je število sodo.

Za n=1 je naša trditev resnična: - sodo število. Predpostavimo, da je to sodo število. Ker je 2k sodo število, potem celo. Torej, parnost je dokazana za n=1, pariteto se izpelje iz parnosti .Torej tudi za vse naravne vrednosti n.

Primer 2Dokaži resničnost stavka

A(n)=(število 5 je večkratnik 19), n je naravno število.

Rešitev.

Trditev A(1)=(število je večkratnik 19) drži.

Recimo, da je za neko vrednost n=k

A(k)=(število je večkratnik 19) je res. Potem, odkar

Očitno je tudi A(k+1) res. Dejansko je prvi člen deljiv z 19 na podlagi predpostavke, da je A(k) resničen; drugi člen je prav tako deljiv z 19, ker vsebuje faktor 19. Oba pogoja principa matematične indukcije sta izpolnjena, zato je trditev A(n) resnična za vse vrednosti n.

Uporaba metode matematične indukcije za

seštevanje serije

Primer 1Dokaži formulo

, n je naravno število.

Rešitev.

Pri n=1 se oba dela enakosti spremenita v enega in je zato izpolnjen prvi pogoj načela matematične indukcije.

Predpostavimo, da je formula resnična za n=k, tj.

.

Dodajmo obema stranema te enakosti in preoblikujemo desno stran. Potem dobimo

Tako iz dejstva, da formula velja za n=k, sledi, da velja tudi za n=k+1. Ta trditev velja za katero koli naravno vrednost k. Torej je izpolnjen tudi drugi pogoj načela matematične indukcije. Formula je dokazana.

Primer 2Dokaži, da je vsota prvih n številk naravnega niza .

Rešitev.

Označimo zahtevano količino, t.j. .

Za n=1 je hipoteza resnična.

Naj bo . Pokažimo to .

Vsekakor,

Problem rešen.

Primer 3Dokaži, da je vsota kvadratov prvih n številk naravnega niza enaka .

Rešitev.

Naj bo .

.

Pretvarjajmo se . Potem

In končno.

Primer 4 Dokaži to.

Rešitev.

Če, potem

Primer 5 Dokaži to

Rešitev.

Za n=1 je hipoteza očitno resnična.

Naj bo .

Dokažimo to.

res,

Primeri uporabe metode matematične indukcije na

dokaz neenakosti

Primer 1Dokaži, da za katero koli naravno število n>1

.

Rešitev.

Označimo levo stran neenakosti z .

Zato je za n=2 neenakost resnična.

Naj za nekaj k. Dokažimo, da potem in . Imamo , .

Če primerjamo in, imamo , tj. .

Za vsako pozitivno celo število k je desna stran zadnje enakosti pozitivna. Zato . Toda zato in .

Primer 2Poiščite napako v sklepanju.

Izjava. Za vsak naravni n je neenakost resnična.

Dokaz.

. (1)

Dokažimo, da potem neenakost velja tudi za n=k+1, t.j.

.

Dejansko vsaj 2 za kateri koli naravni k. Levi strani dodajmo neenakost (1), na desno pa 2. Dobimo pošteno neenakost oz. . Trditev je dokazana.

Primer 3Dokaži to , kjer je >-1, , n naravno število, večje od 1.

Rešitev.

Za n=2 je neenakost resnična, saj .

Naj neenakost velja za n=k, kjer je k neko naravno število, t.j.

. (1)

Pokažimo, da potem neenakost velja tudi za n=k+1, t.j.

. (2)

Dejansko, po predpostavki, , Torej, neenakost

, (3)

dobimo iz neenakosti (1) tako, da vsak njen del pomnožimo z . Prepišimo neenakost (3) takole: . Če zavržemo pozitivni člen na desni strani zadnje neenakosti, dobimo veljavno neenakost (2).

Primer 4 Dokaži to

(1)

kjer je , , n naravno število, večje od 1.

Rešitev.

Pri n=2 ima neenakost (1) obliko

. (2)

Ker , Potem je neenakost

. (3)

Vsakemu delu neenakosti (3) dodamo z , dobimo neenakost (2).

To dokazuje, da neenakost (1) velja za n=2.

Naj neenakost (1) velja za n=k, kjer je k neko naravno število, t.j.

. (4)

Dokažimo, da mora potem neenakost (1) veljati tudi za n=k+1, t.j.

(5)

Oba dela neenakosti (4) pomnožimo z a+b. Ker po pogoju, dobimo naslednjo pošteno neenakost:

. (6)

Za dokaz neenakosti (5) zadostuje, da to pokažemo

, (7)

ali, kar je enako,

. (8)

Neenakost (8) je enakovredna neenakosti

. (9)

Če , Potem , In na levi strani neenakosti (9) imamo produkt dveh pozitivnih števil. Če , Potem , In na levi strani neenakosti (9) imamo produkt dveh negativnih številk. V obeh primerih velja neenakost (9).

To dokazuje, da veljavnost neenakosti (1) za n=k implicira njeno veljavnost za n=k+1.

Metoda matematične indukcije, ki se uporablja za druge

naloge

Najbolj naravna uporaba metode matematične indukcije v geometriji, blizu uporabi te metode v teoriji števil in algebri, je uporaba pri reševanju geometrijskih računskih problemov. Poglejmo si nekaj primerov.

Primer 1Izračunajte stran pravilnega kvadrata, vpisanega v krog s polmerom R.

Rešitev.

Za n=2 pravilno 2 n - kvadrat je kvadrat; njegova stran. Nadalje po formuli za podvajanje

ugotovite, da je stran pravilnega osmerokotnika , stran pravilnega šesterokotnika , stranica pravilnega dvaintridesetega kota . Zato lahko domnevamo, da je stranica pravilne vpisane 2 n - kvadrat za katero koli je enak

. (1)

Predpostavimo, da je stran pravilnega vpisanega -kotnika izražena s formulo (1). V tem primeru po formuli podvojitve

,

od koder sledi, da formula (1) velja za vse n.

Primer 2Na koliko trikotnikov je mogoče razdeliti n-kotnik (ni nujno konveksen) z diagonalami, ki se ne sekajo?

Rešitev.

Za trikotnik je to število enako ena (v trikotniku ni mogoče narisati diagonal); za štirikotnik je to število očitno enako dve.

Recimo, da že vemo, da je vsak k-gon, kjer je k 1 A 2 ... A n v trikotnike.

A n

A 1 A 2

Naj bo A 1 А k ena od diagonal te particije; deli n-kotnik А 1 А 2 …А n na k-kotnik A 1 A 2 …A k in (n-k+2)-kotnik А 1 А k A k+1 …A n . Na podlagi opravljene predpostavke bo skupno število pregradnih trikotnikov enako

(k-2)+[(n-k+2)-2]=n-2;

tako je naša trditev dokazana za vse n.

Primer 3Določite pravilo za izračun števila P(n) načinov, na katere lahko konveksni n-kotnik razdelimo na trikotnike z nesekajočimi se diagonalami.

Rešitev.

Za trikotnik je to število očitno enako ena: P(3)=1.

Recimo, da smo za vse k že določili števila P(k). 1 A 2 ... A n . Za katero koli njegovo razdelitev na trikotnike je stran A 1 A 2 bo stran enega od pregradnih trikotnikov, tretje oglišče tega trikotnika lahko sovpada z vsako od točk A 3 , А 4 , …,А n . Število načinov za razdelitev n-kotnika, pri katerem to oglišče sovpada s točko A 3 , je enako številu načinov za triangulacijo (n-1)-kotnika A 1 A 3 A 4 ... A n , tj. enako P(n-1). Število načinov razdelitve, na katere to oglišče sovpada z A 4 , je enako številu načinov za razdelitev (n-2)-kotnika A 1 A 4 A 5 ... A n , tj. enako P(n-2)=P(n-2)P(3); število načinov razdelitve, v katerih sovpada z A 5 , je enako P(n-3)P(4), saj vsaka od particij (n-3)-kotnika A 1 A 5 ... A n se lahko kombinira z vsako od particij štirikotnika A 2 A 3 A 4 A 5 , itd Tako pridemo do naslednje relacije:

Р(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n -ena).

S to formulo zaporedoma dobimo:

P(4)=P(3)+P(3)=2,

P(5)=P(4)+P(3)P(3)+P(4)+5,

P(6)=P(5)+P(4)P(3)+P(3)P(4)+P(5)=14

itd.

Tudi z uporabo metode matematične indukcije lahko rešujete probleme z grafi.

Naj je na ravnini podana mreža premic, ki povezujejo nekatere točke med seboj in nimajo drugih točk. Takšno mrežo črt bomo poimenovali zemljevid, določene točke z njegovimi oglišči, odseki krivulj med dvema sosednjima ogliščema - mejama zemljevida, deli ravnine, na katere je razdeljena z mejami - državami zemljevida.

Naj bo na letalu podan kakšen zemljevid. Da je pravilno obarvana, bomo rekli, če je vsaka njena država pobarvana v določeno barvo, katerikoli dve državi, ki imata skupno mejo, pa sta pobarvani v različnih barvah.

Primer 4Na ravnini je n krogov. Dokaži, da je za vsako razporeditev teh krogov zemljevid, ki ga tvorijo, mogoče pravilno obarvati z dvema barvama.

Rešitev.

Za n=1 je naša trditev očitna.

Recimo, da je naša izjava resnična za kateri koli zemljevid, ki ga tvori n krogov, in naj je na ravnini podanih n + 1 krogov. Z odstranitvijo enega od teh krogov dobimo zemljevid, ki ga je na podlagi predpostavke mogoče pravilno obarvati z dvema barvama, na primer črno-belo.

Uvod

Glavni del

1. Popolna in nepopolna indukcija

2. Načelo matematične indukcije

3. Metoda matematične indukcije

4. Rešitev primerov

5. Enakosti

6. Delitev številk

7. Neenakosti

Zaključek

Seznam uporabljene literature

Uvod

Deduktivne in induktivne metode so osnova vsakega matematičnega raziskovanja. Deduktivna metoda sklepanja je sklepanje od splošnega k posebnemu, t.j. sklepanje, katerega izhodišče je splošni rezultat, končna točka pa poseben rezultat. Indukcija se uporablja pri prehodu od posameznih rezultatov k splošnim, t.j. je nasprotje deduktivne metode.

Metodo matematične indukcije lahko primerjamo z napredkom. Začnemo od najnižjega, kot posledica logičnega razmišljanja pridemo do najvišjega. Človek si je vedno prizadeval za napredek, za sposobnost logičnega razvoja svoje misli, kar pomeni, da mu je narava sama namenila razmišljanje induktivno.

Čeprav se je področje uporabe metode matematične indukcije povečalo, se ji v šolskem kurikulumu posveča malo časa. No, recimo, da bo koristnega človeka pripeljala tista dva ali tri lekcije, za katere sliši pet teoretskih besed, reši pet primitivnih problemov in posledično dobi pet, ker nič ne ve.

A to je tako pomembno – znati induktivno razmišljati.

Glavni del

V svojem prvotnem pomenu se beseda "indukcija" uporablja za sklepanje, s pomočjo katerega se pridobijo splošni zaključki, ki temeljijo na številnih posebnih izjavah. Najenostavnejša metoda sklepanja te vrste je popolna indukcija. Tukaj je primer takšnega sklepanja.

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;

14=7+7; 16=11+5; 18=13+5; 20=13+7.

Teh devet enakosti kaže, da je vsako od števil, ki nas zanimajo, dejansko predstavljeno kot vsota dveh pračlanov.

Popolna indukcija je torej, da se splošna izjava dokaže ločeno v vsakem od končnega števila možnih primerov.

Včasih je splošni rezultat mogoče predvideti po upoštevanju ne vseh, temveč velikega števila posebnih primerov (tako imenovana nepopolna indukcija).

Rezultat, pridobljen z nepopolno indukcijo, pa ostaja le hipoteza, dokler se ne dokaže z natančnim matematičnim sklepanjem, ki zajema vse posebne primere. Z drugimi besedami, nepopolna indukcija v matematiki ne velja za legitimno metodo strogega dokazovanja, ampak je močna metoda za odkrivanje novih resnic.

Naj na primer najdemo vsoto prvih n zaporednih lihih številk. Razmislite o posebnih primerih:

1+3+5+7+9=25=5 2

Po preučitvi teh nekaj posebnih primerov se izkaže naslednji splošni sklep:

1+3+5+…+(2n-1)=n 2

tiste. vsota prvih n zaporednih lihih števil je n 2

Seveda opravljeno opažanje še ne more služiti kot dokaz veljavnosti zgornje formule.

Popolna indukcija ima v matematiki le omejeno uporabo. Številne zanimive matematične izjave pokrivajo neskončno število posebnih primerov in ne moremo testirati za neskončno število primerov. Nepopolna indukcija pogosto vodi do napačnih rezultatov.

V mnogih primerih je izhod iz te vrste težav uporaba posebne metode sklepanja, imenovane metoda matematične indukcije. To je sledeče.

Naj je treba dokazati veljavnost določene trditve za katero koli naravno število n (na primer, dokazati je treba, da je vsota prvih n lihih številk enaka n 2). Neposredno preverjanje te izjave za vsako vrednost n je nemogoče, saj je množica naravnih števil neskončna. Če želite dokazati to trditev, najprej preverite njeno veljavnost za n=1. Nato se dokaže, da za katero koli naravno vrednost k veljavnost obravnavane izjave za n=k implicira njeno veljavnost tudi za n=k+1.

Potem se trditev šteje za dokazano za vse n. Dejansko je trditev resnična za n=1. Toda potem velja tudi za naslednje število n=1+1=2. Veljavnost trditve za n=2 implicira njeno veljavnost za n=2+

1=3. To pomeni veljavnost izjave za n=4 itd. Jasno je, da bomo na koncu dosegli katero koli naravno število n. Torej je trditev resnična za kateri koli n.

Če povzamemo povedano, oblikujemo naslednje splošno načelo.

Načelo matematične indukcije.

Če stavek A( n ) odvisno od naravnega števila n , res za n =1 in iz dejstva, da je res za n=k (kje k - poljubno naravno število), iz tega sledi, da velja tudi za naslednje število n=k+1 , potem predpostavka A( n ) velja za vsako naravno število n .

Dokaz z metodo matematične indukcije se izvede na naslednji način. Najprej se trditev, ki jo je treba dokazati, preveri za n=1, tj. ugotovljena je resnica trditve A(1). Ta del dokaza se imenuje indukcijska osnova. Temu sledi del dokaza, imenovan indukcijski korak. V tem delu je dokazana veljavnost trditve za n=k+1 ob predpostavki, da je trditev resnična za n=k (indukcijska predpostavka), t.j. dokaži, da je A(k)ÞA(k+1).

PRIMER 1

Dokaži, da je 1+3+5+…+(2n-1)=n 2 .

Rešitev: 1) Imamo n=1=1 2 . posledično

trditev velja za n=1, tj. A(1) je res.

2) Dokažimo, da je A(k)ÞA(k+1).

Naj je k poljubno naravno število in trditev velja za n=k, t.j.

1+3+5+…+(2k-1)=k 2 .

Dokažimo, da potem trditev drži tudi za naslednje naravno število n=k+1, t.j. kaj

1+3+5+…+(2k+1)=(k+1) 2 .

Vsekakor,

1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 .

Torej A(k)ÞA(k+1). Na podlagi principa matematične indukcije sklepamo, da je predpostavka A(n) resnična za vsak nОN.

PRIMER 2

Dokaži to

1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), kjer je x¹1

Rešitev: 1) Za n=1 dobimo

1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1

zato je za n=1 formula resnična; A(1) je res.

2) Naj je k poljubno naravno število in formula velja za n=k, tj.

1 + x + x 2 + x 3 + ... + x k \u003d (x k + 1 -1) / (x-1).

Dokažimo, da je potem enakost

1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1).

Vsekakor

1+х+х 2 +x 3 +…+х k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =

=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1).

Torej A(k)ÞA(k+1). Na podlagi načela matematične indukcije sklepamo, da formula velja za vsako naravno število n.

PRIMER 3

Dokaži, da je število diagonal konveksnega n-kotnika n(n-3)/2.

Rešitev: 1) Za n=3 je trditev resnična

 A 3 =3(3-3)/2=0 diagonal;

A 2 A(3) je res.

2) Recimo, da v katerem koli

konveksni k-kotnik ima-

A 1 sya A k \u003d k (k-3) / 2 diagonali.

A k Dokažimo to potem v konveksnem

(k+1)-kotnik številka

diagonale A k+1 =(k+1)(k-2)/2.

Naj A 1 А 2 А 3 …A k A k+1 -konveksni (k+1)-kot. Vanj narišemo diagonalo A 1 A k. Če želite prešteti skupno število diagonal tega (k + 1)-kotnika, morate prešteti število diagonal v k-kotniku A 1 A 2 ...A k , k dobljeni številki dodati k-2, t.j. upoštevati je treba število diagonal (k+1)-kotnika, ki izhajajo iz oglišča A k+1, in poleg tega še diagonalo A 1 A k.

V to smer,

 k+1 = k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.

Torej A(k)ÞA(k+1). Zaradi načela matematične indukcije je trditev resnična za vsak konveksni n-kotnik.

PRIMER 4

Dokaži, da je za katero koli n trditev resnična:

1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6.

Rešitev: 1) Potem naj bo n=1

X 1 = 1 2 = 1 (1 + 1) (2 + 1) / 6 \u003d 1.

Zato je za n=1 trditev resnična.

2) Predpostavimo, da je n=k

X k \u003d k 2 = k (k + 1) (2k + 1) / 6.

3) Razmislite o tej izjavi za n=k+1

Xk+1 =(k+1)(k+2)(2k+3)/6.

X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2 =(k (k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+

6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+

2))/6=(k+1)(k+2)(2k+3)/6.

Dokazali smo veljavnost enakosti za n=k+1, zato je na podlagi metode matematične indukcije trditev resnična za vsako naravno n.

PRIMER 5

Dokaži, da za katero koli naravno n velja enakost:

1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4.

Rešitev: 1) Naj bo n=1.

Potem je X 1 =1 3 =1 2 (1+1) 2 /4=1.

Vidimo, da je trditev resnična za n=1.

2) Predpostavimo, da je enakost resnična za n=k

Indukcija je metoda pridobivanja splošne izjave iz določenih opazovanj. V primeru, ko se matematična izjava nanaša na končno število predmetov, jo je mogoče dokazati s preverjanjem za vsak predmet. Na primer, trditev: »Vsako dvomestno sodo število je vsota dveh praštevil« izhaja iz niza enakosti, ki jih je precej realno ugotoviti:

10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.

Dokazna metoda, pri kateri se trditev preveri za končno število primerov, ki izčrpajo vse možnosti, se imenuje popolna indukcija. Ta metoda je relativno redko uporabna, saj matematične izjave praviloma ne zadevajo končnih, temveč neskončnih nizov predmetov. Na primer, izjava o sodih dvomestnih številih, dokazana zgoraj s popolno indukcijo, je le poseben primer izreka: "Vsako sodo število je vsota dveh praštevil." Ta izrek še ni bil dokazan ali ovržen.

Matematična indukcija je metoda dokazovanja določene trditve za katero koli naravno n, ki temelji na principu matematične indukcije: »Če je trditev resnična za n=1 in iz njene veljavnosti za n=k sledi, da ta trditev drži za n= k+1, potem velja za vse n". Metoda dokazovanja z matematično indukcijo je naslednja:

1) osnova indukcije: dokazati ali neposredno preveriti veljavnost trditve za n=1 (včasih n=0 ali n=n 0);

2) indukcijski korak (prehod): predpostavijo veljavnost trditev za neko naravno n=k in na podlagi te predpostavke dokazujejo veljavnost izjave za n=k+1.

Težave z rešitvami

1. Dokaži, da je za katero koli naravno n število 3 2n+1 +2 n+2 deljivo s 7.

Označimo A(n)=3 2n+1 +2 n+2 .

osnova indukcije. Če je n=1, potem je A(1)=3 3 +2 3 =35 in je očitno deljivo s 7.

Indukcijska hipoteza. Naj je A(k) deljivo s 7.

induktivni prehod. Dokažimo, da je A(k+1) deljivo s 7, torej veljavnost izjave problema za n=k.

А(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 3 2 +2 k+2 2 1 =3 2k+1 9+2 k+2 2=

3 2k+1 9+2 k+2 (9–7)=(3 2k+1 +2 k+2) 9–7 2 k+2 =9 A(k)–7 2 k +2 .

Zadnje število je deljivo s 7, saj je razlika dveh celih števil, deljivih s 7. Zato je 3 2n+1 +2 n+2 deljivo s 7 za katero koli naravno n.

2. Dokaži, da je za vsako pozitivno celo število n število 2 3 n +1 deljivo s 3 n+1 in ni deljivo s 3 n+2 .

Uvedemo zapis: a i =2 3 i +1.

Za n=1 imamo in 1 =2 3 +1=9. Torej, 1 je deljiva s 3 2 in ni deljiva s 3 3 .

Naj je za n=k število a k deljivo s 3 k+1 in ni deljivo s 3 k+2 , t.j. a k =2 3 k +1=3 k+1 m, kjer m ni deljivo s 3. Potem

in k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k 2 –2 3 k +1)=3 k+1 m m ((2 3 k +1) 2 –3 2 3 k)=3 k+1 m ((3 k+1 m) 2 –3 2 3 k)=

3 k+2 m (3 2k+1 m 2 –2 3 k).

Očitno je k+1 deljiv s 3 k+2 in ni deljiv s 3 k+3 .

Zato je trditev dokazana za vsako naravno n.

3. Znano je, da je x+1/x celo število. Dokaži, da je х n +1/х n tudi celo število za katero koli celo število n.

Uvedemo zapis: a i \u003d x i +1 / x i in takoj opazimo, da a i = a -i, zato bomo še naprej govorili o naravnih indeksih.

Opomba: in 1 je po pogoju celo število; a 2 je celo število, saj je 2 \u003d (a 1) 2 -2; in 0=2.

Predpostavimo, da je a k celo število za vsako pozitivno celo število k, ki ne presega n. Potem je a 1 ·a n celo število, a 1 ·a n =a n+1 +a n–1 in a n+1 =a 1 ·a n –a n–1. Vendar je in n–1 po indukcijski hipotezi celo število. Zato je a n+1 tudi celo število. Zato je х n +1/х n celo število za katero koli celo število n, ki je bilo treba dokazati.

4. Dokaži, da je za vsako pozitivno celo število n, večje od 1, dvojna neenakost

5. Dokaži, da za naravni n > 1 in |х|

(1–x)n +(1+x)n

Za n=2 je neenakost resnična. res,

(1–x) 2 + (1 + x) 2 \u003d 2 + 2 x 2

Če neenakost velja za n=k, potem imamo za n=k+1

(1–x)k+1 +(1+x)k+1

Neenakost je dokazana za vsako naravno število n > 1.

6. Na ravnini je n krogov. Dokaži, da je za vsako razporeditev teh krogov zemljevid, ki ga tvorijo, mogoče pravilno obarvati z dvema barvama.

Uporabimo metodo matematične indukcije.

Za n=1 je trditev očitna.

Predpostavimo, da je trditev resnična za kateri koli zemljevid, ki ga tvori n krogov, in naj je na ravnini podanih n + 1 krogov. Če odstranimo enega od teh krogov, dobimo zemljevid, ki ga na podlagi predpostavke lahko pravilno obarvamo z dvema barvama (glej prvo sliko spodaj).

Nato obnovimo zavrženi krog in na eni njegovi strani, na primer znotraj, spremenimo barvo vsakega področja v nasprotno (glej drugo sliko). Preprosto je videti, da v tem primeru dobimo zemljevid, ki je pravilno obarvan z dvema barvama, vendar šele zdaj z n + 1 krogi, kar je bilo treba dokazati.

7. Konveksni mnogokotnik bomo imenovali "lep", če so izpolnjeni naslednji pogoji:

1) vsako od njegovih oglišč je pobarvano v eni od treh barv;

2) kateri koli dve sosednji točki sta pobarvani v različnih barvah;

3) vsaj eno oglišče mnogokotnika je obarvano v vsako od treh barv.

Dokaži, da lahko vsak lep n-kotnik razrežemo z nesekajočimi se diagonalami v "lepe" trikotnike.

Uporabimo metodo matematične indukcije.

osnova indukcije. Pri najmanjšem možnem n=3 je izjava problema očitna: oglišča "lepega" trikotnika so obarvana v tri različne barve in rezi niso potrebni.

Indukcijska hipoteza. Predpostavimo, da je izjava o problemu resnična za vsak "lep" n-kotnik.

indukcijski korak. Razmislite o poljubnem "lepem" (n + 1)-kotecu in z induktivno predpostavko dokažite, da ga je mogoče z nekaterimi diagonalami razrezati v "lepe" trikotnike. Označimo z А 1 , А 2 , А 3 , … А n , А n+1 – zaporedna oglišča (n+1)-kotnika. Če je samo eno oglišče (n + 1)-kotnika obarvano v katero koli od treh barv, potem s povezovanjem tega oglišča z diagonalami na vsa oglišča, ki mu ne mejijo, dobimo potrebno particijo (n + 1)- gon v "lepe" trikotnike.

Če sta vsaj dve oglišči (n + 1)-kotnika pobarvani v vsako od treh barv, potem barvo oglišča A 1 označimo s številko 1, barvo oglišča A 2 pa s številko 2 . Naj bo k najmanjše število, tako da je oglišče A k obarvano v tretjo barvo. Jasno je, da je k > 2. Odrežemo trikotnik А k–2 А k–1 А k od (n+1)-kotnika z diagonalo А k–2 А k . V skladu z izbiro števila k so vsa oglišča tega trikotnika pobarvana v treh različnih barvah, torej je ta trikotnik "lep". Konveksni n-kotnik A 1 A 2 ... A k–2 A k A k+1 ... A n+1 , ki ostane, bo tudi zaradi induktivne predpostavke »lep«, kar pomeni, da je razdeljen na "lepe" trikotnike, kar in je bilo treba dokazati.

8. Dokaži, da je v konveksnem n-kotniku nemogoče izbrati več kot n diagonal, tako da imata kateri koli dve skupno točko.

Dokaz opravimo po metodi matematične indukcije.

Dokažimo bolj splošno trditev: v konveksnem n-kotniku je nemogoče izbrati več kot n stranic in diagonal, tako da imata kateri koli dve skupno točko. Za n = 3 je trditev očitna. Predpostavimo, da ta trditev velja za poljuben n-kotnik in s tem dokažimo njeno veljavnost za poljuben (n + 1)-kotnik.

Predpostavimo, da za (n + 1)-kotnik ta izjava ne drži. Če iz vsakega oglišča (n+1)-kotnika ne izhajata več kot dve izbrani strani ali diagonali, jih je izbranih največ n+1. Zato iz nekega oglišča A izhajajo vsaj tri izbrane stranice ali diagonale AB, AC, AD. Naj AC leži med AB in AD. Ker katera koli stran ali diagonala, ki izhaja iz C, razen CA, ne more istočasno prečkati AB in AD, iz C izhaja samo ena izbrana diagonala CA.

Če zavržemo točko C skupaj z diagonalo CA, dobimo konveksni n-kotnik, v katerem je izbranih več kot n stranic in diagonal, od katerih imata kateri koli dve skupno točko. Tako pridemo do protislovja s predpostavko, da je trditev resnična za poljuben konveksen n-kotnik.

Torej, za (n + 1)-kotnik je trditev resnična. V skladu z načelom matematične indukcije je trditev resnična za kateri koli konveksni n-kotnik.

9. V ravnini je narisanih n premic, od katerih nobena nista vzporedna in nobena tri ne poteka skozi isto točko. Na koliko delov te premice delijo ravnino.

S pomočjo osnovnih risb je enostavno zagotoviti, da ena ravna črta razdeli ravnino na 2 dela, dve ravni črti na 4 dele, tri ravne črte na 7 delov in štiri ravne črte na 11 delov.

Z N(n) označimo število delov, na katere n premic deli ravnino. To se vidi

N(2)=N(1)+2=2+2,

N(3)=N(2)+3=2+2+3,

N(4)=N(3)+4=2+2+3+4.

To je naravno domnevati

N(n)=N(n–1)+n=2+2+3+4+5+…+n,

ali, kot je enostavno ugotoviti, z uporabo formule za vsoto prvih n členov aritmetične progresije,

N(n)=1+n(n+1)/2.

Dokažimo veljavnost te formule z metodo matematične indukcije.

Za n=1 je bila formula že preverjena.

Po induktivni predpostavki razmislite o k + 1 vrsticah, ki izpolnjujejo pogoj problema. Iz njih poljubno izberemo k ravnih črt. Po induktivni hipotezi razdelijo ravnino na 1+ k(k+1)/2 dela. Preostala (k + 1)-ta vrstica bo razdeljena z izbranimi k vrsticami na k + 1 delov in bo tako šla skozi (k + 1)-ti del, na katerega je bila ravnina že razdeljena, in vsaka od ti deli bodo razdeljeni na 2 dela, torej bo dodanih še k+1 delov. torej

N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,

Q.E.D.

10. V izrazu x 1: x 2: ...: x n so oklepaji postavljeni, da označujejo vrstni red dejanj, rezultat pa je zapisan kot ulomek:

(v tem primeru je vsaka od črk x 1, x 2, ..., x n bodisi v števcu ulomka bodisi v imenovalcu). Koliko različnih izrazov je na ta način mogoče dobiti z vsemi možnimi načini razporeditve oklepajev?

Najprej je jasno, da bo v nastalem ulomku x 1 v števcu. Skoraj enako očitno je, da bo x 2 v imenovalcu za katero koli razporeditev oklepajev (znak delitve pred x 2 se nanaša bodisi na sam x 2 ali na kateri koli izraz, ki vsebuje x 2 v števcu).

Domnevamo lahko, da se lahko vse ostale črke x 3 , x 4 , ... , x n nahajajo v števcu ali imenovalcu na povsem poljuben način. Iz tega sledi, da lahko skupaj dobite 2 n-2 ulomka: vsaka od n-2 črk x 3, x 4, ..., x n je lahko neodvisno od drugih v števcu ali imenovalcu.

Dokažimo to trditev z indukcijo.

Z n=3 lahko dobite 2 ulomka:

torej trditev drži.

Predvidevamo, da velja za n=k in dokažemo za n=k+1.

Naj izraz x 1: x 2: ...: xk po določeni razporeditvi oklepajev zapišemo kot ulomek Q. Če v ta izraz namesto xk nadomestimo xk: x k+1, bo xk v na istem mestu, kot je bilo v ulomkih Q, in x k + 1 ne bo tam, kjer je stal x k (če je bil x k v imenovalcu, bo x k + 1 v števcu in obratno).

Zdaj pa dokažimo, da lahko dodamo x k+1 na isto mesto kot x k . V ulomku Q bo po postavitvi oklepajev nujno izraz v obliki q:x k, kjer je q črka x k–1 ali kakšen izraz v oklepajih. Če zamenjamo q: x k z izrazom (q: x k): x k + 1 = q: (x k x k + 1), dobimo očitno isti ulomek Q, kjer je namesto x k x k x k+1 .

Tako je število možnih ulomkov v primeru n=k+1 2-krat večje kot v primeru n=k in je enako 2 k–2 ·2=2 (k+1)–2 . Tako je trditev dokazana.

Odgovor: 2 n-2 frakcije.

Težave brez rešitev

1. Dokaži, da za katero koli naravno n:

a) število 5 n -3 n + 2n je deljivo s 4;

b) število n 3 +11n je deljivo s 6;

c) število 7 n +3n–1 je deljivo z 9;

d) število 6 2n +19 n –2 n+1 je deljivo s 17;

e) število 7 n+1 +8 2n–1 je deljivo z 19;

f) število 2 2n–1 –9n 2 +21n–14 je deljivo s 27.

2. Dokaži, da je (n+1)·(n+2)· …·(n+n) = 2 n ·1·3·5·…·(2n–1).

3. Dokaži neenakost |sin nx| n|sinx| za katerokoli naravno n.

4. Poiščite naravna števila a, b, c, ki niso deljiva z 10 in taka, da imata za katero koli naravno n števili a n + b n in c n enaki zadnji dve števki.

5. Dokaži, da če n točk ne leži na eni premici, je med premicami, ki jih povezujejo, vsaj n različnih.