Primjena metode matematičke indukcije na rješavanje problema o djeljivosti prirodnih brojeva. Metoda matematičke indukcije i njena primjena u rješavanju problema

Tekst rada je objavljen bez slika i formula.
Puna verzija rada dostupna je na kartici "Radni fajlovi" u PDF formatu

Uvod

Ova tema je relevantna, jer ljudi svakodnevno rješavaju različite probleme u kojima koriste različite metode rješavanja, ali postoje zadaci u kojima se ne može bez metode matematičke indukcije, pa će u takvim slučajevima znanje iz ove oblasti biti vrlo korisno.

Odabrao sam ovu temu za istraživanje jer je malo vremena posvećeno metodi matematičke indukcije u školskom programu; učenik uči površne informacije koje će mu pomoći da stekne samo opštu predstavu o ovoj metodi, ali da bi ovu teoriju proučavao u dubina, biće potreban samorazvoj. Zaista će biti korisno saznati više o ovoj temi, jer proširuje vidike osobe i pomaže u rješavanju složenih problema.

Cilj rada:

Upoznati metodu matematičke indukcije, sistematizovati znanja o ovoj temi i primeniti ih pri rešavanju matematičkih zadataka i dokazivanju teorema, opravdati i jasno pokazati praktičan značaj metode matematičke indukcije kao neophodnog faktora za rešavanje problema.

Ciljevi posla:

Analizirajte literaturu i sumirajte znanje o ovoj temi.

Razumjeti princip metode matematičke indukcije.

Istražiti primjenu metode matematičke indukcije u rješavanju problema.

Formulirajte zaključke i zaključke o obavljenom poslu.

Glavni dio studije

Istorija:

Tek krajem 19. veka javlja se standard zahteva za logičkom strogošću, koji do danas ostaje dominantan u praktičnom radu matematičara na razvoju pojedinačnih matematičkih teorija.

Indukcija je kognitivni postupak kroz koji se izjava koja ih uopštava izvodi iz poređenja postojećih činjenica.

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 vrijedi nejednakost.

Svest o metodi matematičke indukcije kao posebnoj važnoj metodi seže još od Bleza Paskala i Gersonida, iako se pojedinačni slučajevi primene nalaze u antičkim vremenima kod Prokla i Euklida. Savremeni naziv za metodu uveo je De Morgan 1838.

Metoda matematičke indukcije može se uporediti s progresom: počinjemo od najnižeg, a kao rezultat logičkog razmišljanja dolazimo do najvišeg. Čovjek je oduvijek težio napretku, sposobnosti da logički razvija svoje misli, što znači da ga je sama priroda odredila da razmišlja induktivno.

Indukcija i dedukcija

Poznato je da postoje i posebni i opšti iskazi, a ova dva pojma se zasnivaju na prelazu iz jednog u drugi.

Dedukcija (od latinskog deductio - dedukcija) - prijelaz u procesu spoznaje iz general znanje da privatni I single. U dedukciji, opšte znanje služi kao početna tačka rasuđivanja, a za ovo opšte znanje se pretpostavlja da je „gotovo“, postojeće. Posebnost dedukcije je u tome što istinitost njenih premisa garantuje istinitost zaključka. Stoga dedukcija ima ogromnu moć uvjeravanja i široko se koristi ne samo za dokazivanje teorema u matematici, već i gdje god je potrebno pouzdano znanje.

Indukcija (od latinskog inductio - vođenje) je prijelaz u procesu spoznaje od privatni znanje da general Drugim riječima, riječ je o metodi istraživanja i spoznaje koja je povezana sa uopštavanjem rezultata opservacija i eksperimenata.Obilježje indukcije je njena vjerovatnoća, tj. Ako su početne premise tačne, zaključak indukcije je samo vjerovatno tačan, a u konačnom rezultatu može se pokazati ili istinitim ili lažnim.

Potpuna i nepotpuna indukcija

Induktivno zaključivanje je oblik apstraktnog mišljenja u kojem se misao razvija od znanja manjeg stepena uopštenosti do saznanja većeg stepena opštosti, a zaključak koji proizilazi iz premisa je pretežno verovatnoće prirode.

Tokom istraživanja saznao sam da se indukcija dijeli na dvije vrste: potpunu i nepotpunu.

Potpuna indukcija je zaključak u kojem se donosi opći zaključak o klasi predmeta na temelju proučavanja svih objekata ove klase.

Na primjer, neka je potrebno utvrditi da se svaki paran prirodan broj n unutar raspona 6≤ n≤ 18 može predstaviti kao zbir dva prosta broja. Da biste to učinili, uzmite sve takve brojeve i napišite odgovarajuća proširenja:

6=3+3; 8=5+3; 10=7+3; 12=7+5;14=7+7; 16=11+5; 18=13+5;

Ove jednakosti pokazuju da je svaki od brojeva koji nas zanimaju zaista predstavljen kao zbir dva jednostavna člana.

Razmotrimo sljedeći primjer: niz yn= n 2 +n+17; Napišimo prva četiri člana: y 1 =19; y 2 =23; y 3 =29; y 4 =37; Tada možemo pretpostaviti da se cijeli niz sastoji od prostih brojeva. Ali to nije tako, uzmimo y 16 = 16 2 +16+17=16(16+1)+17=17*17. Ovo je kompozitni broj, što znači da je naša pretpostavka netočna, tako da nepotpuna indukcija ne dovodi do potpuno pouzdanih zaključaka, već nam omogućava da formuliramo hipotezu, koja naknadno zahtijeva matematički dokaz ili pobijanje.

Metoda matematičke indukcije

Potpuna indukcija ima samo ograničenu primjenu u matematici. Mnoge zanimljive matematičke izjave pokrivaju beskonačan broj specijalnih slučajeva, a mi nismo u mogućnosti testirati za sve ove situacije, ali kako možemo testirati za beskonačan broj slučajeva? Ovu metodu su predložili B. Pascal i J. Bernoulli, ovo je metoda matematičke indukcije koja se zasniva na princip matematičke indukcije.

Ako je rečenica A(n), u zavisnosti od prirodnog broja n, tačna za n=1 i iz činjenice da je tačna za n=k (gdje je k bilo koji prirodni broj), slijedi da je istinita i za sljedeći broj n=k +1, tada je pretpostavka A(n) tačna za bilo koji prirodan broj n.

U brojnim slučajevima može biti potrebno dokazati valjanost određene tvrdnje ne za sve prirodne brojeve, već samo za n>p, gdje je p fiksni prirodni broj. U ovom slučaju, princip matematičke indukcije je formuliran na sljedeći način:

Ako je tvrdnja A(n) tačna za n=p i ako je A(k)  A(k+1) za bilo koje k>p, onda je tvrdnja A(n) tačna za bilo koje n>p.

Algoritam (sastoji se od četiri faze):

1.baza(pokazujemo da je tvrdnja koja se dokazuje istinita za neke najjednostavnije specijalne slučajeve ( P = 1));

