Matemaattisten induktiotuntien menetelmä. Matemaattisen induktion menetelmän soveltaminen luonnollisten lukujen jaollisuusongelmien ratkaisemiseen

Matemaattisen induktion menetelmä

Johdanto

Pääosa

Täydellinen ja epätäydellinen induktio
Matemaattisen induktion periaate
Matemaattisen induktion menetelmä
Esimerkkien ratkaisu
Tasa-arvo
Numeroiden jako
epätasa-arvoa

Johtopäätös

Luettelo käytetystä kirjallisuudesta

Johdanto

Deduktiiviset ja induktiiviset menetelmät ovat kaiken matemaattisen tutkimuksen perusta. Deduktiivinen päättelytapa on päättelyä yleisestä erityiseen, ts. päättely, jonka lähtökohta on yleinen tulos ja loppupiste on erityinen tulos. Induktiota käytetään siirryttäessä tietyistä tuloksista yleisiin, ts. on deduktiivisen menetelmän vastakohta.

Matemaattisen induktion menetelmää voidaan verrata edistymiseen. Aloitamme alimmasta, loogisen ajattelun tuloksena pääsemme korkeimpaan. Ihminen on aina pyrkinyt edistymiseen, kykyyn kehittää ajatteluaan loogisesti, mikä tarkoittaa, että luonto itse on määrännyt hänet ajattelemaan induktiivisesti.

Vaikka matemaattisen induktion menetelmän sovellusala on kasvanut, koulun opetussuunnitelmassa siihen on varattu vähän aikaa. Sanotaanpa, että hyödyllisen ihmisen tuovat ne kaksi tai kolme oppituntia, joista hän kuulee viisi teorian sanaa, ratkaisee viisi primitiivistä ongelmaa ja saa sen seurauksena viidenneksen, kun hän ei tiedä mitään.

Mutta tämä on niin tärkeää - pystyä ajattelemaan induktiivisesti.

Pääosa

Alkuperäisessä merkityksessään sanaa "induktio" käytetään päättelyyn, jolla tehdään yleisiä johtopäätöksiä useiden tiettyjen lausuntojen perusteella. Yksinkertaisin tällainen päättelytapa on täydellinen induktio. Tässä on esimerkki tällaisesta päättelystä.

Vaaditaan, että jokainen luonnollinen parillinen luku n sisällä 4 voidaan esittää kahden alkuluvun summana. Tätä varten otamme kaikki tällaiset numerot ja kirjoitamme vastaavat laajennukset:

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.

Nämä yhdeksän yhtälöä osoittavat, että jokainen meitä kiinnostavista luvuista on todellakin esitetty kahden alkutermin summana.

Täydellinen induktio on siis sitä, että yleinen väite todistetaan erikseen jokaisessa äärellisessä määrässä mahdollisia tapauksia.

Joskus yleinen tulos voidaan ennustaa, kun ei ole otettu huomioon kaikkia, vaan suuri määrä erikoistapauksia (ns. epätäydellinen induktio).

Epätäydellisellä induktiolla saatu tulos jää kuitenkin vain hypoteesiksi, kunnes se todistetaan tarkalla matemaattisella päättelyllä, joka kattaa kaikki erikoistapaukset. Toisin sanoen matematiikan epätäydellistä induktiota ei pidetä legitiiminä tiukan todistelun menetelmänä, vaan se on tehokas menetelmä uusien totuuksien löytämiseksi.

Olkoon esimerkiksi, että on löydettävä ensimmäisen n peräkkäisen parittoman luvun summa. Harkitse erikoistapauksia:

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

Näiden muutaman erikoistapauksen tarkastelun jälkeen tulee seuraava yleinen johtopäätös:

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

nuo. ensimmäisen n peräkkäisen parittoman luvun summa on n 2

Tehty havainto ei tietenkään voi vielä toimia todisteena yllä olevan kaavan pätevyydestä.

Täydellisellä induktiolla on vain rajallisia sovelluksia matematiikassa. Monet mielenkiintoiset matemaattiset väitteet kattavat äärettömän määrän erikoistapauksia, emmekä voi testata ääretöntä määrää tapauksia. Epätäydellinen induktio johtaa usein virheellisiin tuloksiin.

Monissa tapauksissa ulospääsy tällaisesta vaikeudesta on turvautua erityiseen päättelymenetelmään, jota kutsutaan matemaattisen induktion menetelmäksi. Se on seuraava.

Olkoon tarpeen todistaa tietyn väitteen pätevyys mille tahansa luonnolliselle luvulle n (esimerkiksi on todistettava, että ensimmäisen n parittoman luvun summa on yhtä suuri kuin n 2). Tämän väitteen suora todentaminen jokaiselle n:n arvolle on mahdotonta, koska luonnollisten lukujen joukko on ääretön. Todistaaksesi tämän väitteen, tarkista ensin sen pätevyys arvolle n=1. Sitten todistetaan, että millä tahansa k:n luonnollisella arvolla tarkasteltavan väitteen pätevyys arvolle n=k merkitsee sen pätevyyttä myös arvolle n=k+1.

Sitten väite katsotaan todistetuksi kaikille n:lle. Todellakin, väite on totta, kun n=1. Mutta sitten se pätee myös seuraavalle numerolle n=1+1=2. Väitteen pätevyys arvolle n=2 tarkoittaa sen pätevyyttä arvolle n=2+

1 = 3. Tämä tarkoittaa lauseen pätevyyttä n=4:lle ja niin edelleen. On selvää, että lopulta saavutamme minkä tahansa luonnollisen luvun n. Näin ollen väite on totta mille tahansa n:lle.

Yhteenvetona sanotusta muotoilemme seuraavan yleisperiaatteen.

Matemaattisen induktion periaate.

Jos lause A(n) luonnollisesta luvusta riippuenn, tottan=1 ja siitä, että se on tottan= k (missäk-mikä tahansa luonnollinen luku), tästä seuraa, että se on totta myös seuraavalle numerollen= k+1, sitten oletus A(n) on totta mille tahansa luonnolliselle luvullen.

Jos lause A(n) pitää paikkansan= s ja jos A(k) Þ MUTTA(k+1) mille tahansak> s, sitten lause A(n) on totta kaikillen> s.

Todistus matemaattisen induktion menetelmällä suoritetaan seuraavasti. Ensin tarkistetaan todistettava väite arvolle n=1, ts. väitteen A(1) totuus vahvistetaan. Tätä todistuksen osaa kutsutaan induktiopohjaksi. Tätä seuraa osa todistuksesta, jota kutsutaan induktiovaiheeksi. Tässä osassa todistetaan lauseen pätevyys n=k+1:lle olettaen, että väite on tosi arvolle n=k (induktiivinen oletus), ts. todista, että A(k)ÞA(k+1).

ESIMERKKI 1

Todista, että 1+3+5+…+(2n-1)=n 2 .

Ratkaisu: 1) Meillä on n=1=1 2 . Näin ollen

lause on tosi, kun n=1, ts. A(1) on totta.

2) Osoitetaan, että A(k)ÞA(k+1).

Olkoon k mikä tahansa luonnollinen luku ja olkoon lause tosi kun n=k, ts.

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

Osoitetaan, että silloin väite pätee myös seuraavalle luonnolliselle luvulle n=k+1, ts. mitä

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

Todellakin,

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

Joten A(k)ÞA(k+1). Matemaattisen induktion periaatteen perusteella päättelemme, että oletus A(n) on totta mille tahansa nОN:lle.

ESIMERKKI 2

Todista se

1 + x + x 2 + x 3 + ... + x n \u003d (x n +1 -1) / (x-1), missä x¹1

Ratkaisu: 1) Saat n=1:lle

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

siksi n = 1:lle kaava on tosi; A(1) on totta.

2) Olkoon k mikä tahansa luonnollinen luku ja olkoon kaava tosi, kun n=k, ts.

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

Todistakaamme, että sitten tasa-arvo

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

Todellakin

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).

Joten A(k)ÞA(k+1). Matemaattisen induktion periaatteen perusteella päätämme, että kaava on totta mille tahansa luonnolliselle luvulle n.

