Metoda matematičke indukcije i njena primjena u rješavanju problema. Primjeri indukcije. Metoda matematičke indukcije: primjeri rješenja
Video lekcija “Metoda matematičke indukcije” pomaže vam da savladate metodu matematičke indukcije. Video sadrži materijal koji vam pomaže da shvatite suštinu metode, zapamtite karakteristike njene primjene i naučite kako primijeniti ovu metodu prilikom rješavanja problema. Svrha ovog video tutorijala je olakšati razvoj gradiva i razviti sposobnost rješavanja matematičkih problema metodom indukcije.
Da bi se zadržala pažnja učenika na učenju gradiva, koriste se efekti animacije, ilustracije i prikaz informacija u boji. Video lekcija oslobađa nastavniku vrijeme na času za poboljšanje kvaliteta samostalnog rada i rješavanje drugih obrazovnih problema.
Koncept metode matematičke indukcije uvodi se razmatranjem niza a n , u kojem je a 1 =4, a a n+1 = a n +2n+3. U skladu sa opštim prikazom člana niza, utvrđuje se da je a 1 =4, a 2 =4+2·1+3=9, a 3 =9+2·2+3=16, tj. niz brojeva 4, 9, 16,... Pretpostavlja se da je za ovaj niz tačno n =(n+1) 2. Za naznačene pojmove niza - prvi, drugi, treći - formula je ispravna. Potrebno je dokazati valjanost ove formule za bilo koje proizvoljno veliko n. Naznačeno je da se u takvim slučajevima koristi metoda matematičke indukcije koja pomaže u dokazivanju tvrdnje.
Otkrivena je suština metode. Pretpostavlja se da je formula za n=k validna, vrijednost a k =(k+1) 2 . Potrebno je dokazati da će jednakost vrijediti i za k+1, što znači a k +1 =(k+2) 2 . Da bismo to učinili, u formuli a k +1 =a k +2k+3 zamjenjujemo a k sa (k+1) 2. Nakon zamjene i redukcije sličnih, dobijamo jednakost a k +1 =(k+2) 2 . Ovo nam daje pravo da tvrdimo da valjanost formule za n čini istinitom za n=k+1. Razmatrani dokaz u odnosu na niz a n , koji je predstavljen brojevima 4, 9, 16,... i opštim pojmom a n =(n+1) 2, daje pravo da se tvrdi da ako se formula pretvori u tačna jednakost za n=1, zatim i za n=1+ 1=2, i za 3, itd., odnosno za bilo koji prirodan broj n.
Zatim je matematičkim jezikom predstavljena suština metode indukcije. Princip metode zasniva se na validnosti tvrdnje da činjenica važi za proizvoljan prirodan broj n kada su ispunjena dva uslova: 1) izjava je tačna za n=1 2) iz validnosti ove formule za n= k slijedi da vrijedi za n=k+1. Iz ovog principa slijedi struktura dokaza, korištenjem metode matematičke indukcije. Napominje se da ova metoda pretpostavlja za n=1 dokaz valjanosti iskaza, a kada se pretpostavi valjanost dokaza za n=k, dokazuje se da je to tačno i za n=k+1.
Analiziran je primjer dokazivanja Arhimedove formule metodom matematičke indukcije. S obzirom na formulu 1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6. Izračunavanje se vrši na ekranu kako bi se pokazalo valjanost formule za n=1. Druga tačka dokaza je pretpostavka da za n=k formula vrijedi, odnosno da ima oblik 1 2 +2 2 +3 2 +…+k 2 =k(k+1)(2k+1 )/6 Na osnovu ovoga, dokazano je da formula vrijedi i za n=k+1. Nakon zamjene n=k+1 dobijamo vrijednost formule 1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =(k+1)(k+2)(2k+3) /6. Time je Arhimedova formula dokazana.
Drugi primjer ispituje dokaz višestrukosti 7 od zbira 15 n +6 za bilo koji prirodni broj n. U dokazu koristimo metodu matematičke indukcije. Prvo, provjeravamo valjanost iskaza za n=1. Zaista, 15 1 +6=21. Tada pretpostavljamo validnost za n=k. To znači da je 15 k +6 višekratnik 7. Zamjenom n=k+1 u formulu dokazujemo da je vrijednost 15 k +1 +6 višekratnik 7. Nakon transformacije izraza, dobijamo: 15 k +1 +6=15 k +1 ·14+(15 k +6). Stoga je zbir 15 n +6 višekratnik 7.
Video lekcija “Metoda matematičke indukcije” jasno i detaljno otkriva suštinu i mehanizam upotrebe metode matematičke indukcije u dokazu. Stoga ovaj video materijal može poslužiti ne samo kao vizualna pomoć u lekciji algebre, već će biti koristan kada učenik samostalno proučava materijal, te će pomoći u objašnjavanju teme nastavniku tokom učenja na daljinu.
Bibliografski opis: Badanin A. S., Sizova M. Yu Primjena metode matematičke indukcije na rješavanje problema o djeljivosti prirodnih brojeva // Mladi naučnik. 2015. br. 2. str. 84-86..04.2019.).
Na matematičkim olimpijadama često postoje prilično teški zadaci za dokazivanje djeljivosti prirodnih brojeva. Školarci se suočavaju s problemom: kako pronaći univerzalnu matematičku metodu koja im omogućava rješavanje takvih problema?
Pokazalo se da se većina problema u dokazivanju djeljivosti može riješiti metodom matematičke indukcije, ali školski udžbenici ovoj metodi posvećuju vrlo malo pažnje, najčešće se daje kratak teorijski opis i analizira nekoliko problema.
Metodu matematičke indukcije nalazimo u teoriji brojeva. U zoru teorije brojeva, matematičari su induktivno otkrili mnoge činjenice: L. Euler i K. Gauss su ponekad razmatrali hiljade primjera prije nego što su primijetili numerički obrazac i povjerovali u njega. Ali istovremeno su shvatili koliko hipoteze koje su prošle "konačni" test mogu biti varljive. Da bismo induktivno prešli sa iskaza verifikovanog za konačan podskup na sličan iskaz za ceo beskonačan skup, potreban je dokaz. Ovu metodu je predložio Blaise Pascal, koji je pronašao opći algoritam za pronalaženje znakova djeljivosti bilo kojeg cijelog broja bilo kojim drugim cijelim brojem (traktat „O prirodi djeljivosti brojeva“).
Metoda matematičke indukcije se koristi za dokazivanje istinitosti određene tvrdnje za sve prirodne brojeve ili istinitosti iskaza počevši od određenog broja n.
Rješavanje problema za dokazivanje istinitosti određene tvrdnje metodom matematičke indukcije sastoji se od četiri faze (slika 1):
Rice. 1. Šema za rješavanje problema
1. Indukciona osnova . Oni provjeravaju valjanost iskaza za najmanji prirodni broj za koji izjava ima smisla.
2. Induktivna hipoteza . Pretpostavljamo da je tvrdnja tačna za neku vrijednost k.
3. Indukcijski prijelaz . Dokazujemo da je tvrdnja tačna za k+1.
4. Zaključak . Ako je takav dokaz završen, onda se, na osnovu principa matematičke indukcije, može tvrditi da je tvrdnja tačna za bilo koji prirodni broj n.
Razmotrimo primjenu metode matematičke indukcije na rješavanje problema dokazivanja djeljivosti prirodnih brojeva.
Primjer 1. Dokažite da je broj 5 višekratnik broja 19, gdje je n prirodan broj.
dokaz:
1) Provjerimo da li je ova formula tačna za n = 1: broj =19 je višekratnik od 19.
2) Neka je ova formula tačna za n = k, tj. broj je višestruki od 19.
To je višekratnik od 19. Zaista, prvi član je djeljiv sa 19 zbog pretpostavke (2); drugi član je također djeljiv sa 19 jer sadrži faktor 19.
Primjer 2. Dokažite da je zbir kocki tri uzastopna prirodna broja djeljiv sa 9.
dokaz:
Dokažimo tvrdnju: „Za bilo koji prirodni broj n, izraz n 3 +(n+1) 3 +(n+2) 3 je višekratnik broja 9.
1) Provjerimo da li je ova formula tačna za n = 1: 1 3 +2 3 +3 3 =1+8+27=36 umnožaka 9.
2) Neka je ova formula tačna za n = k, tj. k 3 +(k+1) 3 +(k+2) 3 je višekratnik broja 9.
3) Dokažimo da je formula tačna i za n = k + 1, tj. (k+1) 3 +(k+2) 3 +(k+3) 3 je višekratnik broja 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).
Rezultirajući izraz sadrži dva člana, od kojih je svaki djeljiv sa 9, pa je zbir djeljiv sa 9.
4) Oba uslova principa matematičke indukcije su zadovoljena, dakle, rečenica je tačna za sve vrednosti n.
Primjer 3. Dokažite da je za bilo koji prirodan broj n broj 3 2n+1 +2 n+2 djeljiv sa 7.
dokaz:
1) Provjerimo da li je ova formula tačna za n = 1: 3 2*1+1 +2 1+2 = 3 3 +2 3 =35, 35 je višekratnik broja 7.
2) Neka ova formula vrijedi za n = k, tj. 3 2 k +1 +2 k +2 podijeljeno je sa 7.
3) Dokažimo da je formula tačna i za n = k + 1, tj.
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. k. (3 2 k +1 +2 k +2) 9 je podijeljeno sa 7, a 7 2 k +2 podijeljeno sa 7, tada se njihova razlika podijeli sa 7.
4) Oba uslova principa matematičke indukcije su zadovoljena, dakle, rečenica je tačna za sve vrednosti n.
Mnogi dokazni problemi u teoriji djeljivosti prirodnih brojeva mogu se zgodno riješiti metodom matematičke indukcije; čak se može reći da je rješavanje problema ovom metodom potpuno algoritamsko; dovoljno je izvršiti 4 osnovna koraka. Ali ova metoda se ne može nazvati univerzalnom, jer ima i nedostataka: prvo, može se dokazati samo na skupu prirodnih brojeva, a drugo, može se dokazati samo za jednu varijablu.
Za razvoj logičkog mišljenja i matematičke kulture, ovaj metod je neophodan alat, jer je veliki ruski matematičar A. N. Kolmogorov rekao: „Razumevanje i sposobnost pravilne primene principa matematičke indukcije dobar je kriterijum logičke zrelosti, koji je apsolutno neophodno za jednog matematičara.”
književnost:
1. Vilenkin N. Ya. Induction. Kombinatorika. - M.: Obrazovanje, 1976. - 48 str.
2. Genkin L. O matematičkoj indukciji. - M., 1962. - 36 str.
3. Solominsky I. S. Metoda matematičke indukcije. - M.: Nauka, 1974. - 63 str.
4. Sharygin I.F. Fakultativni predmet iz matematike: Rešavanje zadataka: Udžbenik za 10. razred. školski prosjek - M.: Obrazovanje, 1989. - 252 str.
5. Shen A. Matematička indukcija. - M.: MTsNMO, 2007. - 32 str.
METODA MATEMATIČKE INDUKCIJE
Reč indukcija na ruskom znači vođenje, a zaključci zasnovani na zapažanjima, eksperimentima, odnosno nazivaju se induktivnim. dobijeno zaključivanjem od posebnog do opšteg.
Na primjer, svaki dan opažamo da Sunce izlazi sa istoka. Stoga, možete biti sigurni da će se sutra pojaviti na istoku, a ne na zapadu. Ovaj zaključak izvodimo ne pribjegavajući bilo kakvim pretpostavkama o razlogu kretanja Sunca po nebu (štaviše, ovo kretanje se pokazalo očiglednim, budući da se globus zapravo kreće). Pa ipak, ovaj induktivni zaključak ispravno opisuje zapažanja koja ćemo napraviti sutra.
Uloga induktivnih zaključaka u eksperimentalnim naukama je veoma velika. Oni daju one odredbe iz kojih se zatim izvode daljnji zaključci putem dedukcije. I iako se teorijska mehanika zasniva na tri Newtonova zakona kretanja, sami su ti zakoni bili rezultat dubokog razmišljanja kroz eksperimentalne podatke, posebno Keplerove zakone planetarnog kretanja, koje je izveo iz obrade višegodišnjih zapažanja danskog astronoma Tychoa. Brahe. Pokazalo se da su posmatranje i indukcija korisni u budućnosti za razjašnjavanje napravljenih pretpostavki. Nakon Michelsonovih eksperimenata o mjerenju brzine svjetlosti u pokretnom mediju, pokazalo se da je potrebno razjasniti zakone fizike i stvoriti teoriju relativnosti.
U matematici je uloga indukcije u velikoj mjeri u tome što ona leži u osnovi odabrane aksiomatike. Nakon što je dugogodišnja praksa pokazala da je prava staza uvijek kraća od zakrivljene ili izlomljene, bilo je prirodno formulirati aksiom: za bilo koje tri tačke A, B i C nejednakost
Koncept praćenja, koji je osnova aritmetike, takođe se pojavio iz posmatranja formiranja vojnika, brodova i drugih uređenih skupova.
Ne treba, međutim, misliti da se time iscrpljuje uloga indukcije u matematici. Naravno, ne bismo trebali eksperimentalno testirati teoreme logički izvedene iz aksioma: ako tokom izvođenja nisu napravljene nikakve logičke greške, onda su istinite u onoj mjeri u kojoj su aksiomi koje smo prihvatili istiniti. Ali iz ovog sistema aksioma može se izvesti mnogo tvrdnji. A izbor onih tvrdnji koje treba dokazati opet se predlaže indukcijom. To vam omogućava da odvojite korisne teoreme od beskorisnih, ukazuje na to koje se teoreme mogu pokazati istinitima, pa čak i pomaže da se ocrta put dokaza.
Suština metode matematičke indukcije
U mnogim granama aritmetike, algebre, geometrije i analize potrebno je dokazati istinitost rečenica A(n) u zavisnosti od prirodne varijable. Dokaz istinitosti tvrdnje A(n) za sve vrijednosti varijable često se može izvesti metodom matematičke indukcije, koja se zasniva na sljedećem principu.
Propozicija A(n) smatra se istinitom za sve prirodne vrijednosti varijable ako su ispunjena sljedeća dva uvjeta:
Propozicija A(n) je tačna za n=1.
Iz pretpostavke da je A(n) tačno za n=k (gde je k bilo koji prirodan broj), sledi da je tačno za sledeću vrednost n=k+1.
Ovaj princip se naziva principom matematičke indukcije. Obično se bira kao jedan od aksioma koji definiraju prirodne nizove brojeva i stoga se prihvaća bez dokaza.
Metoda matematičke indukcije podrazumijeva sljedeću metodu dokaza. Ako želite dokazati istinitost rečenice A(n) za svo prirodno n, onda, prvo, trebate provjeriti istinitost tvrdnje A(1) i, drugo, pretpostaviti istinitost iskaza A(k), pokušajte dokazati da je izjava A(k +1) tačna. Ako se to može dokazati, a dokaz ostaje važeći za svaku prirodnu vrijednost k, tada se, u skladu s principom matematičke indukcije, tvrdnja A(n) priznaje kao tačna za sve vrijednosti n.
Metoda matematičke indukcije se široko koristi u dokazivanju teorema, identiteta, nejednakosti, u rješavanju problema djeljivosti, u rješavanju nekih geometrijskih i mnogih drugih problema.
Metoda matematičke indukcije u rješavanju zadataka na
djeljivost
Koristeći metodu matematičke indukcije, možete dokazati različite tvrdnje o djeljivosti prirodnih brojeva.
Sljedeća tvrdnja se može dokazati relativno jednostavno. Pokažimo kako se to dobija metodom matematičke indukcije.
Primjer 1. Ako je n prirodan broj, tada je broj paran.
Kada je n=1 naša izjava je tačna: - paran broj. Pretpostavimo da je to paran broj. Budući da je 2k paran broj, onda 
čak. Dakle, paritet je dokazan za n=1, paritet se izvodi iz parnosti 
.To znači da je paran za sve prirodne vrijednosti n.
Primjer 2.Dokažite istinitost rečenice
A(n)=(broj 5 je višekratnik broja 19), n je prirodan broj.
Rješenje.
Izjava A(1)=(broj djeljiv sa 19) je tačna.
Pretpostavimo da je za neku vrijednost n=k
A(k)=(broj djeljiv sa 19) je istina. Onda, pošto
Očigledno je i A(k+1) tačno. Zaista, prvi član je djeljiv sa 19 zbog pretpostavke da je A(k) istinit; drugi član je također djeljiv sa 19 jer sadrži faktor 19. Oba uslova principa matematičke indukcije su zadovoljena, dakle, tvrdnja A(n) je tačna za sve vrijednosti n.
Primjena metode matematičke indukcije na
sumiranje serije
Primjer 1.Dokazati formulu
, n je prirodan broj.
Rješenje.
Kada je n=1, obje strane jednakosti prelaze na jednu i, prema tome, prvi uvjet principa matematičke indukcije je zadovoljen.
Pretpostavimo da je formula tačna za n=k, tj.
.
Dodajmo objema stranama ove jednakosti i transformirajmo desnu stranu. Onda dobijamo
Dakle, iz činjenice da je formula tačna za n=k, sledi da je tačna i za n=k+1. Ova izjava je tačna za bilo koju prirodnu vrijednost k. Dakle, i drugi uslov principa matematičke indukcije je takođe zadovoljen. Formula je dokazana.
Primjer 2.Dokazati da je zbroj prvih n brojeva prirodnog niza jednak .
Rješenje.
Označimo traženi iznos, tj. 
.
Kada je n=1 hipoteza je tačna.
Neka 
. Pokažimo to 
.
Zaista,
Problem je riješen.
Primjer 3.Dokažite da je zbroj kvadrata prvih n brojeva prirodnog niza jednak 
.
Rješenje.
Neka .
.
Pretvarajmo se to 
. Onda
I na kraju.
Primjer 4. Dokaži to.
Rješenje.
Ako onda
Primjer 5. Dokaži to
Rješenje.
Kada je n=1 hipoteza je očigledno tačna.
Neka .
Dokažimo to.
stvarno,
Primjeri primjene metode matematičke indukcije na
dokaz nejednakosti
Primjer 1.Dokazati da je za bilo koji prirodan broj n>1
.
Rješenje.
Označimo lijevu stranu nejednakosti sa .
Dakle, za n=2 nejednakost je tačna.
Neka za neki k. Hajde da dokažemo da onda i . Imamo 
, .
Upoređujući i , imamo 
, tj. 
.
Za svaki pozitivan cijeli broj k, desna strana posljednje jednakosti je pozitivna. Zbog toga . Ali to takođe znači.
Primjer 2.Pronađite grešku u obrazloženju.
Izjava. Za bilo koji prirodan broj n nejednakost je tačna.
Dokaz.
. (1)
Dokažimo da tada nejednakost vrijedi i za n=k+1, tj.
.
Zaista, ne manje od 2 za bilo koji prirodni k. Dodajmo lijevoj strani nejednakosti (1) i desnoj strani 2. Dobijamo fer nejednakost, ili 
. Tvrdnja je dokazana.
Primjer 3.Dokaži to 
, gdje je >-1, , n prirodni broj veći od 1.
Rješenje.
Za n=2 nejednakost je tačna, jer .
Neka je nejednakost tačna za n=k, gdje je k neki prirodni broj, tj.
. (1)
Pokažimo da tada nejednakost vrijedi i za n=k+1, tj.
. (2)
Zaista, po uvjetu, , Stoga je nejednakost istinita
, (3)
dobijeno iz nejednakosti (1) množenjem svakog dijela sa . Prepišimo nejednačinu (3) na sljedeći način: . Odbacivanjem pozitivnog člana na desnoj strani posljednje nejednakosti dobijamo pravednu nejednakost (2).
Primjer 4. Dokaži to
(1)
gdje je , , n prirodni broj veći od 1.
Rješenje.
Za n=2 nejednakost (1) poprima oblik
. (2)
Budući da je , tada je nejednakost istinita
. (3)
Dodavanjem svakom dijelu nejednakosti (3) dobijamo nejednakost (2).
Ovo dokazuje da je za n=2 nejednakost (1) tačna.
Neka je nejednakost (1) tačna za n=k, gdje je k neki prirodni broj, tj.
. (4)
Dokažimo da tada nejednakost (1) mora biti tačna i za n=k+1, tj.
(5)
Pomnožimo obje strane nejednakosti (4) sa a+b. Budući da, po uvjetu, , dobivamo sljedeću pravednu nejednakost:
. (6)
Da bi se dokazala valjanost nejednakosti (5), dovoljno je to pokazati
, (7)
ili, šta je isto,
. (8)
Nejednakost (8) je ekvivalentna nejednakosti
. (9)
Ako , Tada , I na lijevoj strani nejednakosti (9) imamo proizvod dva pozitivna broja. Ako , Tada , I na lijevoj strani nejednakosti (9) imamo proizvod dva negativna broja. U oba slučaja, nejednakost (9) je tačna.
Ovo dokazuje da valjanost nejednakosti (1) za n=k implicira njenu valjanost za n=k+1.
Metoda matematičke indukcije primijenjena na druge
zadataka
Najprirodnija primena metode matematičke indukcije u geometriji, bliska upotrebi ove metode u teoriji brojeva i algebri, jeste njena primena u rešavanju problema geometrijskog proračuna. Pogledajmo nekoliko primjera.
Primjer 1.Izračunaj stranicu pravilnog kvadrata upisanog u krug polumjera R.
Rješenje.
Kada je n=2 tačno 2 n - kvadrat je kvadrat; njegovu stranu. Nadalje, prema formuli udvostručavanja
nalazimo da je stranica pravilnog osmougla 
, strana pravilnog šestougla 
, strana pravilnog trougla od trideset dva 
. Stoga možemo pretpostaviti da je strana ispravnog upisanog 2 n - kvadrat za bilo koji jednak
. (1)
Pretpostavimo da je stranica pravilnog upisanog kvadrata izražena formulom (1). U ovom slučaju, prema formuli udvostručavanja
,
odakle slijedi da formula (1) vrijedi za sva n.
Primjer 2.Na koliko trouglova se n-ugao (ne nužno konveksan) može podijeliti svojim disjunktnim dijagonalama?
Rješenje.
Za trokut, ovaj broj je jednak jedan (u trouglu se ne može povući niti jedna dijagonala); za četvorougao ovaj broj je očigledno dva.
Pretpostavimo da već znamo da je svaki k-ugao, gdje je k
A n
A 1 A 2
Neka je A 1 A k jedna od dijagonala ove particije; ona dijeli n-ugao A 1 A 2 ...A n na k-ugao A 1 A 2 ...A k i (n-k+2)-ugao A 1 A k A k+1 .. .A n . Zbog napravljene pretpostavke, ukupan broj trouglova u particiji će biti jednak
(k-2)+[(n-k+2)-2]=n-2;
Dakle, naša tvrdnja je dokazana za sve n.
Primjer 3.Navedite pravilo za izračunavanje broja P(n) načina na koje se konveksni n-ugao može podijeliti na trouglove disjunktnim dijagonalama.
Rješenje.
Za trougao, ovaj broj je očigledno jednak jedan: P(3)=1.
Pretpostavimo da smo već odredili brojeve P(k) za sve k
R(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n -1).
Koristeći ovu formulu dosljedno dobijamo:
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.
Također možete rješavati probleme sa grafovima metodom matematičke indukcije.
Neka na ravni postoji mreža pravih koje spajaju neke tačke i nemaju druge tačke. Takvu mrežu linija nazvat ćemo mapom, kojoj su date tačke kao vrhovi, segmenti krivulja između dva susjedna vrha - granice karte, dijelovi ravni na koje je podijeljena granicama - zemlje karte.
Neka se u avionu da neka karta. Reći ćemo da je ispravno obojena ako je svaka njena država obojena određenom bojom, a bilo koje dvije zemlje koje imaju zajedničku granicu obojene su različitim bojama.
Primjer 4.Na ravni ima n krugova. Dokažite da za bilo koji raspored ovih krugova, mapa koju oni formiraju može biti ispravno obojena s dvije boje.
Rješenje.
Za n=1 naša izjava je očigledna.
Pretpostavimo da je naša tvrdnja tačna za bilo koju mapu koju čini n krugova, i neka postoji n+1 krugova na ravni. Uklanjanjem jednog od ovih krugova dobijamo mapu koja se, na osnovu postavljene pretpostavke, može ispravno obojati sa dve boje, na primer crnom i belom.
Lekcija #50
Tema lekcije : Metoda matematičke indukcije.
Svrha lekcije: Upoznajte se sasuštinu metode matematičke indukcije, naučite da primjenjujete ovu metodu prilikom rješavanja problema dokazivanja, nastavite da razvijate računske vještine i nastavite s razvojem matematičke pismenosti.
Tokom nastave.
Organiziranje vremena. Postavljanje ciljeva časa
Aktivacija osnovnih znanja.
Definicija geometrijske progresije, formula za n-ti član geometrijske progresije.
Ponovite formulu za zbir prvih n članova aritmetičke progresije.
Ponovite formulu za zbir beskonačno opadajuće geometrijske progresije
3. Učenje novog gradiva
Prilikom rješavanja mnogih zadataka, prilikom dokazivanja valjanosti matematičkih tvrdnji, kao i kod izvođenja formula, često se koristi rezonovanje, tzv.metodom matematičke indukcije.
Na primjer, koristili ste ovu vrstu zaključivanja kada ste izveli formulunth člana, kao i pri izvođenju formule za zbir prvognčlanovi aritmetičke i geometrijske progresije.
Suština ove metode je sljedeća: ako trebate utvrditi valjanost neke tvrdnje u kojoj se pojavljuje prirodni brojn, To:
1) proverava se da li nameravana izjava važi za određenu vrednostn(na primjer zan=1).
2) pretpostavlja se da je izjava tačna za neku proizvoljnu vrijednostn = k , a dokazano je da i u ovom slučaju vrijedi zan = k + 1. Iz ovoga zaključujemo da je izjava tačna za bilo koju vrijednostn, jer je njegova pravednost otkrivena kadan=1, a prema onome što je dokazano važi i zan= 2, a ovo je tačno zan= 2, onda je tačno i zan= 3, itd.
Pogledajmo sada primjere korištenja ove metode.
Primjer 1. Dokažimo to za svaki prirodninpostoji jednakost
Formula je ispravna zan= 1, pošto:
Pretpostavimo da je formula tačna zan = k .
Dokažimo da je i u ovom slučaju tačno zan = k+ 1, tj.
Direktna provjera je pokazala da je formula tačna kadan =1; stoga će važiti i zan= 2, pa prema tome nan= 3, dakle, atn = 4 i općenito za bilo koji prirodnin.
4.Rješavanje problema
№249(a)
U ovom zadatku morate dokazati formulun – thčlan aritmetičke progresije metodom matematičke indukcije
Atn=1 imamo a 1 =a 1.
Pretpostavimo da je ova formula tačna zakth pojam, tj. jednakost a k = a 1 + d( k-1)
Dokažimo da je i u ovom slučaju ova formula tačna za (k+1)ti član. stvarno,
A k +1 = a 1 + d( k+1-1) = a 1 + dk
S druge strane, po definiciji, arif. prog. A k +1 = A k + d
Pošto su leve strane poslednja dva izraza jednake =, a desne strane jednake:
A k + d= a 1 + dkili a k = a 1 + d( k-1)
Rezultirajuća tačna jednakost nam omogućava da kažemo da je formulanth član aritmetičke progresije je pogodan za bilo koji prirodnin
№ 255
Dokažimo da je broj 11 n+1 +12 2 n -1 za sve prirodne vrednostindjeljivo sa 133
Atn=1 imamo 11 1+1 +12 2*1-1 =133, 133 podeljeno sa 133
Pretpostavimo da kadan= kiznos 11 k +1 +12 2 k -1 djeljivo sa 133
Dokažimo da je ovaj zbir djeljiv sa 133 atn= k+1, tj. jedanaest k +2 +12 2 k +1 djeljivo sa 133
11 k+2 +12 2k+1 =11*11 k +1 +144*12 k-1 =11*11 k +1 +11*12 2k-1 +133*12 2k-1 =11(11 k+1 +12 2k-1 )+133*12 2k-1
Svaki član dobijenog zbira podijeljen je sa 133. Dakle, 11 k +2 +12 2 k +1 takođe podeliti sa 133.
5. Refleksija
6. Podešavanje D/z
§15 rješenje br. 251
Indukcija je metoda dobijanja opšte tvrdnje iz određenih zapažanja. U slučaju kada se matematička izjava odnosi na konačan broj objekata, to se može dokazati testiranjem za svaki objekt. Na primjer, izjava: “Svaki dvocifreni paran broj je zbir dvaju prostih brojeva” slijedi iz niza jednakosti koje je sasvim izvodljivo utvrditi:
10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.
Metoda dokaza u kojoj se tvrdnja provjerava za konačan broj slučajeva koji iscrpljuju sve mogućnosti naziva se potpuna indukcija. Ova metoda se koristi relativno rijetko, jer se matematički iskazi po pravilu ne odnose na konačne, već na beskonačne skupove objekata. Na primjer, iskaz o parnim dvocifrenim brojevima koji je gore dokazan potpunom indukcijom samo je poseban slučaj teoreme: "Svaki paran broj je zbir dvaju prostih brojeva." Ova teorema još nije dokazana ili opovrgnuta.
Matematička indukcija je metoda dokazivanja određene tvrdnje za bilo koji prirodni broj n zasnovana na principu matematičke indukcije: „Ako je tvrdnja tačna za n=1 i njena valjanost za n=k implicira valjanost ove tvrdnje za n=k +1, onda je tačno za sve n " Metoda dokaza matematičkom indukcijom je sljedeća:
1) baza indukcije: dokazuju ili direktno provjeravaju valjanost iskaza za n=1 (ponekad n=0 ili n=n 0);
2) korak indukcije (prijelaz): pretpostavljaju valjanost iskaza za neki prirodni broj n=k i na osnovu ove pretpostavke dokazuju valjanost iskaza za n=k+1.
Problemi sa rešenjima
1. Dokažite da je za bilo koji prirodan broj n broj 3 2n+1 +2 n+2 djeljiv sa 7.
Označimo A(n)=3 2n+1 +2 n+2.
Indukciona baza. Ako je n=1, onda je A(1)=3 3 +2 3 =35 i, očigledno, deljiv je sa 7.
Indukciona pretpostavka. Neka je A(k) deljivo sa 7.
Indukcijski prijelaz. Dokažimo da je A(k+1) djeljivo sa 7, odnosno valjanost iskaza problema za n=k.
A(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.
Posljednji broj je djeljiv sa 7, jer je razlika dva cijela broja djeljiva sa 7. Dakle, 3 2n+1 +2 n+2 je djeljivo sa 7 za bilo koji prirodan broj n.
2. Dokažite da je za bilo koji prirodan broj n broj 2 3 n +1 djeljiv sa 3 n+1 i nije djeljiv sa 3 n+2.
Uvedemo oznaku: a i =2 3 i +1.
Za n=1 imamo, i 1 =2 3 +1=9. Dakle, 1 je deljivo sa 3 2 i nije deljivo sa 3 3.
Neka je za n=k broj a k djeljiv sa 3 k+1 i nije djeljiv sa 3 k+2, odnosno a k =2 3 k +1=3 k+1 m, gdje m nije djeljiv sa 3. Tada
i 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· ((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čigledno, k+1 je djeljiv sa 3 k+2 i nije djeljiv sa 3 k+3.
Prema tome, tvrdnja je dokazana za bilo koji prirodan broj n.
3. Poznato je da je x+1/x cijeli broj. Dokažite da je x n +1/x n također cijeli broj za bilo koji cijeli broj n.
Hajde da uvedemo notaciju: a i =h i +1/h i i odmah primetimo da je a i =a –i, pa ćemo nastaviti da govorimo o prirodnim indeksima.
Napomena: a 1 je po konvenciji cijeli broj; i 2 je cijeli broj, jer je a 2 = (a 1) 2 –2; i 0 =2.
Pretpostavimo da je a k cijeli broj za bilo koji prirodan broj k koji ne prelazi n. Tada je a 1 ·a n cijeli broj, ali a 1 ·a n =a n+1 +a n–1 i a n+1 =a 1 ·a n –a n–1 . Međutim, n–1, prema hipotezi indukcije, je cijeli broj. To znači da je n+1 također cijeli broj. Dakle, x n +1/x n je cijeli broj za bilo koji cijeli broj n, što je trebalo dokazati.
4. Dokazati da je za bilo koji prirodni broj n veći od 1 dvostruka nejednakost tačna
5. Dokazati da je za prirodne n > 1 i |x|
(1–x)n +(1+x)n
Za n=2 nejednakost je tačna. stvarno,
(1–x) 2 +(1+x) 2 = 2+2 x 2
Ako je nejednakost tačna za n=k, onda za n=k+1 imamo
(1–x) k+1 +(1+x) k+1
Nejednakost je dokazana za bilo koji prirodan broj n > 1.
6. Na ravni postoji n krugova. Dokažite da za bilo koji raspored ovih krugova, mapa koju oni formiraju može biti ispravno obojena s dvije boje.
Koristimo metodu matematičke indukcije.
Za n=1 izjava je očigledna.
Pretpostavimo da je tvrdnja tačna za bilo koju mapu formiranu od n krugova, i neka postoji n+1 krugova na ravni. Uklanjanjem jednog od ovih krugova dobijamo mapu koja se, zbog postavljene pretpostavke, može ispravno obojati u dvije boje (vidi prvu sliku ispod).
Zatim vratimo odbačeni krug i na jednoj njegovoj strani, na primjer unutra, promijenimo boju svake oblasti u suprotnu (vidi drugu sliku). Lako je vidjeti da ćemo u ovom slučaju dobiti kartu ispravno obojenu u dvije boje, ali tek sada za n+1 krugova, što je i trebalo dokazati.
7. Konveksni poligon ćemo nazvati "lijepim" ako su ispunjeni sljedeći uslovi:
1) svaki njegov vrh je obojen u jednu od tri boje;
2) bilo koja dva susedna vrha su obojena različitim bojama;
3) najmanje jedan vrh poligona je obojen u svaku od tri boje.
Dokažite da se bilo koji lijepi n-ugao može presjeći disjunktivnim dijagonalama u "lijepe" trouglove.
Koristimo metodu matematičke indukcije.
Indukciona baza. Sa najmanjim mogućim n=3, izjava problema je očigledna: vrhovi „lijepog“ trougla su obojeni u tri različite boje i nisu potrebni rezovi.
Indukciona pretpostavka. Pretpostavimo da je izjava problema tačna za bilo koji „lijepi“ n-ugao.
Indukcioni korak. Razmotrimo proizvoljan “lijepi” (n+1)-ugao i dokažimo, koristeći hipotezu indukcije, da se određenim dijagonalama može rezati u “lijepe” trouglove. Označimo sa A 1, A 2, A 3, ... A n, A n+1 uzastopne vrhove (n+1)-ugla. Ako je samo jedan vrh (n+1)-ugla obojen u bilo koju od tri boje, onda povezivanjem ovog vrha dijagonalama sa svim vrhovima koji mu nisu susjedni, dobijamo potrebnu particiju (n+1) )-gon u "lijepe" trouglove.
Ako su najmanje dva vrha (n+1)-ugla obojena u svaku od tri boje, tada boju temena A 1 označavamo brojem 1, a boju temena A 2 brojem 2. Neka je k najmanji broj takav da je vrh A k obojen u treću boju. Jasno je da je k > 2. Odsjecimo trougao A k–2 A k–1 A k od (n+1)-ugla sa dijagonalom A k–2 A k. U skladu sa izborom broja k, svi vrhovi ovog trougla su obojeni u tri različite boje, odnosno ovaj trougao je „prelep“. Konveksni n-ugao A 1 A 2 ... A k–2 A k A k+1 ... A n+1 , koji ostaje, takođe će, na osnovu induktivne pretpostavke, biti „lep“, što znači podijeljen je na “lijepe” trouglove, koje je i trebalo dokazati.
8. Dokazati da je u konveksnom n-ugaoniku nemoguće izabrati više od n dijagonala tako da bilo koje dvije od njih imaju zajedničku tačku.
Provedimo dokaz metodom matematičke indukcije.
Dokažimo opštiju tvrdnju: u konveksnom n-ugaoniku nemoguće je izabrati više od n stranica i dijagonala tako da bilo koje dvije od njih imaju zajedničku tačku. Za n = 3 izjava je očigledna. Pretpostavimo da je ova tvrdnja tačna za proizvoljan n-ugao i, koristeći ovo, dokazaćemo njegovu validnost za proizvoljan (n+1)-ugao.
Pretpostavimo da ova izjava nije tačna za (n+1)-ugao. Ako iz svakog vrha (n+1)-ugla ne izlazi više od dvije odabrane strane ili dijagonale, tada se ukupno ne bira više od n+1 njih. Dakle, iz nekog vrha A postoje najmanje tri odabrane stranice ili dijagonale AB, AC, AD. Neka AC leži između AB i AD. Budući da bilo koja strana ili dijagonala koja izlazi iz tačke C i koja nije CA ne može istovremeno presecati AB i AD, samo jedna odabrana dijagonala CA izlazi iz tačke C.
Odbacivanjem tačke C zajedno sa dijagonalom CA, dobijamo konveksni n-ugao u kojem je odabrano više od n strana i dijagonala, od kojih bilo koje dve imaju zajedničku tačku. Tako dolazimo do kontradikcije sa pretpostavkom da je tvrdnja tačna za proizvoljan konveksni n-ugao.
Dakle, za (n+1)-ugao izjava je tačna. Prema principu matematičke indukcije, tvrdnja je tačna za svaki konveksni n-ugao.
9. U ravni ima n pravih, od kojih dvije nisu paralelne niti tri prolaze kroz istu tačku. Na koliko dijelova ove prave dijele ravan?
Koristeći elementarne crteže, možete lako provjeriti da li jedna ravna linija dijeli ravan na 2 dijela, dvije prave na 4 dijela, tri prave na 7 dijelova i četiri prave na 11 dijelova.
Označimo sa N(n) broj dijelova na koje n pravih dijele ravan. Može se primijetiti da
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 prirodno pretpostaviti
N(n)=N(n–1)+n=2+2+3+4+5+…+n,
ili, kako je lako utvrditi, koristeći formulu za zbir prvih n članova aritmetičke progresije,
N(n)=1+n(n+1)/2.
Dokažimo validnost ove formule metodom matematičke indukcije.
Za n=1 formula je već provjerena.
Nakon indukcione pretpostavke, razmatramo k+1 linija koje zadovoljavaju uslove problema. Odaberimo k pravih od njih na proizvoljan način. Po hipotezi indukcije, oni će ravan podijeliti na 1+ k(k+1)/2 dijela. Preostala (k+1)-ta prava će biti podijeljena sa odabranih k pravih na k+1 dijelova i stoga će prolaziti duž (k+1)-og dijela na koji je ravan već podijeljena, a svaki ovih dijelova će se podijeliti na 2 dijela, odnosno dodati će se još k+1 dio. dakle,
N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,
Q.E.D.
10. U izrazu x 1: x 2: ... : x n, zagrade se stavljaju da naznače redoslijed radnji, a rezultat se piše kao razlomak:
(u ovom slučaju, svako od slova x 1, x 2, ..., x n je ili u brojiocu razlomka ili u nazivniku). Koliko se različitih izraza može dobiti na ovaj način sa svim mogućim načinima postavljanja zagrada?
Prije svega, jasno je da će u rezultirajućem razlomku x 1 biti u brojiocu. Gotovo je isto tako očigledno da će x 2 biti u nazivniku bez obzira na to kako su postavljene zagrade (znak podjele ispred x 2 odnosi se ili na sam x 2 ili na neki izraz koji sadrži x 2 u brojiocu).
Može se pretpostaviti da se sva ostala slova x 3, x 4, ..., x n mogu nalaziti u brojniku ili nazivniku na potpuno proizvoljan način. Iz toga slijedi da ukupno možete dobiti 2 n–2 razlomka: svako od n–2 slova x 3, x 4, ..., x n može se pojaviti nezavisno od ostalih u brojniku ili nazivniku.
Dokažimo ovu tvrdnju indukcijom.
Sa n=3 možete dobiti 2 razlomka:
tako da je izjava tačna.
Pretpostavimo da je to tačno za n=k i dokažimo to za n=k+1.
Neka se izraz x 1:x 2: ... :x k nakon nekog postavljanja zagrada zapiše u obliku određenog razlomka Q. Ako u ovom izrazu umjesto x k zamijenimo x k:x k+1, tada će x k biti na istom mestu kao što je bilo u razlomku Q, a x k+1 neće biti tamo gde je bilo x k (ako je x k bilo u nazivniku, onda će x k+1 biti u brojiocu i obrnuto).
Sada ćemo dokazati da možemo dodati x k+1 na isto mjesto gdje se nalazi x k. U razlomku Q, nakon postavljanja zagrada, nužno će biti izraz oblika q:x k, gdje je q slovo x k–1 ili neki izraz u zagradi. Zamjenom q:x k izrazom (q:x k):x k+1 =q:(x k ·x k+1), očito ćemo dobiti isti razlomak Q, gdje umjesto x k postoji x k ·x k+1 .
Dakle, broj svih mogućih razlomaka u slučaju n=k+1 je 2 puta veći nego u slučaju n=k i jednak je 2 k–2 ·2=2 (k+1)–2. Time je izjava dokazana.
Odgovor: 2 n–2 razlomka.
Problemi bez rješenja
1. Dokažite da je za bilo koje prirodno n:
a) broj 5 n –3 n +2n je djeljiv sa 4;
b) broj n 3 +11n je djeljiv sa 6;
c) broj 7 n +3n–1 je djeljiv sa 9;
d) broj 6 2n +19 n –2 n+1 je djeljiv sa 17;
e) broj 7 n+1 +8 2n–1 je djeljiv sa 19;
e) broj 2 2n–1 –9n 2 +21n–14 je djeljiv sa 27.
2. Dokazati da je (n+1)·(n+2)· …·(n+n) = 2 n ·1·3·5·…·(2n–1).
3. Dokazati nejednakost |sin nx| n|sin x| za bilo koji prirodni n.
4. Pronađite prirodne brojeve a, b, c koji nisu djeljivi sa 10 i takve da za bilo koje prirodno n brojevi a n + b n i c n imaju iste posljednje dvije cifre.
5. Dokažite da ako n tačaka ne leže na istoj pravoj, onda među pravima koje ih spajaju ima najmanje n različitih.