2.pretpostavka(pretpostavljamo da je tvrdnja dokazana za prvi To slučajevi); 3 .korak(pod ovom pretpostavkom dokazujemo tvrdnju za slučaj P = To + 1); 4.izlaz (na izjava je tačna za sve slučajeve, odnosno za sve P) .

Imajte na umu da metoda matematičke indukcije ne može riješiti sve probleme, već samo probleme parametrizirane određenom varijablom. Ova varijabla se zove indukciona varijabla.

Primjena metode matematičke indukcije

Primijenimo cijelu ovu teoriju u praksi i otkrijmo u kojim se problemima koristi ova metoda.

Problemi za dokazivanje nejednakosti.

Primjer 1. Dokazati Bernoullijevu nejednakost (1+x)n≥1+n x, x>-1, n € N.

1) Za n=1 nejednakost je tačna, jer je 1+x≥1+x

2) Pretpostavimo da je nejednakost tačna za neki n=k, tj.

(1+x) k ≥1+k x.

Pomnožimo obje strane nejednakosti pozitivnim brojem 1+x, dobivamo

(1+x) k+1 ≥(1+kx)(1+ x) =1+(k+1) x + kx 2

Uzimajući u obzir da je kx 2 ≥0, dolazimo do nejednakosti

(1+x) k+1 ≥1+(k+1) x.

Dakle, iz pretpostavke da je Bernoullijeva nejednakost tačna za n=k, slijedi da je istinita za n=k+1. Na osnovu metode matematičke indukcije, može se tvrditi da Bernoullijeva nejednakost vrijedi za bilo koje n € N.

Primjer 2. Dokazati da za bilo koji prirodni broj n>1, .

Dokažimo to metodom matematičke indukcije.

Označimo lijevu stranu nejednakosti sa.

1), dakle, za n=2 vrijedi nejednakost.

2) Neka je za neki k. Dokažimo to 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 znači i. Dokazali smo valjanost nejednakosti za n=k+1, dakle, na osnovu metode matematičke indukcije, nejednakost vrijedi za bilo koji prirodni broj n>1.

Problemi za dokazivanje identiteta.

Primjer 1. Dokažite da je za bilo koji prirodan broj n tačna jednakost:

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

Neka je n=1, tada je X 1 =1 3 =1 2 (1+1) 2 /4=1.

Vidimo da je za n=1 izjava tačna.

2) Pretpostavimo da je jednakost tačna za n=kX k =k 2 (k+1) 2 /4.

3) Dokažimo istinitost ove tvrdnje za n=k+1, tj. X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k+1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4.

Iz gornjeg dokaza jasno je da je tvrdnja tačna za n=k+1, dakle, jednakost je tačna za bilo koji prirodan broj n.

Primjer 2. Dokažite da je za bilo koje prirodno n jednakost tačna

1) Provjerimo da li je ovaj identitet tačan za n = 1.; - u redu.

2) Neka je istovjetnost istinita i za n = k, tj.

3) Dokažimo da je ovaj identitet istinit i za n = k + 1, tj.;

Jer Ako je jednakost tačna za n=k i n=k+1, onda je tačna za bilo koji prirodan broj n.

Problemi sumiranja.

Primjer 1. Dokazati da je 1+3+5+…+(2n-1)=n 2.

Rješenje: 1) Imamo n=1=1 2 . Prema tome, tvrdnja je tačna za n=1, tj. A(1) je tačno.

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

Neka je k bilo koji prirodan broj i neka je izjava tačna za n=k, tj. 1+3+5+…+(2k-1)=k 2 .

Dokažimo da je tada tvrdnja tačna i za sljedeći prirodni broj n=k+1, tj. Šta

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

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

Dakle, A(k) A(k+1). Na osnovu principa matematičke indukcije, zaključujemo da je pretpostavka A(n) tačna za bilo koji n N.

Primjer 2. Dokažite formulu, n je prirodan broj.

Rješenje: Kada je n=1, obje strane jednakosti prelaze na jedan 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, onda je ova tvrdnja tačna za bilo koji prirodan broj n.

Problemi djeljivosti.

Primjer 1. Dokazati da je (11 n+2 +12 2n+1) djeljivo sa 133 bez ostatka.

Rješenje: 1) Neka je onda n=1

11 3 +12 3 =(11+12)(11 2 -132+12 2)=23× 133.

(23×133) je djeljiv sa 133 bez ostatka, što znači da je za n=1 izjava tačna;

2) Pretpostavimo da je (11 k+2 +12 2k+1) djeljivo sa 133 bez ostatka.

3) Dokažimo to u ovom slučaju

(11 k+3 +12 2k+3) je djeljivo sa 133 bez ostatka. Zaista, 11 k+3 +12 2l+3 =11×11 k+2 +

12 2 ×12 2k+1 =11× 11 k+2 +(11+133)× 12 2k+1 =11(11 k+2 +12 2k+1)+133× 12 2k+1 .

Dobijeni zbir se dijeli sa 133 bez ostatka, jer je njegov prvi član djeljiv sa 133 bez ostatka po pretpostavci, a u drugom je jedan od faktora 133.

Dakle, A(k)→ A(k+1), onda na osnovu metode matematičke indukcije, tvrdnja je tačna za bilo koje prirodno n.

Primjer 2. Dokažite da je 3 3n-1 +2 4n-3 za proizvoljan prirodan broj n djeljiv sa 11.

Rješenje: 1) Neka je n=1, tada je X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 djeljiv sa 11 bez ostatka. To znači da je za n=1 izjava tačna.

2) Pretpostavimo da je za n=k

X k =3 3k-1 +2 4k-3 je deljivo sa 11 bez ostatka.

3) Dokažimo da je tvrdnja tačna za n=k+1.

X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 *3 3k-1 +2 4 *2 4k-3 =

27 3 3k-1 +16* 2 4k-3 =(16+11)* 3 3k-1 +16* 2 4k-3 =16* 3 3k-1 +

11* 3 3k-1 +16* 2 4k-3 =16(3 3k-1 +2 4k-3)+11* 3 3k-1 .

Prvi član je djeljiv sa 11 bez ostatka, jer je 3 3k-1 +2 4k-3 djeljiv sa 11 po pretpostavci, drugi je djeljiv sa 11, jer je jedan od njegovih faktora broj 11. To znači da je zbir je djeljiv sa 11 bez ostatka za bilo koji prirodan broj n.

Problemi iz stvarnog života.

Primjer 1. Dokažite da je zbir Sn unutrašnjih uglova bilo kojeg konveksnog poligona jednak ( P- 2)π, gdje P— broj stranica ovog poligona: Sn = ( P- 2)π (1).

Ova izjava nema smisla za sve prirodne P, ali samo za P > 3, pošto je najmanji broj uglova u trouglu 3.