ESIMERKKI 3

Osoita, että kuperan n-kulman lävistäjien lukumäärä on n(n-3)/2.

Ratkaisu: 1) Kun n=3, väite on tosi

Ja 3 on oikein, koska kolmiossa

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

2 A(3) on totta.

2) Oletetaan, että missä tahansa

kupera k-gon on-

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

A k Todistetaan, että silloin konveksissa

(k+1)-gon luku

diagonaalit A k +1 \u003d (k + 1) (k-2) / 2.

Olkoon А 1 А 2 А 3 …A k A k +1 -kupera (k+1)-kulma. Piirretään siihen diagonaali A 1 A k. Laskeaksesi tämän (k + 1)-gonin diagonaalien kokonaismäärän, sinun on laskettava lävistäjät k-gonissa A 1 A 2 ...A k , lisätään k-2 saatuun lukuun, ts. Huomioon tulee ottaa kärjestä A k +1 lähtevän (k+1)-gonin lävistäjät ja lisäksi diagonaali A 1 A k.

Tällä tavalla,

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

Joten A(k)ÞA(k+1). Matemaattisen induktion periaatteesta johtuen väite pätee mille tahansa konveksille n-kulmiolle.

ESIMERKKI 4

Todista, että mille tahansa n:lle lause on tosi:

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

Ratkaisu: 1) Olkoon sitten n=1

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

Näin ollen n=1:lle väite on tosi.

2) Oletetaan, että n=k

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

3) Tarkastellaan tätä lausetta n=k+1:lle

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)(2k2 +7k+6)/6=(k+1)(2(k+3/2)(k+)

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

Olemme todistaneet yhtälön pätevyyden n=k+1:lle, joten matemaattisen induktion menetelmän perusteella väite pätee mille tahansa luonnolliselle n:lle.

ESIMERKKI 5

Todista, että minkä tahansa luonnollisen n:n yhtäläisyys on totta:

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

Ratkaisu: 1) Olkoon n=1.

Sitten X 1 = 1 3 = 1 2 (1+1) 2 /4 = 1.

Näemme, että n=1:lle väite on tosi.

2) Oletetaan, että yhtälö on tosi, kun n=k

X k \u003d k 2 (k + 1) 2/4.

3) Todistetaan tämän väitteen totuus arvolle n=k+1, ts.

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(k2+4k+4)/4=(k+1)2(k+2)2/4.

Yllä olevasta todistuksesta käy selvästi ilmi, että väite on tosi n=k+1, joten yhtäläisyys pätee mille tahansa luonnolliselle n:lle.

ESIMERKKI 6

Todista se

((2 3 +1)/(2 3 -1))´((3 3 +1)/(3 3 -1))´…´((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n2+n+1), missä n>2.

Ratkaisu: 1) Arvolla n=2 identiteetti näyttää tältä: (2 3 +1)/(2 3 -1)=(3´2´3)/2(2 2 +2+1),

nuo. Se on oikein.

2) Oletetaan, että lauseke on tosi, kun n=k

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

3) Todistetaan lausekkeen oikeellisuus n=k+1:lle.

(((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).

Olemme todistaneet yhtälön pätevyyden arvolle n=k+1, joten matemaattisen induktion menetelmästä johtuen väite on totta mille tahansa n>2:lle

ESIMERKKI 7

Todista se

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

mille tahansa luonnolliselle n.

Ratkaisu: 1) Olkoon sitten n=1

1 3 -2 3 =-1 3 (4+3); -7=-7.

2) Oletetaan, että n=k

1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3-(2k)3 = -k2 (4k+3).

3) Todistetaan tämän väitteen totuus arvolle 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).

Myös yhtälön pätevyys n=k+1:lle on todistettu, joten väite pätee mille tahansa luonnolliselle luvulle n.

ESIMERKKI 8

Todista identiteetin oikeellisuus

(1 2 /1'3)+(2 2 /3'5)+…+(n 2 /(2n-1)´(2n+1))=n(n+1)/2(2n+1)

mille tahansa luonnolliselle n.

1) Kun n=1, identtisyys on tosi 1 2 /1´3=1(1+1)/2(2+1).

2) Oletetaan, että n=k

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

3) Osoitetaan, että identtisyys on tosi 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).

Yllä olevasta todistuksesta voidaan nähdä, että väite on totta mille tahansa luonnolliselle luvulle n.

ESIMERKKI 9

Todista, että (11 n+2 +12 2n+1) on jaollinen luvulla 133 ilman jäännöstä.

Ratkaisu: 1) Olkoon sitten n=1

11 3 +12 3 \u003d (11 + 12) (11 2 -132 + 12 2) \u003d 23´133.

Mutta (23´133) on jaollinen luvulla 133 ilman jäännöstä, joten n=1:lle väite on tosi; A(1) on totta.

2) Oletetaan, että (11 k+2 +12 2k+1) on jaollinen luvulla 133 ilman jäännöstä.

3) Todistakaamme se tässä tapauksessa

(11 k+3 +12 2k+3) on jaollinen 133:lla ilman jäännöstä. Todellakin, 11 k+3 +12 2k+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 .

Tuloksena oleva summa on jaollinen luvulla 133 ilman jäännöstä, koska sen ensimmäinen termi on oletuksena jaollinen luvulla 133 ilman jäännöstä, ja toisessa yksi tekijöistä on 133. Eli А(k)ÞА(k+1). Matemaattisen induktion menetelmän avulla väite todistetaan.

ESIMERKKI 10

Todista, että millä tahansa n 7:llä n -1 on jaollinen 6:lla ilman jäännöstä.

Ratkaisu: 1) Olkoon n=1, niin X 1 =7 1 -1=6 jaetaan 6:lla ilman jäännöstä. Joten lauseelle n=1 väite on tosi.

2) Oletetaan, että n=k

7 k -1 on jaollinen 6:lla ilman jäännöstä.

3) Osoitetaan, että väite on tosi, kun n=k+1.

X k+1 =7 k+1-1=7'7 k-7+6=7(7 k-1)+6.

Ensimmäinen termi on jaollinen 6:lla, koska 7 k -1 on jaollinen 6:lla oletuksella, ja toinen termi on 6. Joten 7 n -1 on luvun 6 kerrannainen mille tahansa luonnolliselle n:lle. Matemaattisen induktion menetelmän avulla väite todistetaan.

ESIMERKKI 11

Todista, että 3 3n-1 +2 4n-3 mielivaltaiselle luonnolliselle n:lle on jaollinen luvulla 11.
Ratkaisu: 1) Olkoon sitten n=1

X 1 \u003d 3 3-1 +2 4-3 \u003d 3 2 +2 1 \u003d 11 jaetaan 11:llä ilman jäännöstä. Näin ollen n=1:lle väite on tosi.

2) Oletetaan, että n=k

X k \u003d 3 3k-1 +2 4k-3 on jaollinen 11:llä ilman jäännöstä.

3) Osoitetaan, että väite on tosi, kun 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.

Ensimmäinen termi on jaollinen 11:llä ilman jäännöstä, koska 3 3 k-1 +2 4k-3 on jaollinen 11:llä oletuksena, toinen termi on jaollinen 11:llä, koska yksi sen tekijöistä on luku 11. Summa on siis jaollinen 11:llä ei jäännöstä millekään luonnolliselle n:lle. Matemaattisen induktion menetelmän avulla väite todistetaan.

ESIMERKKI 12

Osoita, että 11 2n -1 mielivaltaiselle positiiviselle kokonaisluvulle n on jaollinen 6:lla ilman jäännöstä.

Ratkaisu: 1) Olkoon n=1, niin 11 2 -1=120 on jaollinen 6:lla ilman jäännöstä. Joten lauseelle n=1 väite on tosi.

2) Oletetaan, että n=k

11 2 k -1 on jaollinen 6:lla ilman jäännöstä.

11 2(k+1)-1=121´11 2k-1=120´11 2k +(11 2k-1).