1) Kada P= 3 naša izjava ima oblik: S 3 = π. Ali zbir unutrašnjih uglova bilo kojeg trougla je zaista π. Stoga, kada P= 3 formula (1) je tačna.

2) Neka je ova formula tačna za n =k, odnosno S k = (k- 2)π, gdje k > 3. Dokažimo da u ovom slučaju vrijedi formula: S k+ 1 = (k- 1)π.

Neka je A 1 A 2 ... A k A k+ 1—proizvoljno konveksno ( k+ 1) -gon (Sl. 338).

Povezivanje tačaka A 1 i A k , dobijamo konveksno k-gon A 1 A 2 ... A k — 1 A k . Očigledno, zbir uglova ( k+ 1) -gon A 1 A 2 ... A k A k+ 1 je jednako zbiru uglova k-gon A 1 A 2 ... A k plus zbir uglova trougla A 1 A k A k+ 1 . Ali zbir uglova k-gon A 1 A 2 ... A k po pretpostavci jednako ( k- 2)π, i zbir uglova trougla A 1 A k A k+ 1 je jednako π. Zbog toga

S k+ 1 = S k + π = ( k- 2)π + π = ( k- 1)π.

Dakle, oba uslova principa matematičke indukcije su zadovoljena, pa je stoga formula (1) tačna za bilo koju prirodnu P > 3.

Primjer 2. Tu je i stepenište čije su sve stepenice iste. Potrebno je navesti minimalni broj pozicija koje bi garantovale mogućnost „penjanja“ na bilo koju stepenicu.

Svi se slažu da mora postojati uslov. Moramo biti u stanju da se popnemo do prve stepenice. Zatim, moraju biti u stanju da se popnu sa 1. stepenice na drugu. Zatim na drugu - na treću, itd. na n-ti korak. Naravno, sveukupno, “n” iskazi garantuju da ćemo moći doći do n-og koraka.

Pogledajmo sada pozicije 2, 3,..., n i uporedimo ih međusobno. Lako je vidjeti da svi imaju istu strukturu: ako smo došli do k koraka, onda se možemo popeti na (k+1) stepenicu. Dakle, sljedeći aksiom postaje prirodan za valjanost iskaza u zavisnosti od “n”: ako rečenica A(n), u kojoj je n prirodan broj, vrijedi za n=1 i iz činjenice da vrijedi za n=k (gdje je k bilo koji prirodan broj), slijedi da vrijedi za n=k+1, tada pretpostavka A(n) vrijedi za bilo koji prirodni broj n.

Aplikacija

Problemi primjene metode matematičke indukcije pri upisu na fakultete.

Imajte na umu da prilikom ulaska u visokoškolske ustanove postoje i problemi koji se mogu riješiti ovom metodom. Pogledajmo ih na konkretnim primjerima.

Primjer 1. Dokaži da bilo koji prirodni P jednakost je istinita

1) Kada n=1 dobijamo tačnu jednakost Sin.

2) Napravivši indukcijsku pretpostavku da kada je n= k jednakost je tačna, razmotrite zbir na lijevoj strani jednakosti za n =k+1;

3) Koristeći formule redukcije, transformiramo izraz:

Zatim, na osnovu metode matematičke indukcije, jednakost je tačna za bilo koji prirodni broj n.

Primjer 2. Dokažite da je za bilo koji prirodni broj n vrijednost izraza 4n +15n-1 višekratnik 9.

1) Sa n=1: 2 2 +15-1=18 - višekratnik od 9 (od 18:9=2)

2) Neka vrijedi jednakost za n=k: 4 k +15k-1 višestruko od 9.

3) Dokažimo da jednakost vrijedi za sljedeći broj n=k+1

4 k+1 +15(k+1)-1=4 k+1 +15k+15-1=4,4 k +60k-4-45k+18=4(4 k +15k-1)-9(5k- 2)

4(4 k +15k-1) - višekratnik od 9;

9(5k-2) - višekratnik od 9;

Posljedično, cijeli izraz 4(4 k +15k-1)-9(5k-2) je višekratnik broja 9, što je trebalo dokazati.

Primjer 3. Dokažite to za bilo koji prirodan broj P ispunjen je uslov: 1∙2∙3+2∙3∙4+…+ p(p+1)(p+2)=.

1) Provjerimo da li je ova formula tačna kada n=1: Lijeva strana = 1∙2∙3=6.

Desni deo = . 6 = 6; istina kada n=1.

2) Pretpostavimo da je ova formula tačna za n =k:

1∙2∙3+2∙3∙4+…+k(k+1)(k+2)=. S k =.

3) Dokažimo da je ova formula tačna za n =k+1:

1∙2∙3+2∙3∙4+…+(k+1)(k+2)(k+3)=.

S k+1 =.

dokaz:

Dakle, ovaj uslov je tačan u dva slučaja i dokazano je da je tačan za n =k+1, stoga je istinito za bilo koji prirodan broj P.

Zaključak

Da rezimiramo, u procesu istraživanja saznao sam šta je indukcija, koja može biti potpuna ili nepotpuna, upoznao sam se sa metodom matematičke indukcije po principu matematičke indukcije, te razmotrio mnoge probleme koristeći ovu metodu.

Saznao sam i dosta novih informacija, drugačijih od onih koje su uključene u školski program.Učeći metod matematičke indukcije koristio sam raznu literaturu, internet resurse, a konsultovao sam se i sa nastavnikom.

zaključak: Uopštivši i sistematizirajući znanje o matematičkoj indukciji, uvjerio sam se u potrebu znanja o ovoj temi u stvarnosti. Pozitivan kvalitet metode matematičke indukcije je njena široka primena u rešavanju problema: u oblasti algebre, geometrije i realne matematike. Ovo znanje takođe povećava interesovanje za matematiku kao nauku.

Uvjeren sam da će mi vještine koje sam stekao tokom rada pomoći u budućnosti.

Bibliografija

Sominsky I.S. Metoda matematičke indukcije. Popularna predavanja iz matematike, broj 3-M.: Nauka, 1974.

L. I. Golovina, I. M. Yaglom. Indukcija u geometriji. - Fizmatgiz, 1961. - T. 21. - 100 str. — (Popularna predavanja iz matematike).

Dorofejev G.V., Potapov M.K., Rozov N.Kh. Priručnik o matematici za studente (Odabrana pitanja iz osnovne matematike) - 5. izdanje, revidirano, 1976. - 638 str.

A. Shen. Matematička indukcija. - MCNMO, 2004. - 36 str.

M.L. Galitsky, A.M. Goldman, L.I. Zvavich Zbirka zadataka iz algebre: udžbenik za 8-9 razred. sa dubinom studiranje matematike 7. izd. - M.: Prosveshchenie, 2001. - 271 str.

Ma-ka-ry-chev Yu.N., Min-dyuk N.G Dodatna poglavlja za školski udžbenik al-geb-ry 9. razreda. - M.: Pro-sve-shche-nie, 2002.