Molemmat termit ovat jaollisia 6:lla ilman jäännöstä: ensimmäinen sisältää 6:n kerrannaisluvun 120, ja toinen on jaollinen 6:lla ilman jäännöstä oletuksena. Joten summa on jaollinen 6:lla ilman jäännöstä. Matemaattisen induktion menetelmän avulla väite todistetaan.

ESIMERKKI 13

Osoita, että 3 3 n+3 -26n-27 mielivaltaiselle positiiviselle kokonaisluvulle n on jaollinen luvulla 26 2 (676) ilman jäännöstä.

Ratkaisu: Osoitetaan ensin, että 3 3 n+3 -1 on jaollinen luvulla 26 ilman jäännöstä.

Jos n = 0

3 3 -1=26 on jaollinen 26:lla

Oletetaan, että n=k

3 3k+3 -1 on jaollinen 26:lla

Todistakaamme tämä väite

totta kun n=k+1.

3 3 k+6 -1=27´3 3k+3 -1=26´3 3k+3 +(3 3 k +3 -1) - on jaollinen luvulla 26

Todistakaamme nyt ongelman ehdolla muotoiltu väite.

1) On selvää, että n=1:lle väite on tosi

3 3+3 -26-27=676

2) Oletetaan, että n=k

lauseke 3 3 k+3 -26k-27 on jaollinen luvulla 26 2 ilman jäännöstä.

3) Osoitetaan, että väite on tosi, kun n=k+1

3 3k+6-26(k+1)-27=26(3 3k+3-1)+(3 3k+3-26k-27).

Molemmat termit ovat jaollisia luvulla 26 2 ; ensimmäinen on jaollinen luvulla 26 2, koska olemme osoittaneet, että suluissa oleva lauseke on jaollinen luvulla 26, ja toinen on jaollinen induktiivisella hypoteesilla. Matemaattisen induktion menetelmän avulla väite todistetaan.

ESIMERKKI 14

Todista, että jos n>2 ja x>0, niin epäyhtälö

(1+x) n > 1+n´x.

Ratkaisu: 1) Kun n=2, epäyhtälö on tosi, koska

(1+x) 2 =1+2x+x 2 >1+2x.

Joten A(2) on totta.

2) Osoitetaan, että A(k)ÞA(k+1), jos k> 2. Oletetaan, että A(k) on tosi, eli että epäyhtälö

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

Osoitetaan, että silloin myös A(k+1) on totta, eli että epäyhtälö

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

Todellakin, kun epäyhtälön (3) molemmat puolet kerrotaan positiivisella luvulla 1+x, saadaan

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

Harkitse viimeisen epätasa-arvon oikeaa puolta

stva; meillä on

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

Tämän seurauksena saamme sen

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

Joten A(k)ÞA(k+1). Matemaattisen induktion periaatteen perusteella voidaan väittää, että Bernoullin epäyhtälö pätee mille tahansa

ESIMERKKI 15

Todista, että eriarvoisuus on totta

(1+a+a 2) m > 1+m´a+(m(m+1)/2)´a 2 kun a > 0.

Ratkaisu: 1) Kun m=1

(1+a+a 2) 1 > 1+a+(2/2)´a 2 molemmat osat ovat yhtä suuret.

2) Oletetaan, että m=k

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

3) Osoitetaan, että m=k+1 epäyhtälö on tosi

(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 .

Olemme osoittaneet epäyhtälön pätevyyden m=k+1:lle, joten matemaattisen induktion menetelmän ansiosta epäyhtälö on totta mille tahansa luonnolliselle m:lle.

ESIMERKKI 16

Todista, että n>6 epäyhtälö

Ratkaisu: kirjoitetaan epäyhtälö muotoon

Meillä on n=7

37/27 =2187/128>14=2´7

eriarvoisuus on totta.

Oletetaan, että n=k

3) Osoitetaan epäyhtälön oikeellisuus n=k+1:lle.

3k+1/2k+1 =(3k/2k)´(3/2)>2k´(3/2)=3k>2(k+1).

Koska k>7, viimeinen epäyhtälö on ilmeinen.

Matemaattisen induktion menetelmän ansiosta epäyhtälö pätee mille tahansa luonnolliselle n:lle.

ESIMERKKI 17

Todista, että n>2 epäyhtälö

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

Ratkaisu: 1) Kun n=3 epäyhtälö on tosi

1+(1/2 2)+(1/3 2)=245/180

Oletetaan, että n=k

1+(1/2 2)+(1/3 2)+…+(1/k2)=1,7-(1/k).

3) Todistamme ei-

yhtälöt n=k+1:lle

(1+(1/2 2)+…+(1/k2))+(1/(k+1) 2)

Osoitetaan, että 1,7-(1/k)+(1/(k+1) 2)

Û(1/(k+1) 2)+(1/k+1)Ûk(k+2)

Jälkimmäinen on ilmeinen ja siksi

1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)

Matemaattisen induktion menetelmän avulla epätasa-arvo todistetaan.

Johtopäätös

Erityisesti opiskeltuani matemaattisen induktion menetelmää lisäsin tietämystäni tällä matematiikan alueella ja opin myös ratkaisemaan ongelmia, jotka olivat aiemmin ylivoimaiseni.

Pohjimmiltaan nämä olivat loogisia ja viihdyttäviä tehtäviä, ts. vain ne, jotka lisäävät kiinnostusta matematiikkaa kohtaan tieteenä. Tällaisten ongelmien ratkaisemisesta tulee viihdyttävää toimintaa ja se voi houkutella yhä enemmän uteliaita ihmisiä matemaattisiin labyrinteihin. Mielestäni tämä on kaiken tieteen perusta.

Jatkamalla matemaattisen induktion menetelmän tutkimista, yritän oppia soveltamaan sitä paitsi matematiikassa myös fysiikan, kemian ja itse elämän ongelmien ratkaisemisessa.

MATEMAA:

LUONEET, TEHTÄVÄT, RATKAISUT

Oppikirja / V. G. Boltyansky, Yu. V. Sidorov, M. I. Shabunin. Potpourri LLC 1996.

ALGEBRA JA ANALYYSIPERIAATTEET

Oppikirja / I.T. Demidov, A.N. Kolmogorov, S.I. Shvartsburg, O.S. Ivashev-Musatov, B.E. Veyts. "Valaistus" 1975.

Induktio on menetelmä yleisen lausunnon saamiseksi tietyistä havainnoista. Siinä tapauksessa, että matemaattinen väite koskee äärellistä määrää objekteja, se voidaan todistaa tarkistamalla jokaisen objektin osalta. Esimerkiksi lause: "Jokainen kaksinumeroinen parillinen luku on kahden alkuluvun summa" seuraa sarjasta yhtäläisyyksiä, jotka on melko realistisia määrittää:

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

Todistusmenetelmää, jossa väite tarkistetaan äärelliselle määrälle tapauksia, käyttäen kaikki mahdollisuudet, kutsutaan täydelliseksi induktioksi. Tätä menetelmää voidaan soveltaa suhteellisen harvoin, koska matemaattiset lausunnot eivät yleensä koske äärellisiä, vaan äärettömiä oliojoukkoja. Esimerkiksi edellä täydellisellä induktiolla todistettu väite parillisista kaksinumeroisista luvuista on vain lauseen erikoistapaus: "Mikä tahansa parillinen luku on kahden alkuluvun summa." Tätä lausetta ei ole vielä todistettu tai kumottu.

Matemaattinen induktio on menetelmä jolla todistetaan tietty väite mille tahansa luonnolliselle n:lle, joka perustuu matemaattisen induktion periaatteeseen: ”Jos väite on tosi arvolle n=1 ja sen pätevyydestä arvolle n=k, tämä väite on tosi arvolle n= k+1, niin se on totta kaikille n". Todistusmenetelmä matemaattisella induktiolla on seuraava:

1) induktion perusta: todista tai todenna suoraan väitteen pätevyys arvolle n=1 (joskus n=0 tai n=n 0);

2) induktioaskel (siirtymä): ne olettavat lauseen pätevyyden jollekin luonnolliselle n=k:lle ja tämän oletuksen perusteella todistavat lauseen pätevyyden n=k+1:lle.

Ongelmia ratkaisujen kanssa

1. Osoita, että millä tahansa luonnollisella n:llä luku 3 2n+1 +2 n+2 on jaollinen 7:llä.

Merkitään A(n)=3 2n+1 +2 n+2.

induktion perusta. Jos n=1, niin A(1)=3 3 +2 3 =35 ja ilmeisesti jaollinen 7:llä.

Induktiohypoteesi. Olkoon A(k) jaollinen 7:llä.

induktiivinen siirtymä. Osoitetaan, että A(k+1) on jaollinen 7:llä, eli tehtävän lauseen pätevyys n=k:lle.

А(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 .

Viimeinen luku on jaollinen 7:llä, koska se on kahden 7:llä jaollisen kokonaisluvun erotus. Siksi 3 2n+1 +2 n+2 on jaollinen 7:llä millä tahansa luonnollisella n:llä.

2. Osoita, että millä tahansa positiivisella kokonaisluvulla n luku 2 3 n +1 on jaollinen luvulla 3 n+1, eikä se ole jaollinen luvulla 3 n+2 .

Otetaan käyttöön merkintä: a i =2 3 i +1.

Kun n=1 meillä on, ja 1 =2 3 +1=9. Joten 1 on jaollinen luvulla 3 2 eikä jaollinen luvulla 3 3 .

Olkoon n=k:lla luku a k jaollinen 3 k+1:llä eikä 3 k+2:lla, eli a k =2 3 k +1=3 k+1 m, missä m ei ole jaollinen kolmella.

ja 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).

On selvää, että k+1 on jaollinen luvulla 3 k+2, eikä se ole jaollinen luvulla 3 k+3 .

Siksi väite on todistettu mille tahansa luonnolliselle n:lle.

3. Tiedetään, että x+1/x on kokonaisluku. Todista, että х n +1/х n on myös minkä tahansa kokonaisluvun n kokonaisluku.

Esitellään merkintä: a i \u003d x i + 1 / x i ja huomaa heti, että a i \u003d a -i, joten jatkamme puhumista luonnollisista indekseistä.

Huomautus: ja 1 on ehdon mukainen kokonaisluku; a 2 on kokonaisluku, koska a 2 \u003d (a 1) 2 -2; ja 0 = 2.

Oletetaan, että a k on kokonaisluku mille tahansa positiiviselle kokonaisluvulle k, joka ei ole suurempi kuin n. Silloin a 1 ·a n on kokonaisluku, mutta a 1 ·a n =a n+1 +a n–1 ja a n+1 =a 1 ·a n –a n–1. Kuitenkin ja n–1 on kokonaisluku induktiohypoteesin mukaan. Siten а n+1 on myös kokonaisluku. Siksi х n +1/х n on minkä tahansa kokonaisluvun n kokonaisluku, joka oli todistettava.

4. Osoita, että jokaiselle positiiviselle kokonaisluvulle n, joka on suurempi kuin 1, on kaksois-epäyhtälö

5. Todista, että luonnollisille n > 1 ja |x|

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

Arvolle n=2 epäyhtälö on tosi. Todella,

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

Jos epäyhtälö on tosi arvolle n=k, niin arvolla n=k+1 meillä on

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

Epäyhtälö on todistettu mille tahansa luonnolliselle luvulle n > 1.

6. Tasossa on n ympyrää. Todista, että millä tahansa näiden ympyröiden järjestelyllä niiden muodostama kartta voidaan värittää oikein kahdella värillä.

Käytetään matemaattisen induktion menetelmää.

Jos n = 1, väite on ilmeinen.

Oletetaan, että väite on totta mille tahansa n ympyrän muodostamalle kartalle, ja annetaan tasossa n + 1 ympyrää. Poistamalla yhden näistä ympyröistä saamme kartan, joka voidaan tehdyn oletuksen perusteella värjätä oikein kahdella värillä (katso ensimmäinen kuva alla).

Palautamme sitten hylätyn ympyrän ja sen toisella puolella, esimerkiksi sisällä, muutamme kunkin alueen värin vastakkaiseksi (katso toinen kuva). On helppo nähdä, että tässä tapauksessa saadaan oikein kahdella värillä väritetty kartta, mutta vasta nyt n + 1 ympyrällä, mikä oli todistettava.

7. Kutsumme kuperaa monikulmiota "kauniiksi", jos seuraavat ehdot täyttyvät:

1) jokainen sen kärki on maalattu yhdellä kolmesta väristä;

2) mitkä tahansa kaksi vierekkäistä kärkeä on maalattu eri väreillä;

3) vähintään yksi monikulmion kärki on väritetty kullakin kolmella värillä.

Todista, että mikä tahansa kaunis n-kulmio voidaan leikata ei-leikkaavilla lävistäjällä "kauniiksi" kolmioksi.

Käytetään matemaattisen induktion menetelmää.

induktion perusta. Vähimmälle mahdolliselle n=3:lle ongelman lause on ilmeinen: "kauniin" kolmion kärjet on maalattu kolmella eri värillä eikä leikkauksia tarvita.

Induktiohypoteesi. Oletetaan, että ongelman väite on totta mille tahansa "kauniille" n-gonille.

induktiovaihe. Tarkastellaan mielivaltaista "kaunista" (n + 1)-kulmiota ja osoita induktiivisen oletuksen avulla, että se voidaan leikata joillakin diagonaaleilla "kauniiksi" kolmioksi. Merkitään А 1 , А 2 , А 3 , … А n , А n+1 – (n+1)-kulman peräkkäiset kärjet. Jos vain yksi (n + 1)-gonin kärki on värjätty jollakin kolmesta väristä, niin yhdistämällä tämä kärki diagonaaleilla kaikkiin sen viereisiin pisteisiin, saadaan (n + 1)- tarvittava osio. mene "kauniisiin" kolmioihin.

Jos vähintään kaksi kulman (n + 1) kärkeä on maalattu kullakin kolmella värillä, merkitään kärjen A 1 väri numerolla 1 ja kärjen A 2 väri numerolla 2. . Olkoon k pienin luku, jonka kärkipiste A k on värjätty kolmannella värillä. On selvää, että k > 2. Leikataan kolmio А k–2 А k–1 А k (n+1)-kulmiosta diagonaalilla А k–2 А k . Numeron k valinnan mukaisesti tämän kolmion kaikki kärjet on maalattu kolmella eri värillä, eli tämä kolmio on "kaunis". Jäljelle jäänyt kupera n-kulmio A 1 A 2 ... A k–2 A k A k+1 ... A n+1 on myös induktiivisen oletuksen ansiosta "kaunis", mikä tarkoittaa sitä, että on jaettu "kauniisiin" kolmioihin, jotka ja piti todistaa.

8. Osoita, että kuperassa n-kulmiossa on mahdotonta valita enemmän kuin n lävistäjää siten, että millä tahansa kahdella niistä on yhteinen piste.

Suoritetaan todistus matemaattisen induktion menetelmällä.

Todistakaamme yleisempi väite: kuperassa n-kulmiossa on mahdotonta valita enemmän kuin n sivua ja diagonaalia siten, että millä tahansa kahdella niistä on yhteinen piste. Jos n = 3, väite on ilmeinen. Oletetaan, että tämä väite pätee mielivaltaiselle n-kulmiolle ja todistaa tätä käyttämällä sen pätevyys mielivaltaiselle (n + 1)-kulmiolle.

Oletetaan, että (n + 1)-gonilla tämä väite ei pidä paikkaansa. Jos (n+1)-kulman kustakin kärjestä ei esiinny enempää kuin kaksi valittua sivua tai diagonaalia, niin niitä on valittu korkeintaan n+1. Tästä syystä ainakin kolme valittua sivua tai diagonaalia AB, AC, AD nousee jostakin kärjestä A. Olkoon AC AB:n ja AD:n välissä. Koska mikään muu sivu tai diagonaali, joka tulee ulos C:stä, paitsi CA, ei voi ylittää AB:tä ja AD:ta samanaikaisesti, vain yksi valittu diagonaali CA tulee ulos C:stä.