Wikipedia je besplatna enciklopedija.

Ako je tvrdnja A(n) tačna za n=p i ako je A(k) ≈ A(k+1) za bilo koje k>p, onda je tvrdnja A(n) tačna za bilo koje n>p.

Dokaz metodom matematičke indukcije izvodi se na sljedeći način. Prvo, iskaz koji treba dokazati se provjerava za n=1, tj. istinitost iskaza A(1) je utvrđena. Ovaj dio dokaza naziva se baza indukcije. Zatim dolazi dio dokaza koji se naziva korak indukcije. U ovom dijelu dokazuju valjanost iskaza za n=k+1 pod pretpostavkom valjanosti iskaza za n=k (indukcijska pretpostavka), tj. dokazati da je A(k) 1 A(k+1)

Dokazati da je 1+3+5+…+(2n-1)=n 2.

1) Imamo n=1=1 2 . Prema tome, tvrdnja je tačna za n=1, tj. A(1) tačno
2) Dokažimo da je A(k) ≥ A(k+1)

Neka je k bilo koji prirodan broj i neka je izjava tačna za n=k, tj.

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

Dokažimo da je tada tvrdnja tačna i za sljedeći prirodni broj n=k+1, tj. Šta

1+3+5+…+(2k+1)=(k+1) 2 Zaista,
1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2

Dakle, A(k) 1 A(k+1). Na osnovu principa matematičke indukcije, zaključujemo da je pretpostavka A(n) tačna za bilo koje n O N

Dokaži to

1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), gdje je x br. 1

1) Za n=1 dobijamo
1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1

dakle, za n=1 formula je ispravna; A(1) tačno

2) Neka je k bilo koji prirodan broj i neka je formula tačna za n=k,
1+x+x 2 +x 3 +…+x k =(x k+1 -1)/(x-1)

Dokažimo da je onda jednakost

1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1) Zaista
1+x+x 2 +x 3 +…+x 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)

Dakle, A(k) 1 A(k+1). Na osnovu principa matematičke indukcije zaključujemo da je formula tačna za svaki prirodni broj n

Dokažite da je broj dijagonala konveksnog n-ugla n(n-3)/2

Rješenje: 1) Za n=3 tvrdnja je tačna, jer je u trouglu

A 3 =3(3-3)/2=0 dijagonala; A 2 A(3) tačno

2) Pretpostavimo da u svakom konveksnom k-ugaoniku postoje A 1 x A k =k(k-3)/2 dijagonale. A k Dokažimo da je tada u konveksnom A k+1 (k+1)-ugaoniku broj dijagonala A k+1 =(k+1)(k-2)/2.

Neka je A 1 A 2 A 3 …A k A k+1 konveksan (k+1)-ugao. Nacrtajmo dijagonalu A 1 A k u njoj. Da biste izračunali ukupan broj dijagonala ovog (k+1)-ugla, potrebno je izbrojati broj dijagonala u k-ugaoniku A 1 A 2 ...A k , dodati k-2 na rezultirajući broj, tj. treba uzeti u obzir broj dijagonala (k+1)-ugla koje izlaze iz vrha A k+1, a pored toga treba uzeti u obzir i dijagonalu A 1 A k

dakle,

G k+1 =G k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2

Dakle, A(k) 1 A(k+1). Zbog principa matematičke indukcije, tvrdnja je tačna za svaki konveksni n-ugao.

Dokažite da je za bilo koje n tačna sljedeća izjava:

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

Rješenje: 1) Neka je onda n=1

X 1 =1 2 =1(1+1)(2+1)/6=1

2) Pretpostavimo da je n=k

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

3) Razmotrimo ovu tvrdnju za n=k+1

X k+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 da je jednakost tačna za n=k+1, dakle, na osnovu metode matematičke indukcije, tvrdnja je tačna za bilo koji prirodan broj n

Dokažite da je za bilo koji prirodan broj n tačna jednakost:

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

Rješenje: 1) Neka je n=1

Tada je X 1 =1 3 =1 2 (1+1) 2 /4=1. Vidimo da je za n=1 izjava tačna.

2) Pretpostavimo da je jednakost tačna za n=k

X k =k 2 (k+1) 2 /4

3) Dokažimo istinitost ove tvrdnje za n=k+1, tj.

X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4

Iz gornjeg dokaza jasno je da je tvrdnja tačna za n=k+1, dakle, jednakost je tačna za bilo koji prirodan broj n

Dokaži to

((2 3 +1)/(2 3 -1)) ´ ((3 3 +1)/(3 3 -1)) ´ ... ´ ((n 3 +1)/(n 3 -1) )= 3n(n+1)/2(n 2 +n+1), gdje je n>2

Rješenje: 1) Za n=2 identitet izgleda ovako:

(2 3 +1)/(2 3 -1)=(3 ´2 ´3)/2(2 2 +2+1), tj. istina je
2) Pretpostavimo da je izraz tačan za n=k
(2 3 +1)/(2 3 -1) ´ … ´ (k 3 +1)/(k 3 -1)=3k(k+1)/2(k 2 +k+1)
3) Dokažimo valjanost izraza za n=k+1
(((2 3 +1)/(2 3 -1)) ´ … ´ ((k 3 +1)/(k 3 -1))) ´ (((k+1) 3 +

1)/((k+1) 3 -1))=(3k(k+1)/2(k 2 +k+1)) ´ ((k+2)((k+

1) 2 -(k+1)+1)/k((k+1) 2 +(k+1)+1))=3(k+1)(k+2)/2 ´

´ ((k+1) 2 +(k+1)+1)

Dokazali smo da je jednakost tačna za n=k+1, dakle, na osnovu metode matematičke indukcije, tvrdnja je tačna za bilo koje n>2

Dokaži to

1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3) za bilo koji prirodni broj n

Rješenje: 1) Neka je onda n=1

1 3 -2 3 =-1 3 (4+3); -7=-7
2) Pretpostavimo da je onda n=k
1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3)
3) Dokažimo istinitost ove tvrdnje za n=k+1
(1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+

+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3)

Dokazana je i valjanost jednakosti za n=k+1, pa je tvrdnja tačna za svaki prirodan broj n.

Dokažite da je identitet tačan

(1 2 /1 ´ 3)+(2 2 /3 ´ 5)+…+(n 2 /(2n-1) ´ (2n+1))=n(n+1)/2(2n+1) za bilo koji prirodni n

1) Za n=1 identitet je tačan 1 2 /1 ´ 3=1(1+1)/2(2+1)
2) Pretpostavimo da je za n=k
(1 2 /1 ´3)+…+(k 2 /(2k-1) ´ (2k+1))=k(k+1)/2(2k+1)
3) Dokažimo da je identičnost tačna za n=k+1
(1 2 /1 ´3)+…+(k 2 /(2k-1)(2k+1))+(k+1) 2 /(2k+1)(2k+3)=(k(k+ 1) )/2(2k+1))+((k+1) 2 /(2k+1)(2k+3))=((k+1)/(2k+1)) ´ ((k/2 ) +((k+1)/(2k+3)))=(k+1)(k+2) ´ (2k+1)/2(2k+1)(2k+3)=(k+1) (k+2)/2(2(k+1)+1)