Hylkäämällä piste C yhdessä diagonaalin CA kanssa, saadaan kupera n-kulmio, jossa valitaan enemmän kuin n sivua ja diagonaalia, joista kahdella on yhteinen piste. Siten päädymme ristiriitaan sen oletuksen kanssa, että väite on totta mielivaltaiselle konveksille n-kulmiolle.

Joten (n + 1)-gonille väite on tosi. Matemaattisen induktion periaatteen mukaisesti väite pätee mille tahansa konveksille n-kulmiolle.

9. Tasoon on piirretty n suoraa, joista ei kahta ole yhdensuuntaista eikä kolmea kulje saman pisteen kautta. Kuinka moneen osaan nämä suorat jakavat tason.

Peruspiirustusten avulla on helppo varmistaa, että yksi suora jakaa tason 2 osaan, kaksi suoraa 4 osaan, kolme suoraa 7 osaan ja neljä suoraa 11 osaan.

Merkitään N(n):llä niiden osien lukumäärä, joihin n suoraa jakaa tason. Sen voi nähdä

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

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

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

Se on luonnollista olettaa

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

tai, kuten on helppo todeta, käyttämällä kaavaa aritmeettisen etenemisen n ensimmäisen ehdon summalle,

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

Todistakaamme tämän kaavan pätevyys matemaattisen induktion menetelmällä.

Arvolle n=1 kaava on jo vahvistettu.

Kun olet tehnyt induktiivisen oletuksen, katso k + 1 riviä, jotka täyttävät tehtävän ehdon. Valitsemme niistä mielivaltaisesti k suoraa viivaa. Induktiivisen hypoteesin mukaan ne jakavat tason 1+ k(k+1)/2 osaan. Jäljelle jäävä (k + 1)-viiva jaetaan valitulla k:nnellä viivalla k + 1 osaan ja kulkee siten sen (k + 1)-osan läpi, johon taso on jo jaettu, ja jokainen nämä osat jaetaan 2 osaan, eli k+1 osaa lisätään lisää. Niin,

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

Q.E.D.

10. Lausekkeessa x 1: x 2: ...: x n toimintojen järjestystä merkitään sulkeilla ja tulos kirjoitetaan murtolukuna:

(tässä tapauksessa jokainen kirjain x 1, x 2, ..., x n on joko murtoluvun osoittajassa tai nimittäjässä). Kuinka monta erilaista lauseketta voidaan saada tällä tavalla kaikilla mahdollisilla tavoilla järjestää hakasulkeet?

Ensinnäkin on selvää, että tuloksena olevassa murtoluvussa x 1 on osoittajassa. On lähes yhtä ilmeistä, että x 2 tulee olemaan nimittäjässä missä tahansa hakasulkeiden järjestelyssä (jakomerkki ennen x 2:ta viittaa joko itse x 2:een tai mihin tahansa lausekkeeseen, joka sisältää x 2:n osoittajassa).

Voidaan olettaa, että kaikki muut kirjaimet x 3 , x 4 , ... , x n voivat sijaita osoittajassa tai nimittäjässä täysin mielivaltaisella tavalla. Tästä seuraa, että yhteensä voit saada 2 n-2 murto-osaa: jokainen n-2 kirjainta x 3, x 4, ..., x n voi olla muista riippumatta osoittajassa tai nimittäjässä.

Todistakaamme tämä väite induktiolla.

Kun n=3, saat 2 murto-osaa:

joten väite on totta.

Oletetaan, että se pätee n=k:lle ja todistetaan se n=k+1:lle.

Kirjoitetaan lauseke x 1: x 2: ...: x k jonkin sulkujärjestyksen jälkeen murtolukuna Q. Jos x k: x k+1 korvataan tähän lausekkeeseen x k:n sijaan, niin x k on sama paikka kuin se oli murtoluvuissa Q, ja x k + 1 ei ole siellä, missä x k oli (jos x k oli nimittäjässä, niin x k + 1 on osoittajassa ja päinvastoin).

Osoitetaan nyt, että voimme lisätä x k+1 samaan paikkaan kuin x k . Murtoluvussa Q sulujen asettamisen jälkeen tulee välttämättä lauseke muotoa q:x k, jossa q on kirjain x k–1 tai jokin suluissa oleva lauseke. Korvaamalla q: x k lausekkeella (q: x k): x k + 1 = q: (x k x k + 1), saadaan ilmeisesti sama murto-osa Q, jossa x k:n sijaan on x k x k+1 .

Näin ollen mahdollisten murto-osien lukumäärä tapauksessa n=k+1 on 2 kertaa suurempi kuin tapauksessa n=k ja on yhtä suuri kuin 2 k–2 ·2=2 (k+1)–2 . Näin väite on todistettu.

Vastaus: 2 n-2 murto-osaa.

Ongelmia ilman ratkaisuja

1. Todista, että mille tahansa luonnolliselle n:lle:

a) luku 5 n -3 n + 2n on jaollinen 4:llä;

b) luku n 3 +11n on jaollinen 6:lla;

c) luku 7 n +3n–1 on jaollinen 9:llä;

d) luku 6 2n +19 n –2 n+1 on jaollinen luvulla 17;

e) luku 7 n+1 +8 2n–1 on jaollinen luvulla 19;

f) luku 2 2n–1 –9n 2 +21n–14 on jaollinen luvulla 27.

2. Todista, että (n+1)·(n+2)· …·(n+n) = 2 n ·1·3·5·…·(2n–1).

3. Todista epäyhtälö |sin nx| n|sinx| mille tahansa luonnolliselle n.

4. Etsi luonnolliset luvut a, b, c, jotka eivät ole jaollisia 10:llä ja niin, että minkä tahansa luonnollisen n:n luvuilla a n + b n ja c n on samat kaksi viimeistä numeroa.

5. Osoita, että jos n pistettä ei ole samalla suoralla, niin niitä yhdistävien suorien joukossa on vähintään n erilaista.

Bibliografinen kuvaus: Badanin AS, Sizova M. Yu. Matemaattisen induktion menetelmän soveltaminen luonnollisten lukujen jaollisuusongelmien ratkaisemiseen // Nuori tiedemies. 2015. №2. S. 84-86..04.2019).

Matemaattisissa olympialaisissa kohdataan usein varsin vaikeita ongelmia luonnollisten lukujen jaollisuuden todistamisessa. Koululaiset kohtaavat ongelman: kuinka löytää universaali matemaattinen menetelmä, joka mahdollistaa tällaisten ongelmien ratkaisemisen?

Osoittautuu, että useimmat jako-ongelmat voidaan ratkaista matemaattisella induktiolla, mutta koulukirjoissa tähän menetelmään kiinnitetään vain vähän huomiota, useimmiten annetaan lyhyt teoreettinen kuvaus ja analysoidaan useita ongelmia.

Löydämme matemaattisen induktion menetelmän lukuteoriasta. Lukuteorian kynnyksellä matemaatikot löysivät monia tosiasioita induktiivisesti: L. Euler ja K. Gauss pohdiskelivat joskus tuhansia esimerkkejä ennen kuin huomasivat numeerisen kuvion ja uskoivat siihen. Mutta samalla he ymmärsivät, kuinka harhaanjohtavia hypoteesit voivat olla, jos he läpäisevät "lopullisen" testin. Induktiivinen siirtyminen äärelliselle osajoukolle vahvistetusta lauseesta samanlaiseen lauseeseen koko äärettömälle joukolle tarvitaan todiste. Tätä menetelmää ehdotti Blaise Pascal, joka löysi yleisen algoritmin minkä tahansa kokonaisluvun jaollisuuden kriteerien löytämiseksi millä tahansa muulla kokonaisluvulla (käsitelmä "Lukujen jaollisuuden luonteesta").

Matemaattisen induktion menetelmällä todistetaan perustelemalla tietyn väitteen totuus kaikille luonnollisille luvuille tai jostakin luvusta n alkavan väitteen totuus.

Tehtävien ratkaiseminen tietyn väitteen totuuden todistamiseksi matemaattisen induktion menetelmällä koostuu neljästä vaiheesta (kuva 1):

Riisi. 1. Kaava ongelman ratkaisemiseksi

1. Induktion perusteet . Tarkista lauseen pätevyys pienimmän luonnollisen luvun osalta, jolle lauseessa on järkeä.

2. Induktiivinen oletus . Oletetaan, että väite on tosi jollekin k:n arvolle.

3. induktiivinen siirtymä . Osoitamme, että väite on totta k+1:lle.

4. Johtopäätös . Jos tällainen todistus on suoritettu loppuun, niin matemaattisen induktion periaatteen perusteella voidaan väittää, että väite on totta mille tahansa luonnolliselle luvulle n.

Harkitse matemaattisen induktion menetelmän soveltamista ongelmien ratkaisemiseen luonnollisten lukujen jaollisuuden osoittamiseksi.

Esimerkki 1. Osoita, että luku 5 on luvun 19 kerrannainen, missä n on luonnollinen luku.

Todiste:

1) Tarkistetaan, että tämä kaava on tosi, kun n = 1: luku =19 on luvun 19 kerrannainen.

2) Olkoon tämä kaava tosi, kun n = k, eli luku on luvun 19 kerrannainen.

Jaollinen luvulla 19. Itse asiassa ensimmäinen termi on jaollinen luvulla 19 johtuen oletuksesta (2); Toinen termi on myös jaollinen luvulla 19, koska se sisältää kertoimen 19.

Esimerkki 2 Osoita, että kolmen peräkkäisen luonnollisen luvun kuutioiden summa on jaollinen 9:llä.

Todiste:

Todistakaamme väite: ”Millä tahansa luonnollisella luvulla n lauseke n 3 +(n+1) 3 +(n+2) 3 on luvun 9 kerrannainen.

1) Tarkista, että tämä kaava on oikea arvolle n = 1: 1 3 +2 3 +3 3 =1+8+27=36 on luvun 9 kerrannainen.

2) Olkoon tämä kaava tosi, kun n = k, eli k 3 +(k+1) 3 +(k+2) 3 on luvun 9 kerrannainen.

3) Osoitetaan, että kaava pätee myös n = k + 1:lle, eli (k+1) 3 +(k+2) 3 +(k+3) 3 on luvun 9 kerrannainen. (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 +3 k+ 3).

Tuloksena oleva lauseke sisältää kaksi termiä, joista jokainen on jaollinen 9:llä, joten summa on jaollinen 9:llä.

4) Molemmat matemaattisen induktion periaatteen ehdot täyttyvät, joten väite pätee kaikkiin n:n arvoihin.

Esimerkki 3 Osoita, että millä tahansa luonnollisella n:llä luku 3 2n+1 +2 n+2 on jaollinen 7:llä.

Todiste:

1) Tarkista, että tämä kaava on oikea arvolle n = 1: 3 2*1+1 +2 1+2 = 3 3 +2 3 =35, 35 on 7:n kerrannainen.

2) Olkoon tämä kaava tosi, kun n = k, eli 3 2 k +1 +2 k +2 on jaollinen 7:llä.

3) Osoitetaan, että kaava pätee myös n = k + 1:lle, ts.

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. Koska (3 2 k +1 +2 k +2) 9 on jaollinen 7:llä ja 7 2 k +2 on jaollinen 7:llä, niin niiden ero on myös jaollinen 7:llä.

4) Molemmat matemaattisen induktion periaatteen ehdot täyttyvät, joten väite pätee kaikkiin n:n arvoihin.

On kätevää ratkaista monia todistusongelmia luonnollisten lukujen jakoteoriassa matemaattisen induktion menetelmällä, voidaan jopa sanoa, että ongelmien ratkaiseminen tällä menetelmällä on melko algoritmista, riittää, että suoritetaan 4 perusvaihetta. Mutta tätä menetelmää ei voida kutsua universaaliksi, koska siinä on myös haittoja: ensinnäkin on mahdollista todistaa vain luonnollisten lukujen joukolla, ja toiseksi on mahdollista todistaa vain yhdelle muuttujalle.

Loogisen ajattelun, matemaattisen kulttuurin kehittämiseksi tämä menetelmä on välttämätön työkalu, koska jopa suuri venäläinen matemaatikko A. N. Kolmogorov sanoi: "Ymmärrys ja kyky soveltaa oikein matemaattisen induktion periaatetta on hyvä kriteeri loogiselle kypsuudelle, joka on ehdottoman välttämätöntä matematiikan kannalta."

Kirjallisuus:

1. Vilenkin N. Ya. Induktio. Kombinatoriikka. - M.: Enlightenment, 1976. - 48 s.

2. Genkin L. Matemaattisesta induktiosta. - M., 1962. - 36 s.

3. Solominsky I. S. Matemaattisen induktion menetelmä. - M.: Nauka, 1974. - 63 s.

4. Sharygin I. F. Valinnainen matematiikan kurssi: Ongelmanratkaisu: Oppikirja 10 solulle. keskikoulu - M.: Enlightenment, 1989. - 252 s.

5. Shen A. Matemaattinen induktio. - M.: MTSNMO, 2007.- 32 s.

Johdanto

Pääosa

1. Täydellinen ja epätäydellinen induktio

2. Matemaattisen induktion periaate

3. Matemaattisen induktion menetelmä

4. Esimerkkien ratkaisu

5. Tasa-arvot

6. Numeroiden jako

7. Epätasa-arvo

Johtopäätös

Luettelo käytetystä kirjallisuudesta

Johdanto

Mutta tämä on niin tärkeää - pystyä ajattelemaan induktiivisesti.

Pääosa

Vaaditaan, että jokainen luonnollinen parillinen luku n sisällä 4< n < 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения:

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.

Nämä yhdeksän yhtälöä osoittavat, että jokainen meitä kiinnostavista luvuista on todellakin esitetty kahden alkutermin summana.

Täydellinen induktio on siis sitä, että yleinen väite todistetaan erikseen jokaisessa äärellisessä määrässä mahdollisia tapauksia.

Joskus yleinen tulos voidaan ennustaa, kun ei ole otettu huomioon kaikkia, vaan suuri määrä erikoistapauksia (ns. epätäydellinen induktio).

Olkoon esimerkiksi, että on löydettävä ensimmäisen n peräkkäisen parittoman luvun summa. Harkitse erikoistapauksia:

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

Näiden muutaman erikoistapauksen tarkastelun jälkeen tulee seuraava yleinen johtopäätös:

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

nuo. ensimmäisen n peräkkäisen parittoman luvun summa on n 2

Tehty havainto ei tietenkään voi vielä toimia todisteena yllä olevan kaavan pätevyydestä.

Monissa tapauksissa ulospääsy tällaisesta vaikeudesta on turvautua erityiseen päättelymenetelmään, jota kutsutaan matemaattisen induktion menetelmäksi. Se on seuraava.

1 = 3. Tämä tarkoittaa lauseen pätevyyttä n=4:lle ja niin edelleen. On selvää, että lopulta saavutamme minkä tahansa luonnollisen luvun n. Näin ollen väite on totta mille tahansa n:lle.

Yhteenvetona sanotusta muotoilemme seuraavan yleisperiaatteen.

Matemaattisen induktion periaate.

Jos lause A( n ) luonnollisesta luvusta riippuen n , totta n =1 ja siitä, että se on totta n=k (missä k -mikä tahansa luonnollinen luku), tästä seuraa, että se on totta myös seuraavalle numerolle n=k+1 , sitten oletus A( n ) on totta mille tahansa luonnolliselle luvulle n .

Monissa tapauksissa saattaa olla tarpeen todistaa tietyn väitteen pätevyys ei kaikille luonnollisille luvuille, vaan vain n>p:lle, jossa p on kiinteä luonnollinen luku. Tässä tapauksessa matemaattisen induktion periaate on muotoiltu seuraavasti. Jos lause A( n ) pitää paikkansa n = p ja jos A( k ) Þ MUTTA( k+1) kenelle tahansa k>p, sitten lause A( n) totta kenelle tahansa n>p.