Iz gornjeg dokaza jasno je da je tvrdnja tačna za bilo koji prirodan broj n.

Dokažite da je (11 n+2 +12 2n+1) deljivo sa 133 bez ostatka

Rješenje: 1) Neka je onda n=1

11 3 +12 3 =(11+12)(11 2 -132+12 2)=23 ґ 133

Ali (23 ´ 133) je deljivo sa 133 bez ostatka, što znači da je za n=1 izjava tačna; A(1) je tačno.

2) Pretpostavimo da je (11 k+2 +12 2k+1) deljivo sa 133 bez ostatka
3) Dokažimo da je u ovom slučaju (11 k+3 +12 2k+3) djeljivo sa 133 bez ostatka. Zaista
11 k+3 +12 2l+3 =11 ´ 11 k+2 +12 2 ´ 12 2k+1 =11 ´ 11 k+2 +

+(11+133) ´12 2k+1 =11(11 k+2 +12 2k+1)+133´ 12 2k+1

Dobijeni zbir se dijeli sa 133 bez ostatka, jer je njegov prvi član djeljiv sa 133 bez ostatka po pretpostavci, a u drugom je jedan od faktora 133. Dakle, A(k) 1 A(k+1). Metodom matematičke indukcije tvrdnja je dokazana

Dokazati da je za bilo koji n 7 n -1 djeljiv sa 6 bez ostatka

1) Neka je n=1, tada je X 1 =7 1 -1=6 podijeljen sa 6 bez ostatka. To znači da je za n=1 izjava tačna
2) Pretpostavimo da je kada je n=k 7 k -1 podijeljeno sa 6 bez ostatka
3) Dokažimo da je tvrdnja tačna za n=k+1

X k+1 =7 k+1 -1=7 g 7 k -7+6=7(7 k -1)+6

Prvi član je djeljiv sa 6, jer je 7 k -1 djeljivo sa 6 prema pretpostavci, a drugi član je 6. To znači da je 7 n -1 višekratnik 6 za bilo koji prirodni broj n. Metodom matematičke indukcije tvrdnja je dokazana.

Dokažite da je 3 3n-1 +2 4n-3 za proizvoljan prirodan broj n djeljiv sa 11.

1) Neka je onda n=1

X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 dijeli se sa 11 bez ostatka.

To znači da je za n=1 izjava tačna

2) Pretpostavimo da kada je n=k X k =3 3k-1 +2 4k-3 je podijeljeno sa 11 bez ostatka
3) Dokažimo da je tvrdnja tačna za n=k+1

X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 ´3 3k-1 +2 4 ´2 4k-3 =

27 ´ 3 3k-1 +16 ´ 2 4k-3 =(16+11) ´ 3 3k-1 +16 ´ 2 4k-3 =16 ´3 3k-1 +

11 ´ 3 3k-1 +16 ´ 2 4k-3 =16(3 3k-1 +2 4k-3)+11 ´3 3k-1

Dokažite da je 11 2n -1 za proizvoljni prirodan broj n djeljivo sa 6 bez ostatka

1) Neka je n=1, tada je 11 2 -1=120 deljivo sa 6 bez ostatka. To znači da je za n=1 izjava tačna
2) Pretpostavimo da je kada je n=k 1 2k -1 podijeljeno sa 6 bez ostatka
11 2(k+1) -1=121 ´ 11 2k -1=120´ 11 2k +(11 2k -1)

Oba člana su djeljiva sa 6 bez ostatka: prvi sadrži višekratnik 6, 120, a drugi je djeljiv sa 6 bez ostatka po pretpostavci. To znači da je zbir djeljiv sa 6 bez ostatka. Metodom matematičke indukcije tvrdnja je dokazana.

Dokažite da je 3 3n+3 -26n-27 za proizvoljan prirodan broj n djeljiv sa 26 2 (676) bez ostatka

Hajde da prvo dokažemo da je 3 3n+3 -1 deljivo sa 26 bez ostatka

1. Kada je n=0
3 3 -1=26 je podijeljeno sa 26
2. Pretpostavimo da je za n=k
3 3k+3 -1 je deljivo sa 26
3. Dokažimo da je tvrdnja tačna za n=k+1
3 3k+6 -1=27 ´ 3 3k+3 -1=26´ 3 3l+3 +(3 3k+3 -1) -podeljeno sa 26

Dokažimo sada tvrdnju formulisanu u iskazu problema

1) Očigledno, za n=1 izjava je tačna
3 3+3 -26-27=676
2) Pretpostavimo da je za n=k izraz 3 3k+3 -26k-27 podijeljen sa 26 2 bez ostatka
3) Dokažimo da je tvrdnja tačna za n=k+1
3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27)

Oba člana su djeljiva sa 26 2; prva je djeljiva sa 26 2 jer smo dokazali da je izraz u zagradama djeljiva sa 26, a druga je djeljiva hipotezom indukcije. Metodom matematičke indukcije tvrdnja je dokazana

Dokažite da ako je n>2 i x>0, onda je nejednakost (1+x) n >1+n ´x tačna

1) Za n=2 vrijedi nejednakost, jer
(1+x) 2 =1+2x+x 2 >1+2x

Dakle, A(2) je tačno

2) Dokažimo da je A(k) ≈ A(k+1), ako je k> 2. Pretpostavimo da je A(k) tačno, tj. da je nejednakost
(1+x) k >1+k ´x. (3)

Dokažimo da je tada i A(k+1) tačno, tj. da je nejednakost

(1+x) k+1 >1+(k+1) ´x

U stvari, množenjem obe strane nejednakosti (3) pozitivnim brojem 1+x, dobijamo

(1+x) k+1 >(1+k ´x)(1+x)

Razmotrimo desnu stranu posljednje nejednakosti; imamo

(1+k ´x)(1+x)=1+(k+1) ´x+k´ x 2 >1+(k+1) ´x

Kao rezultat, dobijamo da (1+x) k+1 >1+(k+1) ´x

Dakle, A(k) 1 A(k+1). Na osnovu principa matematičke indukcije, može se tvrditi da Bernoullijeva nejednakost vrijedi za bilo koje n> 2

Dokažite da je nejednakost (1+a+a 2) m > 1+m ´ a+(m(m+1)/2) ´ a 2 za a> 0 tačna

Rješenje: 1) Kada je m=1

(1+a+a 2) 1 > 1+a+(2/2) ½ a 2 obe strane su jednake
2) Pretpostavimo da je za m=k
(1+a+a 2) k >1+k ´ a+(k(k+1)/2) ´ a 2
3) Dokažimo da je za m=k+1 nejednakost tačna
(1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k ´ a+

+(k(k+1)/2) ´ a 2)=1+(k+1) ´ a+((k(k+1)/2)+k+1) ´ a 2 +