ESIMERKKI 1

Todista, että 1+3+5+…+(2n-1)=n 2 .

Ratkaisu: 1) Meillä on n=1=1 2 . Näin ollen

lause on tosi, kun n=1, ts. A(1) on totta.

2) Osoitetaan, että A(k)ÞA(k+1).

Olkoon k mikä tahansa luonnollinen luku ja olkoon lause tosi kun n=k, ts.

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

Osoitetaan, että silloin väite pätee myös seuraavalle luonnolliselle luvulle n=k+1, ts. mitä

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

Todellakin,

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

Joten A(k)ÞA(k+1). Matemaattisen induktion periaatteen perusteella päättelemme, että oletus A(n) on totta mille tahansa nОN:lle.

ESIMERKKI 2

Todista se

1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), missä x¹1

Ratkaisu: 1) Saat n=1:lle

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

siksi n = 1:lle kaava on tosi; A(1) on totta.

2) Olkoon k mikä tahansa luonnollinen luku ja olkoon kaava tosi, kun n=k, ts.

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

Todistakaamme, että sitten tasa-arvo

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

Todellakin

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).

Joten A(k)ÞA(k+1). Matemaattisen induktion periaatteen perusteella päätämme, että kaava on totta mille tahansa luonnolliselle luvulle n.

ESIMERKKI 3

Osoita, että kuperan n-kulman lävistäjien lukumäärä on n(n-3)/2.

Ratkaisu: 1) Kun n=3, väite on tosi

Ja 3 on oikein, koska kolmiossa

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

2 A(3) on totta.

2) Oletetaan, että missä tahansa

kupera k-gon on-

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

A k Todistetaan, että silloin konveksissa

(k+1)-gon luku

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

Olkoon А 1 А 2 А 3 …A k A k+1 -kupera (k+1)-kulma. Piirretään siihen diagonaali A 1 A k. Laskeaksesi tämän (k + 1)-gonin diagonaalien kokonaismäärän, sinun on laskettava lävistäjät k-gonissa A 1 A 2 ...A k , lisätään k-2 saatuun lukuun, ts. Huomioon tulee ottaa kärjestä A k+1 lähtevän (k+1)-gonin lävistäjät ja lisäksi diagonaali A 1 A k.

Tällä tavalla,

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

Joten A(k)ÞA(k+1). Matemaattisen induktion periaatteesta johtuen väite pätee mille tahansa konveksille n-kulmiolle.

ESIMERKKI 4

Todista, että mille tahansa n:lle lause on tosi:

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

Ratkaisu: 1) Olkoon sitten n=1

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

Näin ollen n=1:lle väite on tosi.

2) Oletetaan, että n=k

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

3) Tarkastellaan tätä lausetta n=k+1:lle

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)(2k2 +7k+6)/6=(k+1)(2(k+3/2)(k+)

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

Olemme todistaneet yhtälön pätevyyden n=k+1:lle, joten matemaattisen induktion menetelmän perusteella väite pätee mille tahansa luonnolliselle n:lle.

ESIMERKKI 5

Todista, että minkä tahansa luonnollisen n:n yhtäläisyys on totta:

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

Ratkaisu: 1) Olkoon n=1.

Sitten X 1 = 1 3 = 1 2 (1+1) 2 /4 = 1.

Näemme, että n=1:lle väite on tosi.

2) Oletetaan, että yhtälö on tosi, kun n=k

Luento 6. Matemaattisen induktion menetelmä.

Tieteessä ja elämässä uutta tietoa saadaan eri tavoin, mutta ne kaikki (jos et mene yksityiskohtiin) on jaettu kahteen tyyppiin - siirtyminen yleisestä erityiseen ja erityisestä yleiseen. Ensimmäinen on deduktio, toinen on induktio. Deduktiivista päättelyä kutsutaan yleensä matematiikassa looginen päättely, ja matemaattisessa tieteessä päättely on ainoa laillinen tutkimusmenetelmä. Loogisen päättelyn säännöt muotoili kaksi ja puoli tuhatta vuotta sitten antiikin kreikkalainen tiedemies Aristoteles. Hän loi täydellisen luettelon yksinkertaisimmista oikeista päätelmistä, syllogismit– logiikan "tiilet", samalla osoittavat tyypillisiä päättelyjä, jotka ovat hyvin samanlaisia kuin oikeat, mutta väärät (tällaista "pseudologista" päättelyä kohtaamme usein mediassa).

Induktio (induktio - latinaksi opastusta) havainnollistaa tunnettu legenda siitä, kuinka Isaac Newton muotoili yleisen gravitaatiolain sen jälkeen, kun omena putosi hänen päähänsä. Toinen esimerkki fysiikasta: sellaisessa ilmiössä kuin sähkömagneettinen induktio, sähkökenttä luo, "indusoi" magneettikentän. "Newtonin omena" on tyypillinen esimerkki tilanteesta, jossa yksi tai useampi erikoistapaus, ts. havainnot, "johtaa" yleiseen lausuntoon, yleinen johtopäätös tehdään yksittäisten tapausten perusteella. Induktiivinen menetelmä on tärkein yleisten mallien saamiseksi sekä luonnontieteissä että humanistisissa tieteissä. Mutta sillä on erittäin merkittävä haittapuoli: yksittäisten esimerkkien perusteella voidaan tehdä väärä johtopäätös. Yksityisistä havainnoista johtuvat hypoteesit eivät aina pidä paikkaansa. Harkitse esimerkkiä Eulerin johdosta.

Laskemme trinomin arvon joillekin ensimmäisille arvoille n:

Huomaa, että laskelmien tuloksena saadut luvut ovat alkulukuja. Ja se voidaan suoraan tarkistaa jokaisen kohdalla n 1-39 polynomiarvo
on alkuluku. Kuitenkin milloin n=40 saadaan luku 1681=41 2 , joka ei ole alkuluku. Siten hypoteesi, joka voisi syntyä tässä, eli hypoteesi, että jokaiselle n määrä
on yksinkertainen, osoittautuu vääräksi.

Leibniz osoitti 1600-luvulla, että jokaiselle positiiviselle kokonaisluvulle n määrä
jaollinen 3:lla
on jaollinen 5:llä ja niin edelleen. Tämän perusteella hän ehdotti, että jokaiseen parilliseen k ja mikä tahansa luonnollinen n määrä
jaettuna k, mutta huomasin sen pian
ei ole jaollinen 9:llä.

Tarkastettujen esimerkkien avulla voimme tehdä tärkeän johtopäätöksen: väite voi olla totta useissa erikoistapauksissa ja samalla yleisesti epäoikeudenmukainen. Kysymys lausunnon pätevyydestä yleisessä tapauksessa voidaan ratkaista käyttämällä erityistä päättelymenetelmää nimeltä matemaattisen induktion avulla(täydellinen induktio, täydellinen induktio).

6.1. Matemaattisen induktion periaate.

♦ Matemaattisen induktion menetelmä perustuu matemaattisen induktion periaate , joka koostuu seuraavista:

1) tämän lausunnon pätevyys on varmistettun=1 (induktioperusteisesti) ,

2) tämän väitteen oletetaan pitävän paikkansan= k, missäkon mielivaltainen luonnollinen luku 1(induktio-oletus) , ja tämä oletus huomioon ottaen sen pätevyys vahvistetaann= k+1.

Todiste. Oletetaan päinvastoin, eli oletetaan, että väite ei ole totta jokaiselle luonnolle n. Sitten on sellainen luonnollinen m, mitä:

1) hyväksyntä n=m epäreilua,

2) kaikille n, pienempi m, väite on totta (toisin sanoen m on ensimmäinen luonnollinen luku, jonka väite epäonnistuu).

Se on selvää m>1, koska varten n=1 väite on tosi (ehto 1). Näin ollen
- luonnollinen luku. Se käy ilmi luonnolliselle luvulle
lause on tosi, ja seuraavalle luonnolliselle luvulle m se on epäreilua. Tämä on ristiriidassa ehdon 2 kanssa. ■