+((k(k+1)/2)+k) ´ a 3 +(k(k+1)/2) ´ a 4 > 1+(k+1) ´ a+

+((k+1)(k+2)/2) ´ a 2

Dokazali smo da je nejednakost tačna za m=k+1, pa prema tome, na osnovu metode matematičke indukcije, nejednakost vrijedi za bilo koji prirodni broj m

Dokažite da je za n>6 tačna nejednakost 3 n >n ´ 2 n+1

Prepišimo nejednačinu u obliku (3/2) n >2n

1. Za n=7 imamo 3 7 /2 7 =2187/128>14=2 ´ 7 nejednakost je tačna
2. Pretpostavimo da je za n=k (3/2) k >2k
3) Dokažimo nejednakost za n=k+1
3 k+1 /2 k+1 =(3 k /2 k) ´ (3/2)>2k ´ (3/2)=3k>2 (k+1)

Pošto je k>7, posljednja nejednakost je očigledna.

Na osnovu metode matematičke indukcije, nejednakost vrijedi za bilo koji prirodni broj n

Dokažite da je za n>2 nejednakost tačna

1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n)

1) Za n=3 nejednakost je tačna
1+(1/2 2)+(1/3 2)=245/180
2. Pretpostavimo da je za n=k
1+(1/2 2)+(1/3 2)+…+(1/k 2)=1,7-(1/k)
3) Dokažimo valjanost nejednakosti za n=k+1
(1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)

Dokažimo da je 1.7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1) Ы

S (1/(k+1) 2)+(1/k+1)<1/k Ы (k+2)/(k+1) 2 <1/k Ы

y k(k+2)<(k+1) 2 Ы k 2 +2k

Ovo poslednje je očigledno, i stoga

1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)<1,7-(1/k+1)

Metodom matematičke indukcije nejednakost je dokazana.

Matematička indukcija je osnova jedne od najčešćih metoda matematičkog dokaza. Uz njegovu pomoć možete dokazati većinu formula s prirodnim brojevima n, na primjer, formulu za pronalaženje zbira prvih članova progresije S n = 2 a 1 + n - 1 d 2 · n, Newtonovu binomnu formulu a + b n = C n 0 · a n · C n 1 · a n - 1 · b + . . . + C n n - 1 · a · b n - 1 + C n n · b n .

U prvom paragrafu analiziraćemo osnovne koncepte, zatim ćemo razmotriti osnove same metode, a zatim ćemo vam reći kako da je koristite za dokazivanje jednakosti i nejednakosti.

Yandex.RTB R-A-339285-1

Koncepti indukcije i dedukcije

Prvo, pogledajmo šta su indukcija i dedukcija uopšte.

Definicija 1

Indukcija je prijelaz od posebnog ka općem, i odbitak naprotiv – od opšteg ka specifičnom.

Na primjer, imamo izjavu: 254 se može podijeliti sa dva. Iz toga možemo izvući mnoge zaključke, uključujući i istinite i lažne. Na primjer, izjava da se svi cijeli brojevi koji završavaju brojem 4 mogu podijeliti sa dva bez ostatka je tačna, ali izjava da je bilo koji broj od tri znamenke djeljiv sa 2 je netačna.

Općenito, može se reći da se uz pomoć induktivnog zaključivanja iz jednog poznatog ili očiglednog zaključivanja mogu izvući mnogi zaključci. Matematička indukcija nam omogućava da utvrdimo koliko su ovi zaključci validni.

Recimo da imamo niz brojeva poput 1 1 2, 1 2 3, 1 3 4, 1 4 5, . . . , 1 n (n + 1) , gdje n označava neki prirodni broj. U ovom slučaju, kada se dodaju prvi elementi niza, dobijamo sljedeće:

S 1 = 1 1 2 = 1 2, S 2 = 1 1 2 + 1 2 3 = 2 3, S 3 = 1 1 2 + 1 2 3 + 1 3 4 = 3 4, S 4 = 1 1 · 2 + 1 2 · 3 + 1 3 · 4 + 1 4 · 5 = 4 5 , . . .

Koristeći indukciju, možemo zaključiti da je S n = n n + 1 . U trećem dijelu ćemo dokazati ovu formulu.

Šta je metoda matematičke indukcije?

Ova metoda se zasniva na istoimenom principu. Formulisan je ovako:

Definicija 2

Određena tvrdnja će biti tačna za prirodnu vrijednost n kada 1) bit će tačna za n = 1 i 2) iz činjenice da ovaj izraz vrijedi za proizvoljnu prirodnu vrijednost n = k, slijedi da će biti istinit za n = k + 1 .

Primena metode matematičke indukcije odvija se u 3 faze:

Prvo, proveravamo validnost originalne izjave u slučaju proizvoljne prirodne vrednosti od n (obično se provera radi za jedinicu).
Nakon toga provjeravamo valjanost kada je n = k.
A onda dokazujemo valjanost tvrdnje ako je n = k + 1.

Kako koristiti metodu matematičke indukcije za rješavanje nejednačina i jednačina

Uzmimo primjer o kojem smo ranije govorili.

Primjer 1

Dokazati formulu S n = 1 1 · 2 + 1 2 · 3 + . . . + 1 n (n + 1) = n n + 1 .

Rješenje

Kao što već znamo, za primjenu metode matematičke indukcije potrebno je izvršiti tri uzastopna koraka.

Prvo provjeravamo da li će ova jednakost vrijediti za n jednako jedan. Dobijamo S 1 = 1 1 · 2 = 1 1 + 1 = 1 2 . Ovde je sve tačno.
Zatim pretpostavljamo da je formula S k = k k + 1 tačna.
U trećem koraku trebamo dokazati da je S k + 1 = k + 1 k + 1 + 1 = k + 1 k + 2 , na osnovu valjanosti prethodne jednakosti.

Možemo predstaviti k + 1 kao zbir prvih članova originalnog niza i k + 1:

S k + 1 = S k + 1 k + 1 (k + 2)

Pošto smo u drugoj akciji dobili da je S k = k k + 1, možemo napisati sljedeće:

S k + 1 = S k + 1 k + 1 (k + 2) .

Sada izvodimo potrebne transformacije. Trebat ćemo svesti razlomak na zajednički nazivnik, smanjiti slične članove, primijeniti skraćenu formulu množenja i smanjiti ono što dobijemo:

S k + 1 = S k + 1 k + 1 (k + 2) = k k + 1 + 1 k + 1 (k + 2) = = k (k + 2) + 1 k + 1 (k + 2) = k 2 + 2 k + 1 k + 1 (k + 2) = (k + 1) 2 k + 1 (k + 2) = k + 1 k + 2

Dakle, dokazali smo jednakost u trećoj tački ispunjavanjem sva tri koraka metode matematičke indukcije.

odgovor: pretpostavka o formuli S n = n n + 1 je tačna.

Uzmimo složeniji problem sa trigonometrijskim funkcijama.

Primjer 2

Dajte dokaz identiteta cos 2 α · cos 4 α · . . . · cos 2 n α = sin 2 n + 1 α 2 n sin 2 α .

Rješenje

Kao što se sjećamo, prvi korak bi trebao biti provjera valjanosti jednakosti kada je n jednako jedan. Da bismo saznali, moramo se sjetiti osnovnih trigonometrijskih formula.

cos 2 1 = cos 2 α sin 2 1 + 1 α 2 1 sin 2 α = sin 4 α 2 sin 2 α = 2 sin 2 α cos 2 α 2 sin 2 α = cos 2 α

Prema tome, za n jednako jedan, identitet će biti istinit.

Sada pretpostavimo da njegova valjanost ostaje istinita za n = k, tj. biće tačno da je cos 2 α · cos 4 α · . . . · cos 2 k α = sin 2 k + 1 α 2 k sin 2 α .

Dokazujemo jednakost cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = sin 2 k + 2 α 2 k + 1 sin 2 α za slučaj kada je n = k + 1, uzimajući prethodnu pretpostavku kao osnovu.

Prema trigonometrijskoj formuli,

sin 2 k + 1 α cos 2 k + 1 α = = 1 2 (sin (2 k + 1 α + 2 k + 1 α) + sin (2 k + 1 α - 2 k + 1 α)) = = 1 2 sin (2 2 k + 1 α) + sin 0 = 1 2 sin 2 k + 2 α

dakle,

cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = = cos 2 α · cos 4 α · . . . · cos 2 k α · cos 2 k + 1 α = = sin 2 k + 1 α 2 k sin 2 α · cos 2 k + 1 α = 1 2 · sin 2 k + 1 α 2 k sin 2 α = sin 2 k + 2 α 2 k + 1 sin 2 α

Dali smo primjer rješavanja problema za dokazivanje nejednakosti ovom metodom u članku o metodi najmanjih kvadrata. Pročitajte pasus u kojem se izvode formule za pronalaženje aproksimacijskih koeficijenata.

Ako primijetite grešku u tekstu, označite je i pritisnite Ctrl+Enter

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..02.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. Indukcijska 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.

Predavanje 6. Metoda matematičke indukcije.

Nova saznanja u nauci i životu stiču se na različite načine, ali se sva (ako ne ulazimo u detalje) dijele na dvije vrste - prijelaz iz opšteg u specifično i iz specifičnog u opšte. Prvi je dedukcija, drugi je indukcija. Deduktivno zaključivanje je ono što se obično naziva u matematici. logičko rezonovanje, au matematičkoj nauci dedukcija je jedina legitimna metoda istraživanja. Pravila logičkog zaključivanja formulisao je prije dva i po milenijuma starogrčki naučnik Aristotel. Napravio je kompletnu listu najjednostavnijih ispravnih rasuđivanja, silogizmi– „građevinski blokovi” logike, a istovremeno ukazuju na tipično rezonovanje koje je veoma slično ispravnom, ali netačno (često se susrećemo sa takvim „pseudološkim” rezonovanjem u medijima).

Indukcija (indukcija - na latinskom vođenje) jasno ilustruje poznata legenda o tome kako je Isak Njutn formulisao zakon univerzalne gravitacije nakon što mu je jabuka pala na glavu. Još jedan primjer iz fizike: u fenomenu kao što je elektromagnetna indukcija, električno polje stvara, "inducira" magnetno polje. „Njutnova jabuka“ je tipičan primer situacije u kojoj jedan ili više posebnih slučajeva, tj. zapažanja, “predlažu” opštu izjavu; opšti zaključak se izvodi na osnovu konkretnih slučajeva. Induktivna metoda je glavna za dobijanje opštih obrazaca kako u prirodnim tako iu ljudskim naukama. Ali ima vrlo značajan nedostatak: na osnovu konkretnih primjera može se izvući netačan zaključak. Hipoteze koje proizilaze iz privatnih zapažanja nisu uvijek tačne. Razmotrimo primjer zbog Eulera.

Izračunat ćemo vrijednost trinoma za neke prve vrijednosti n:

Imajte na umu da su brojevi dobijeni kao rezultat proračuna prosti. I to se može direktno provjeriti za svaki n 1 do 39 polinomska vrijednost
je prost broj. Međutim, kada n=40 dobijamo broj 1681=41 2, koji nije prost. Dakle, hipoteza koja bi ovdje mogla nastati, odnosno hipoteza da za svaku n broj
je jednostavno, ispostavilo se da je lažno.

Lajbnic je u 17. veku dokazao da za svaku pozitivnu celinu n broj
djeljivo sa 3, broj
djeljivo sa 5 itd. Na osnovu ovoga, pretpostavio je da je za bilo koji nepar k i bilo koje prirodne n broj
podijeljena k, ali ubrzo sam to primijetio
nije djeljiva sa 9.

Razmotreni primjeri nam omogućavaju da izvučemo važan zaključak: izjava može biti pravedna u nizu posebnih slučajeva i istovremeno nepravedna općenito. Pitanje valjanosti iskaza u opštem slučaju može se rešiti upotrebom posebne metode rezonovanja tzv matematičkom indukcijom(potpuna indukcija, savršena indukcija).

6.1. Princip matematičke indukcije.

♦ Metoda matematičke indukcije se zasniva na princip matematičke indukcije , što je kako slijedi:

1) proverava se validnost ove izjaven=1 (osnova indukcije) ,

2) valjanost ove izjave se pretpostavlja zan= k, Gdjek– proizvoljan prirodan broj 1(pretpostavka indukcije) , a uzimajući u obzir ovu pretpostavku, njegova valjanost se utvrđuje zan= k+1.

Dokaz. Pretpostavimo suprotno, odnosno pretpostavimo da izjava nije tačna za svako prirodno n. Onda postoji tako prirodno m, Šta:

1) izjava za n=m nije fer,

2) za sve n, manji m, izjava je tačna (drugim riječima, m je prvi prirodan broj za koji tvrdnja nije tačna).

Očigledno je da m>1, jer Za n=1 izjava je tačna (uslov 1). dakle,
- prirodni broj. Ispada da je to za prirodan broj
tvrdnja je tačna, a za sljedeći prirodni broj m to je nepravedno. Ovo je u suprotnosti sa uslovom 2. ■

Imajte na umu da je u dokazu korišten aksiom da bilo koja zbirka prirodnih brojeva sadrži najmanji broj.

Dokaz zasnovan na principu matematičke indukcije naziva se metodom potpune matematičke indukcije .

 Primjer6.1. Dokažite to za bilo koji prirodni n broj
djeljivo sa 3.

Rješenje.