Huomaa, että todistuksessa käytettiin aksioomaa, että mikä tahansa luonnollisten lukujen kokoelma sisältää pienimmän luvun.

Matemaattisen induktion periaatteeseen perustuvaa todistusta kutsutaan täydellisellä matemaattisella induktiolla .

 Esimerkki6.1. Todista se kaikille luonnollisille n määrä
on jaollinen 3:lla.

Ratkaisu.

1) Milloin n=1, niin a 1 on jaollinen 3:lla ja lause on tosi n=1.

2) Oletetaan, että väite pitää paikkansa n=k,
, eli tuo numero
on jaollinen kolmella ja löydä se n=k+1 luku on jaollinen 3:lla.

Todellakin,

Koska jokainen termi on jaollinen 3:lla, niin niiden summa on myös jaollinen 3:lla. ■ 

 Esimerkki6.2. Todista, että ensimmäisen summa n luonnolliset parittomat luvut on yhtä suuri kuin niiden lukumäärän neliö, eli .

Ratkaisu. Käytämme täydellisen matemaattisen induktion menetelmää.

1) Tarkistamme tämän lausunnon oikeellisuuden n=1: 1=1 2 on oikein.

2) Oletetaan, että ensimmäisen summa k (
) parittomien lukujen on yhtä suuri kuin näiden lukujen lukumäärän neliö, eli . Tämän yhtäläisyyden perusteella määritämme, että ensimmäisen summa k+1 parittomat luvut on yhtä suuri kuin
, tuo on .

Käytämme oletustamme ja saamme

. ■ 

Täydellisen matemaattisen induktion menetelmää käytetään joidenkin epäyhtälöiden todistamiseen. Todistakaamme Bernoullin epätasa-arvo.

 Esimerkki6.3. Todista, että milloin
ja mikä tahansa luonnollinen n eriarvoisuutta
(Bernoullin epätasa-arvo).

Ratkaisu. 1) Milloin n=1 saamme
, kumpi on oikein.

2) Oletetaan, että klo n=k on epätasa-arvoa
(*). Tätä olettamusta käyttämällä todistamme sen
. Huomaa, että milloin
tämä epätasa-arvo pätee, ja siksi tapauksen tarkastelu riittää
.

Kerro molemmat epäyhtälön osat (*) numerolla
ja saada:

Eli (1+
.■ 

Todistus menetelmällä epätäydellinen matemaattinen induktio jokin väite riippuen n, missä
suoritetaan samalla tavalla, mutta alussa oikeus perustetaan pienimmälle arvolle n.

Jotkut ongelmat eivät muotoile eksplisiittisesti väitettä, joka voidaan todistaa matemaattisella induktiolla. Tällaisissa tapauksissa on tarpeen vahvistaa säännöllisyys ja esittää hypoteesi tämän säännönmukaisuuden pätevyydestä ja sitten testata ehdotettu hypoteesi matemaattisen induktion menetelmällä.

 Esimerkki6.4. Etsi summa
.

Ratkaisu. Etsitään summat S 1 , S 2 , S 3. Meillä on
,
,
. Oletamme, että kaikki luonnolliset n kaava on voimassa
. Tämän hypoteesin testaamiseksi käytämme täydellisen matemaattisen induktion menetelmää.

1) Milloin n=1 hypoteesi on totta, koska
.

2) Oletetaan, että hypoteesi pitää paikkansa n=k,
, tuo on
. Käyttämällä tätä kaavaa vahvistamme, että hypoteesi on totta ja for n=k+1, eli

Todellakin,

Olettaen siis, että hypoteesi pitää paikkansa n=k,
, on todistettu, että se pitää paikkansa n=k+1, ja matemaattisen induktion periaatteen perusteella päätämme, että kaava pätee mille tahansa luonnolliselle n. ■ 

 Esimerkki6.5. Matematiikassa on todistettu, että kahden tasaisesti jatkuvan funktion summa on tasaisesti jatkuva funktio. Tämän väitteen perusteella meidän on todistettava, että minkä tahansa luvun summa
Tasaisesti jatkuvien funktioiden funktio on tasaisesti jatkuva funktio. Mutta koska emme ole vielä ottaneet käyttöön "tasaisesti jatkuvan funktion" käsitettä, asetetaan ongelma abstraktimmin: tiedetään, että kahden funktion summa, joilla on jokin ominaisuus S, itsellään on omaisuutta S. Osoittakaamme, että minkä tahansa määrän funktioiden summalla on ominaisuus S.

Ratkaisu. Induktion perusta tässä on jo ongelman muotoilussa. Induktiivisen oletuksen tekeminen, harkitse
toimintoja f 1 , f 2 , …, f n , f n+1, joilla on omaisuus S. Sitten . Oikealla puolella ensimmäisellä termillä on omaisuus S induktiohypoteesin mukaan toisella termillä on ominaisuus S ehdon mukaan. Siksi heidän summalla on omaisuus S– kahdella termillä induktion peruste "toimii".

Tämä vahvistaa väitteen ja käyttää sitä edelleen. ■ 

 Esimerkki6.6. Löydä kaikki luonnolliset n, jolle epätasa-arvo

Ratkaisu. Harkitse n=1, 2, 3, 4, 5, 6. Meillä on: 2 1 >1 2, 2 2 =2 2, 2 3<3 2 , 2 4 =4 2 , 2 5 >5 2 , 2 6 >6 2 . Siten voimme tehdä hypoteesin: epätasa-arvo
on paikka kaikille
. Tämän hypoteesin totuuden todistamiseksi käytämme epätäydellisen matemaattisen induktion periaatetta.

1) Kuten edellä todettiin, tämä hypoteesi pitää paikkansa n=5.

2) Oletetaan, että se pitää paikkansa n=k,
eli epätasa-arvoa
. Tätä olettamusta käyttämällä todistamme, että epätasa-arvo
.

T. to.
ja klo
on epätasa-arvoa

klo
,

sitten saamme sen
. Eli hypoteesin totuus n=k+1 seuraa oletuksesta, että se pitää paikkansa n=k,
.

Alkaen pp. 1 ja 2 epätäydellisen matemaattisen induktion periaatteeseen perustuen seuraa, että epäyhtälö
totta kaikille luonnollisille
. ■ 

 Esimerkki6.7. Todista se mille tahansa luonnolliselle luvulle n erotuskaava on pätevä
.

Ratkaisu. klo n=1 tällä kaavalla on muoto
, tai 1=1, eli se on totta. Induktiivisen oletuksen perusteella meillä on:

Q.E.D. ■ 

 Esimerkki6.8. Todista, että joukko koostuu n elementtejä, on osajoukkoja.

Ratkaisu. Setti, jossa on yksi elementti a, sisältää kaksi alajoukkoa. Tämä on totta, koska kaikki sen osajoukot ovat tyhjä joukko ja itse joukko, ja 2 1 =2.

Oletamme, että mikä tahansa joukko n elementtejä on osajoukkoja. Jos joukko A koostuu n+1 elementtejä, sitten kiinnitämme siihen yhden elementin - merkitse se d, ja jaa kaikki osajoukot kahteen luokkaan - ei sisällä d ja sisältävät d. Kaikki ensimmäisen luokan osajoukot ovat joukon B osajoukkoja, jotka saadaan A:sta poistamalla elementti d.

Sarja B koostuu n elementtejä, ja siksi sillä on induktiohypoteesin mukaan osajoukkoja, joten ensimmäisessä luokassa osajoukkoja.

Mutta toisessa luokassa on sama määrä osajoukkoja: jokainen niistä saadaan täsmälleen yhdestä ensimmäisen luokan osajoukosta lisäämällä elementti d. Siksi yhteensä sarja A
osajoukkoja.

Näin väite on todistettu. Huomaa, että se pätee myös joukolle, joka koostuu 0 alkiosta - tyhjä joukko: sillä on yksi osajoukko - itse ja 2 0 =1. ■ 