1) Kada n=1, dakle a 1 je djeljiv sa 3 i tvrdnja je tačna kada n=1.

2) Pretpostavimo da je izjava tačna za n=k,
, odnosno taj broj
je djeljiv sa 3, a mi utvrđujemo da kada n=k+1 broj je djeljiv sa 3.

Zaista,

Jer Svaki član je djeljiv sa 3, tada je i njihov zbir djeljiv sa 3. ■ 

 Primjer6.2. Dokaži da je zbir prvog n prirodni neparni brojevi jednak je kvadratu njihovog broja, tj.

Rješenje. Koristimo metodu potpune matematičke indukcije.

1) Provjeravamo valjanost ove izjave kada n=1: 1=1 2 – to je tačno.

2) Pretpostavimo da je zbir prvog k (
) neparnih brojeva jednak je kvadratu broja tih brojeva, tj. Na osnovu ove jednakosti utvrđujemo da je zbir prvog k+1 neparni brojevi je jednako
, to je .

Koristimo našu pretpostavku i dobijamo

. ■ 

Za dokazivanje nekih nejednakosti koristi se metoda potpune matematičke indukcije. Dokažimo Bernoullijevu nejednakost.

 Primjer6.3. Dokaži to kada
i bilo koje prirodne n nejednakost je tačna
(Bernoullijeva nejednakost).

Rješenje. 1) Kada n=1 dobijamo
, što je tačno.

2) Pretpostavljamo da kada n=k postoji nejednakost
(*). Koristeći ovu pretpostavku, to dokazujemo
. Imajte na umu da kada
ova nejednakost vrijedi i stoga je dovoljno razmotriti slučaj
.

Pomnožimo obje strane nejednakosti (*) brojem
i dobijamo:

To je (1+
.■ 

Dokaz metodom nepotpuna matematička indukcija neke izjave u zavisnosti od n, Gdje
izvedeno na sličan način, ali se na početku uspostavlja pravičnost za najmanju vrijednost n.

Neki problemi ne navode eksplicitno tvrdnju koja se može dokazati matematičkom indukcijom. U takvim slučajevima morate sami uspostaviti obrazac i postaviti hipotezu o valjanosti ovog uzorka, a zatim koristiti metodu matematičke indukcije da testirate predloženu hipotezu.

 Primjer6.4. Pronađite iznos
.

Rješenje. Nađimo sume S 1 , S 2 , S 3. Imamo
,
,
. Pretpostavljamo da za bilo koji prirodni n formula je važeća
. Da bismo provjerili ovu hipotezu, koristit ćemo metodu potpune matematičke indukcije.

1) Kada n=1 hipoteza je tačna, jer
.

2) Pretpostavimo da je hipoteza tačna za n=k,
, to je
. Koristeći ovu formulu, utvrđujemo da je hipoteza istinita čak i kada n=k+1, tj

Zaista,

Dakle, na osnovu pretpostavke da je hipoteza tačna kada n=k,
, dokazano je da to vrijedi i za n=k+1, a na osnovu principa matematičke indukcije zaključujemo da formula vrijedi za bilo koji prirodan broj n. ■ 

 Primjer6.5. U matematici je dokazano da je zbir dvije ravnomjerno neprekidne funkcije uniformno kontinuirana funkcija. Na osnovu ove izjave, morate dokazati da je zbir bilo kojeg broja
uniformno kontinuiranih funkcija je uniformno kontinuirana funkcija. Ali pošto još nismo uveli koncept „jednoliko kontinuirane funkcije“, postavimo problem apstraktnije: neka bude poznato da je zbroj dviju funkcija koje imaju neko svojstvo S, sama ima imovinu S. Dokažimo da zbir bilo kojeg broja funkcija ima svojstvo S.

Rješenje. Osnova indukcije ovdje je sadržana u formulaciji samog problema. Nakon što ste napravili indukcijsku pretpostavku, razmotrite
funkcije f 1 , f 2 , …, f n , f n+1 koji imaju svojstvo S. Onda . Na desnoj strani, prvi pojam ima svojstvo S po hipotezi indukcije, drugi član ima svojstvo S po stanju. Prema tome, njihov zbir ima svojstvo S– za dva mandata osnova indukcije „radi“.

Ovo dokazuje tvrdnju i mi ćemo je dalje koristiti. ■ 

 Primjer6.6. Pronađite sve prirodno n, za koje je tačna nejednakost

Rješenje. Hajde da razmotrimo n=1, 2, 3, 4, 5, 6. Imamo: 2 1 >1 2, 2 2 =2 2, 2 3<3 2 , 2 4 =4 2 , 2 5 >5 2, 2 6 >6 2. Dakle, možemo postaviti hipotezu: nejednakost
ima mjesta za svakoga
. Da bismo dokazali istinitost ove hipoteze, koristit ćemo princip nepotpune matematičke indukcije.

1) Kao što je gore utvrđeno, ova hipoteza je tačna kada n=5.

2) Pretpostavimo da je tačno za n=k,
, odnosno nejednakost je tačna
. Koristeći ovu pretpostavku, dokazujemo da je nejednakost
.

Jer
i na
postoji nejednakost

at
,

onda to dobijamo
. Dakle, istinitost hipoteze na n=k+1 proizlazi iz pretpostavke da je tačno kada n=k,
.

Iz paragrafa. 1 i 2, na osnovu principa nepotpune matematičke indukcije, slijedi da je nejednakost
istina za svako prirodno
. ■ 

 Primjer6.7. Dokažite to za bilo koji prirodan broj n formula diferencijacije je važeća
.

Rješenje. At n=1 ova formula izgleda
, ili 1=1, odnosno tačno je. Uz indukcijsku pretpostavku, imamo:

Q.E.D. ■ 

 Primjer6.8. Dokazati da je skup koji se sastoji od n elemenata, ima podskupovi

Rješenje. Skup koji se sastoji od jednog elementa A, ima dva podskupa. Ovo je tačno jer su svi njegovi podskupovi prazan skup i sam prazan skup, i 2 1 =2.

Pretpostavimo da je svaki skup od n elemenata ima podskupovi Ako se skup A sastoji od n+1 elemenata, onda u njega fiksiramo jedan element - označavamo ga d, i podijeliti sve podskupove u dvije klase - one koje ne sadrže d i koji sadrži d. Svi podskupovi iz prve klase su podskupovi skupa B koji se dobija od A uklanjanjem elementa d.

Skup B se sastoji od n elemenata, pa prema tome, indukcijom, ima podskupovi, dakle u prvoj klasi podskupovi

Ali u drugoj klasi postoji isti broj podskupova: svaki od njih se dobija iz tačno jednog podskupa prve klase dodavanjem elementa d. Dakle, ukupno skup A
podskupovi

Time je izjava dokazana. Imajte na umu da to vrijedi i za skup koji se sastoji od 0 elemenata - prazan skup: on ima jedan podskup - sebe, i 2 0 = 1. ■ 