Metóda matematickej indukcie

Úvod

Hlavná časť

1. Úplná a neúplná indukcia
2. Princíp matematickej indukcie
3. Metóda matematickej indukcie
4. Riešenie príkladov
5. Rovnosť
6. Delenie čísel
7. nerovnosti

Záver

Zoznam použitej literatúry

Úvod

Deduktívne a induktívne metódy sú základom každého matematického výskumu. Deduktívnou metódou uvažovania je uvažovanie od všeobecného k jednotlivému, t.j. uvažovanie, ktorého východiskom je všeobecný výsledok a konečným bodom konkrétny výsledok. Indukcia sa uplatňuje pri prechode od konkrétnych výsledkov k všeobecným, t.j. je opakom deduktívnej metódy.

Metódu matematickej indukcie možno porovnať s pokrokom. Začíname od najnižšieho, výsledkom logického myslenia sa dostávame k najvyššiemu. Človek sa vždy snažil o pokrok, o schopnosť logicky rozvíjať svoje myslenie, čo znamená, že samotná príroda mu predurčila myslieť induktívne.

Hoci sa oblasť použitia metódy matematickej indukcie rozrástla, v školských osnovách sa jej venuje málo času. Povedzme, že užitočného človeka privedú tie dve-tri lekcie, na ktoré si vypočuje päť slov z teórie, vyrieši päť primitívnych problémov a v dôsledku toho dostane päťku za to, že nič nevie.

Ale toto je také dôležité – vedieť myslieť induktívne.

Hlavná časť

Vo svojom pôvodnom význame sa slovo „indukcia“ používa na uvažovanie, ktorým sa získavajú všeobecné závery založené na množstve konkrétnych tvrdení. Najjednoduchšou metódou uvažovania tohto druhu je úplná indukcia. Tu je príklad takéhoto uvažovania.

Nech je potrebné stanoviť, že každé prirodzené párne číslo n v rámci 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.

Týchto deväť rovnosti ukazuje, že každé z čísel, ktoré nás zaujímajú, je skutočne reprezentované ako súčet dvoch prvočísel.

Úplnou indukciou teda je, že všeobecné tvrdenie je dokázané oddelene v každom z konečného počtu možných prípadov.

Niekedy možno všeobecný výsledok predpovedať po zvážení nie všetkých, ale skôr veľkého počtu špeciálnych prípadov (tzv. neúplná indukcia).

Výsledok získaný neúplnou indukciou však zostáva iba hypotézou, kým sa nepreukáže exaktným matematickým uvažovaním, pokrývajúcim všetky špeciálne prípady. Inými slovami, neúplná indukcia v matematike sa nepovažuje za legitímnu metódu rigorózneho dokazovania, ale je mocnou metódou na objavovanie nových právd.

Nech je napríklad potrebné nájsť súčet prvých n po sebe idúcich nepárnych čísel. Zvážte špeciálne prípady:

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

Po zvážení týchto niekoľkých špeciálnych prípadov sa navrhuje nasledujúci všeobecný záver:

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

tie. súčet prvých n po sebe idúcich nepárnych čísel je n 2

Samozrejme, uskutočnené pozorovanie ešte nemôže slúžiť ako dôkaz platnosti vyššie uvedeného vzorca.

Úplná indukcia má v matematike len obmedzené aplikácie. Mnoho zaujímavých matematických tvrdení pokrýva nekonečný počet špeciálnych prípadov a my nemôžeme testovať nekonečný počet prípadov. Neúplná indukcia často vedie k chybným výsledkom.

V mnohých prípadoch je východiskom z tohto druhu ťažkostí uchýliť sa k špeciálnej metóde uvažovania, nazývanej metóda matematickej indukcie. Je to nasledovné.

Nech je potrebné dokázať platnosť určitého tvrdenia pre ľubovoľné prirodzené číslo n (napr. treba dokázať, že súčet prvých n nepárnych čísel sa rovná n 2). Priame overenie tohto tvrdenia pre každú hodnotu n nie je možné, pretože množina prirodzených čísel je nekonečná. Na dôkaz tohto tvrdenia najskôr skontrolujte jeho platnosť pre n=1. Potom je dokázané, že pre akúkoľvek prirodzenú hodnotu k, platnosť uvažovaného tvrdenia pre n=k implikuje jeho platnosť aj pre n=k+1.

Potom sa tvrdenie považuje za preukázané pre všetky n. Toto tvrdenie skutočne platí pre n=1. Potom však platí aj pre ďalšie číslo n=1+1=2. Platnosť tvrdenia pre n=2 implikuje jeho platnosť pre n=2+

1=3. To znamená platnosť tvrdenia pre n=4 atď. Je jasné, že nakoniec sa dostaneme k akémukoľvek prirodzenému číslu n. Preto tvrdenie platí pre každé n.

Zhrnutím toho, čo bolo povedané, sformulujeme nasledujúci všeobecný princíp.

Princíp matematickej indukcie.

Ak veta A(n), ktorá závisí od prirodzeného čísla n, platí pre n=1 a z toho, že platí pre n=k (kde k je ľubovoľné prirodzené číslo), vyplýva, že je aj platí pre nasledujúce číslo n=k +1, potom Predpoklad A(n) platí pre každé prirodzené číslo n.

V mnohých prípadoch môže byť potrebné dokázať platnosť určitého tvrdenia nie pre všetky prirodzené čísla, ale iba pre n>p, kde p je pevné prirodzené číslo. V tomto prípade je princíp matematickej indukcie formulovaný nasledovne.

Ak výrok A(n) platí pre n=p a ak A(k)ÞA(k+1) pre ľubovoľné k>p, potom výrok A(n) platí pre ľubovoľné n>p.

Dôkaz metódou matematickej indukcie sa vykonáva nasledovne. Najprv sa skontroluje tvrdenie, ktoré sa má dokázať, na n=1, t.j. je potvrdená pravdivosť výroku A(1). Táto časť dôkazu sa nazýva indukčná báza. Potom nasleduje časť dôkazu nazývaná indukčný krok. V tejto časti je dokázaná platnosť tvrdenia pre n=k+1 za predpokladu, že tvrdenie platí pre n=k (induktívny predpoklad), t.j. dokázať, že A(k)ÞA(k+1).

Dokážte, že 1+3+5+…+(2n-1)=n 2 .

Riešenie: 1) Máme n=1=1 2 . teda

tvrdenie je pravdivé pre n=1, t.j. A(1) je pravda.

2) Dokážme, že A(k)ÞA(k+1).

Nech k je ľubovoľné prirodzené číslo a výrok nech platí pre n=k, t.j.

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

Dokážme, že potom tvrdenie platí aj pre ďalšie prirodzené číslo n=k+1, t.j. čo

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

Naozaj,

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

Takže A(k)ÞA(k+1). Na základe princípu matematickej indukcie sme dospeli k záveru, že predpoklad A(n) platí pre akékoľvek nОN.

Dokáž to

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

Riešenie: 1) Pre n=1 dostaneme

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

preto pre n=1 platí vzorec; A(1) je pravda.

2) Nech k je ľubovoľné prirodzené číslo a vzorec nech platí pre n=k, t.j.

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

Dokážme, že potom tá rovnosť

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

Naozaj

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

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

Takže A(k)ÞA(k+1). Na základe princípu matematickej indukcie sme dospeli k záveru, že vzorec platí pre akékoľvek prirodzené číslo n.

Dokážte, že počet uhlopriečok konvexného n-uholníka je n(n-3)/2.

Riešenie: 1) Pre n=3 je tvrdenie pravdivé

A 3 je správne, pretože v trojuholníku

 A 3 =3(3-3)/2=0 uhlopriečok;

A 2 A(3) je pravdivé.

2) Predpokladajme, že v akomkoľvek

konvexný k-uholník má-

A 1 sya A k \u003d k (k-3) / 2 uhlopriečky.

A k Dokážme, že potom v konvexnom

(k+1)-gon číslo

uhlopriečky A k+1 =(k+1)(k-2)/2.

Nech А 1 А 2 А 3 …A k A k+1 -konvexný (k+1)-uhol. Narysujme do nej uhlopriečku A 1 A k. Na spočítanie celkového počtu uhlopriečok tohto (k + 1)-uholníka je potrebné spočítať počet uhlopriečok v k-uholníku A 1 A 2 ...A k , k výslednému číslu pripočítať k-2, t.j. treba brať do úvahy počet uhlopriečok (k+1)-uholníka vychádzajúceho z vrcholu A k+1 a navyše uhlopriečku A 1 A k.

teda

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

Takže A(k)ÞA(k+1). Vzhľadom na princíp matematickej indukcie je tvrdenie pravdivé pre akýkoľvek konvexný n-uholník.

Dokážte, že pre akékoľvek n je tvrdenie pravdivé:

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

Riešenie: 1) Nech n=1

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

Pre n=1 je teda tvrdenie pravdivé.

2) Predpokladajme, že n=k

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

3) Uvažujme toto tvrdenie pre n=k+1

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

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

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

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

Dokázali sme platnosť rovnosti pre n=k+1, preto na základe metódy matematickej indukcie platí tvrdenie pre každé prirodzené n.

Dokážte, že pre akékoľvek prirodzené n platí rovnosť:

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

Riešenie: 1) Nech n=1.

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

Vidíme, že pre n=1 je tvrdenie pravdivé.

2) Predpokladajme, že rovnosť platí pre n=k

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

3) Dokážme pravdivosť tohto tvrdenia pre n=k+1, t.j.

Xk+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.

Z vyššie uvedeného dôkazu je zrejmé, že tvrdenie platí pre n=k+1, teda rovnosť platí pre akékoľvek prirodzené n.

Dokáž to

((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), kde n>2.

Riešenie: 1) Pre n=2 identita vyzerá takto: (2 3 +1)/(2 3 -1)=(3´2´3)/2(2 2 +2+1),

tie. je to správne.

2) Predpokladajme, že výraz platí pre n=k

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

3) Dokážeme správnosť výrazu pre 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).

Dokázali sme platnosť rovnosti pre n=k+1, preto vzhľadom na metódu matematickej indukcie platí tvrdenie pre ľubovoľné n>2

Dokáž to

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

pre akékoľvek prirodzené n.

Riešenie: 1) Nech n=1

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

2) Predpokladajme, že n=k

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

3) Dokážme pravdivosť tohto tvrdenia pre 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).

Dokázaná je aj platnosť rovnosti pre n=k+1, preto tvrdenie platí pre ľubovoľné prirodzené číslo n.

Dokážte platnosť totožnosti

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

pre akékoľvek prirodzené n.

1) Pre n=1 je identita pravdivá 1 2 /1´3=1(1+1)/2(2+1).

2) Predpokladajme, že pre n=k

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

3) Dokážme, že totožnosť platí pre 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).

Z vyššie uvedeného dôkazu je zrejmé, že tvrdenie platí pre každé prirodzené číslo n.

Dokážte, že (11 n+2 +12 2n+1) je bezo zvyšku deliteľné číslom 133.

Riešenie: 1) Nech n=1

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

Ale (23´133) je deliteľné 133 bezo zvyšku, takže pre n=1 je tvrdenie pravdivé; A(1) je pravda.

2) Predpokladajme, že (11 k+2 +12 2k+1) je deliteľné číslom 133 bezo zvyšku.

3) Dokážme to v tomto prípade

(11 k+3 +12 2k+3) je deliteľné 133 bezo zvyšku. Skutočne, 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 .

Výsledný súčet je bezo zvyšku deliteľný číslom 133, pretože jeho prvý člen je bezo zvyšku deliteľný číslom 133 a druhý člen je deliteľný číslom 133. Takže А(k)ÞА(k+1). Pomocou metódy matematickej indukcie je tvrdenie dokázané.

Dokážte, že pre ľubovoľné n je n -1 deliteľné číslom 6 bezo zvyšku.

Riešenie: 1) Nech n=1, potom X 1 =7 1 -1=6 delíme 6 bezo zvyšku. Takže pre n=1 je tvrdenie pravdivé.

2) Predpokladajme, že pre n=k

7 k -1 je deliteľné 6 bezo zvyšku.

3) Dokážme, že tvrdenie platí pre n=k+1.

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

Prvý člen je deliteľný 6, pretože 7 k -1 je deliteľných 6 za predpokladu, a druhý člen je 6. Takže 7 n -1 je násobkom 6 pre ľubovoľné prirodzené n. Pomocou metódy matematickej indukcie je tvrdenie dokázané.

Dokážte, že 3 3n-1 +2 4n-3 pre ľubovoľné prirodzené n je deliteľné 11.
Riešenie: 1) Nech n=1

X 1 \u003d 3 3-1 +2 4-3 \u003d 3 2 +2 1 \u003d 11 sa vydelí 11 bez zvyšku. Pre n=1 je teda tvrdenie pravdivé.

2) Predpokladajme, že pre n=k

X k \u003d 3 3k-1 +2 4k-3 je bezo zvyšku deliteľné 11.

3) Dokážme, že tvrdenie platí pre 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 .

Prvý člen je deliteľný 11 bezo zvyšku, keďže 3 3k-1 +2 4k-3 je deliteľné 11 za predpokladu, druhý člen je deliteľný 11, pretože jedným z jeho faktorov je číslo 11. Súčet je teda deliteľné aj 11 bezo zvyšku pre ľubovoľné prirodzené n. Pomocou metódy matematickej indukcie je tvrdenie dokázané.

Dokážte, že 11 2n -1 pre ľubovoľné kladné celé číslo n je bezo zvyšku deliteľné 6.

Riešenie: 1) Nech n=1, potom 11 2 -1=120 je deliteľné 6 bezo zvyšku. Takže pre n=1 je tvrdenie pravdivé.

2) Predpokladajme, že pre n=k

11 2k -1 je deliteľné 6 bezo zvyšku.

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

Oba členy sú bezo zvyšku deliteľné 6: prvý obsahuje násobok 6 číslo 120 a druhý je deliteľný 6 bezo zvyšku podľa predpokladu. Čiže súčet je bezo zvyšku deliteľný 6. Pomocou metódy matematickej indukcie je tvrdenie dokázané.

Dokážte, že 3 3n+3 -26n-27 pre ľubovoľné kladné celé číslo n je bezo zvyšku deliteľné číslom 26 2 (676).

Riešenie: Najprv dokážme, že 3 3n+3 -1 je bezo zvyšku deliteľné 26.

1. Pre n=0

3 3 -1 = 26 je deliteľné 26

2. Predpokladajme, že pre n=k

3 3k+3 -1 je deliteľné 26

3. Dokážme, že tvrdenie

platí pre n=k+1.

3 3k+6 -1=27´3 3k+3 -1=26´3 3k+3 +(3 3k+3 -1) – deliteľné 26

Teraz dokážme tvrdenie formulované v podmienke problému.

1) Je zrejmé, že pre n=1 je tvrdenie pravdivé

3 3+3 -26-27=676

2) Predpokladajme, že pre n=k

výraz 3 3k+3 -26k-27 je deliteľný 26 2 bezo zvyšku.

3) Dokážme, že tvrdenie platí pre n=k+1

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

Oba členy sú deliteľné 26 2 ; prvý je deliteľný 26 2, pretože sme dokázali, že výraz v zátvorke je deliteľný 26, a druhý je deliteľný induktívnou hypotézou. Pomocou metódy matematickej indukcie je tvrdenie dokázané.

Dokážte, že ak n>2 a x>0, potom nerovnosť

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

Riešenie: 1) Pre n=2 je nerovnosť pravdivá, pretože

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

Takže A(2) je pravda.

2) Dokážme, že A(k)ÞA(k+1), ak k> 2. Predpokladajme, že A(k) platí, t.j. že nerovnosť

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

Dokážme, že potom platí aj A(k+1), t.j. že nerovnosť

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

Vynásobením oboch strán nerovnosti (3) kladným číslom 1+x dostaneme

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

Zvážte pravú stranu posledného nerovného

stva; máme

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

Výsledkom je, že to dostaneme

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

Takže A(k)ÞA(k+1). Na základe princípu matematickej indukcie možno tvrdiť, že Bernoulliho nerovnosť platí pre všetky

Dokážte, že nerovnosť je pravdivá

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

Riešenie: 1) Pre m=1

(1+a+a 2) 1 > 1+a+(2/2)´a 2 obe časti sú rovnaké.

2) Predpokladajme, že pre m=k

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

3) Dokážme, že pre m=k+1 je nerovnosť pravdivá

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

Dokázali sme platnosť nerovnosti pre m=k+1, preto pomocou metódy matematickej indukcie platí nerovnosť pre akékoľvek prirodzené m.

Dokážte, že pre n>6 je nerovnosť

3 n > n'2 n+1.

Riešenie: Prepíšme nerovnosť do tvaru

1. Pre n=7 máme

3 7 /2 7 =2187/128>14=2´7

nerovnosť je pravdivá.

2. Predpokladajme, že pre n=k

3) Dokážme správnosť nerovnosti pre n=k+1.

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

Od k>7 je zrejmá posledná nerovnosť.

Na základe metódy matematickej indukcie platí nerovnosť pre akékoľvek prirodzené n.

Dokážte, že pre n>2 je nerovnosť

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

Riešenie: 1) Pre n=3 platí nerovnosť

1+(1/2 2)+(1/3 2)=245/180<246/180=1,7-(1/3).

1. Predpokladajme, že pre n=k

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

3) Preukážeme platnosť ne-

rovnosti pre n=k+1

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

Dokážme, že 1,7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1)Û

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

Ûk(k+2)<(k+1) 2Û k 2 +2k

To druhé je zrejmé, a preto

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

Pomocou metódy matematickej indukcie je nerovnosť dokázaná.

Záver

Najmä tým, že som študoval metódu matematickej indukcie, rozšíril som svoje znalosti v tejto oblasti matematiky a tiež som sa naučil, ako riešiť problémy, ktoré predtým presahovali moje sily.

V podstate to boli logické a zábavné úlohy, t.j. práve tie, ktoré zvyšujú záujem o samotnú matematiku ako vedu. Riešenie takýchto úloh sa stáva zábavnou činnosťou a dokáže prilákať do matematických labyrintov stále viac zvedavcov. To je podľa mňa základ každej vedy.

Pokračovaním v štúdiu metódy matematickej indukcie sa pokúsim naučiť ju aplikovať nielen v matematike, ale aj pri riešení úloh vo fyzike, chémii a živote samotnom.

MATEMATIKA:

PREDNÁŠKY, ÚLOHY, RIEŠENIA

Učebnica / V. G. Boltyansky, Yu. V. Sidorov, M. I. Shabunin. Potpourri LLC 1996.

ALGEBRA A PRINCÍPY ANALÝZY

Učebnica / I. T. Demidov, A. N. Kolmogorov, S. I. Shvartsburg, O. S. Ivashev-Musatov, B. E. Veits. "Osvietenie" 1975.

Prednáška 6. Metóda matematickej indukcie.

Nové poznatky vo vede a živote sa získavajú rôznymi spôsobmi, ale všetky (ak nejdete do detailov) sa delia na dva typy – prechod od všeobecného k konkrétnemu a od konkrétneho k všeobecnému. Prvým je odpočet, druhým indukcia. Deduktívne uvažovanie je to, čo sa zvyčajne nazýva v matematike logické uvažovanie a v matematickej vede je dedukcia jedinou legitímnou metódou vyšetrovania. Pravidlá logického uvažovania sformuloval pred dva a pol tisícročím starogrécky vedec Aristoteles. Vytvoril úplný zoznam najjednoduchších správnych úvah, sylogizmy– „tehličky“ logiky, zároveň poukazujúce na typické uvažovanie, veľmi podobné tým správnym, ale nesprávne (s takýmto „pseudologickým“ uvažovaním sa v médiách často stretávame).

Indukcia (indukcia - v latinčine vedenie) ilustruje známa legenda o tom, ako Isaac Newton sformuloval zákon univerzálnej gravitácie po tom, čo mu na hlavu spadlo jablko. Ďalší príklad z fyziky: pri takom jave, akým je elektromagnetická indukcia, elektrické pole vytvára, „indukuje“ magnetické pole. „Newtonovo jablko“ je typickým príkladom situácie, kedy jeden alebo viacero špeciálnych prípadov, t.j. pozorovania, „vedie“ k všeobecnému konštatovaniu, všeobecný záver sa robí na základe konkrétnych prípadov. Induktívna metóda je hlavnou metódou na získanie všeobecných vzorov v prírodných aj humanitných vedách. Má to však veľmi významnú nevýhodu: na základe konkrétnych príkladov možno vyvodiť nesprávny záver. Hypotézy vyplývajúce zo súkromných pozorovaní nie sú vždy správne. Uvažujme o príklade vďaka Eulerovi.

Pre niektoré prvé hodnoty vypočítame hodnotu trojčlenky n:

Všimnite si, že čísla získané ako výsledok výpočtov sú prvočísla. A to sa dá u každého priamo overiť n 1 až 39 hodnota polynómu
je prvočíslo. Avšak, kedy n=40 dostaneme číslo 1681=41 2 , ktoré nie je prvočíslo. Teda hypotéza, ktorá by tu mohla vzniknúť, teda hypotéza, že pre každého nčíslo
je jednoduchý, ukáže sa ako nepravdivý.

Leibniz v 17. storočí dokázal, že pre každé kladné celé číslo nčíslo
deliteľné 3
je deliteľné 5 a tak ďalej. Na základe toho navrhol, že za každú odd k a akékoľvek prírodné nčíslo
deleno k, ale čoskoro si to všimol
nie je deliteľné 9.

Uvažované príklady nám umožňujú vyvodiť dôležitý záver: výrok môže byť pravdivý v mnohých špeciálnych prípadoch a zároveň nespravodlivý vo všeobecnosti. Otázku platnosti výroku vo všeobecnom prípade možno riešiť uplatnením špeciálnej metódy uvažovania tzv matematickou indukciou(úplná indukcia, dokonalá indukcia).

6.1. Princíp matematickej indukcie.

♦ Metóda matematickej indukcie je založená na princíp matematickej indukcie , ktorý pozostáva z:

1) platnosť tohto vyhlásenia je overená pren=1 (indukčný základ) ,

2) predpokladá sa, že toto tvrdenie je pravdivén= k, kdekje ľubovoľné prirodzené číslo 1(indukčný predpoklad) , a s prihliadnutím na tento predpoklad je jeho platnosť ustanovená pren= k+1.

Dôkaz. Predpokladajme opak, teda predpokladajme, že toto tvrdenie neplatí pre každého prirodzeného n. Potom je tu taký prirodzený m, čo:

1) schválenie pre n=m nespravodlivé,

2) pre všetkých n, menšie m, tvrdenie je pravdivé (inými slovami, m je prvé prirodzené číslo, pre ktoré tvrdenie zlyhá).

To je zrejmé m>1, pretože pre n=1 tvrdenie je pravdivé (podmienka 1). teda
- prirodzené číslo. Ukazuje sa, že pre prirodzené číslo
výrok je pravdivý a pre ďalšie prirodzené číslo m je to nespravodlivé. To je v rozpore s podmienkou 2. ■

Všimnite si, že dôkaz použil axiómu, že každá zbierka prirodzených čísel obsahuje najmenšie číslo.

Dôkaz založený na princípe matematickej indukcie je tzv úplnou matematickou indukciou .

 Príklad6.1. Dokážte to pre akékoľvek prírodné nčíslo
je deliteľné 3.

rozhodnutie.

1) Kedy n=1, takže a 1 je deliteľné 3 a tvrdenie je pravdivé pre n=1.

2) Predpokladajme, že tvrdenie je pravdivé pre n=k,
, teda to číslo
je deliteľné 3 a nájdite to n=kČíslo +1 je deliteľné 3.

Naozaj,

Pretože každý člen je deliteľný 3, potom je aj ich súčet deliteľný 3. ■ 

 Príklad6.2. Dokážte, že súčet prvého n prirodzené nepárne čísla sa rovná druhej mocnine ich počtu, teda .

rozhodnutie. Používame metódu úplnej matematickej indukcie.

1) Overíme platnosť tohto vyhlásenia pre n=1: 1=1 2 je správne.

2) Predpokladajme, že súčet prvého k (
) nepárnych čísel sa rovná druhej mocnine počtu týchto čísel, teda . Na základe tejto rovnosti zistíme, že súčet prvého k+1 nepárne čísla sa rovná
, t.j.

Používame náš predpoklad a dostaneme

. ■ 

Na dokázanie niektorých nerovností sa používa metóda úplnej matematickej indukcie. Dokážme Bernoulliho nerovnosť.

 Príklad6.3. Dokáž, že kedy
a akékoľvek prírodné n nerovnosť
(Bernoulliho nerovnosť).

rozhodnutie. 1) Kedy n= 1 dostaneme
, ktoré je správne.

2) Predpokladáme, že pri n=k existuje nerovnosť
(*). Pomocou tohto predpokladu to dokážeme
. Všimnite si, že kedy
táto nerovnosť platí, a preto stačí zvážiť prípad
.

Vynásobte obe časti nerovnosti (*) číslom
a získaj:

To znamená (1+
.■ 

Dôkaz metódou neúplná matematická indukcia nejaké tvrdenie v závislosti od n, kde
vykonávané podobným spôsobom, ale na začiatku je nastolená spravodlivosť pre najmenšiu hodnotu n.

Niektoré úlohy výslovne neformulujú tvrdenie, ktoré možno dokázať matematickou indukciou. V takýchto prípadoch je potrebné stanoviť pravidelnosť a vysloviť hypotézu o platnosti tejto zákonitosti a následne testovať navrhnutú hypotézu metódou matematickej indukcie.

 Príklad6.4. Nájdite množstvo
.

rozhodnutie. Poďme nájsť sumy S 1 , S 2 , S 3. Máme
,
,
. Predpokladáme, že pre akékoľvek prírodné n vzorec je platný
. Na overenie tejto hypotézy používame metódu úplnej matematickej indukcie.

1) Kedy n=1 hypotéza je pravdivá, pretože
.

2) Predpokladajme, že hypotéza platí pre n=k,
, t.j
. Pomocou tohto vzorca zistíme, že hypotéza je pravdivá a pre n=k+1, tj

Naozaj,

Takže za predpokladu, že hypotéza platí pre n=k,
, je dokázané, že platí pre n=k+1 a na základe princípu matematickej indukcie sme dospeli k záveru, že vzorec je platný pre akékoľvek prírodné n. ■ 

 Príklad6.5. V matematike je dokázané, že súčet dvoch rovnomerne spojitých funkcií je rovnomerne spojitá funkcia. Na základe tohto tvrdenia musíme dokázať, že súčet ľubovoľného čísla
rovnomerne spojitých funkcií je rovnomerne spojitá funkcia. Ale keďže sme ešte nezaviedli pojem „rovnomerne spojitá funkcia“, položme problém abstraktnejšie: nech je známe, že súčet dvoch funkcií, ktoré majú nejakú vlastnosť S, sama má vlastnosť S. Dokážme, že súčet ľubovoľného počtu funkcií má vlastnosť S.

rozhodnutie. Základ indukcie je tu obsiahnutý v samotnej formulácii problému. Pri indukčnom predpoklade zvážte
funkcie f 1 , f 2 , …, f n , f n+1, ktorí majú nehnuteľnosť S. Potom . Na pravej strane má prvý výraz vlastnosť S podľa indukčnej hypotézy má druhý člen vlastnosť S podľa podmienok. Preto ich súčet má vlastnosť S– pri dvoch termínoch „funguje“ základ indukcie.

Toto potvrdzuje tvrdenie a použije ho ďalej. ■ 

 Príklad6.6. Nájdite všetko prirodzené n, pre ktoré je nerovnosť

.

rozhodnutie. Zvážte n=1, 2, 3, 4, 5, 6. Máme: 2 1 >1 2, 2 2 = 2 2, 2 3<3 2 , 2 4 =4 2 , 2 5 >52, 26 > 62. Môžeme teda urobiť hypotézu: nerovnosť
má miesto pre každého
. Aby sme dokázali pravdivosť tejto hypotézy, používame princíp neúplnej matematickej indukcie.

1) Ako je uvedené vyššie, táto hypotéza platí pre n=5.

2) Predpokladajme, že platí pre n=k,
, teda nerovnosť
. Pomocou tohto predpokladu dokážeme, že nerovnosť
.

T. do.
a pri
existuje nerovnosť

pri
,

potom to dostaneme
. Takže pravdivosť hypotézy n=k+1 vyplýva z predpokladu, že platí pre n=k,
.

Od pp. 1 a 2 na základe princípu neúplnej matematickej indukcie vyplýva, že nerovnosť
pravda pre každú prírodnú
. ■ 

 Príklad6.7. Dokážte to pre akékoľvek prirodzené číslo n platí diferenciačný vzorec
.

rozhodnutie. o n=1 tento vzorec má tvar
, alebo 1=1, to znamená, že je to pravda. Na základe indukčného predpokladu máme:

Q.E.D. ■ 

 Príklad6.8. Dokážte, že súbor pozostávajúci z n prvky, má podmnožiny.

rozhodnutie. Súprava s jedným prvkom a, má dve podmnožiny. To je pravda, pretože všetky jeho podmnožiny sú prázdna množina a samotná množina a 2 1 = 2.

Predpokladáme, že akýkoľvek súbor n prvky má podmnožiny. Ak sa množina A skladá z n+1 prvkov, potom v ňom fixujeme jeden prvok - označíme ho d a rozdeliť všetky podmnožiny do dvoch tried – neobsahujúce d a obsahujúce d. Všetky podmnožiny z prvej triedy sú podmnožinami množiny B získanej z A odstránením prvku d.

Sada B pozostáva z n prvkov, a preto podľa indukčnej hypotézy má podmnožiny, teda v prvej triede podmnožiny.

Ale v druhej triede je rovnaký počet podmnožín: každá z nich sa získa presne z jednej podmnožiny prvej triedy pridaním prvku d. Celkovo teda súbor A
podmnožiny.

Tým je tvrdenie dokázané. Všimnite si, že platí aj pre množinu pozostávajúcu z 0 prvkov – prázdnu množinu: má jedinú podmnožinu – samotnú a 2 0 = 1. ■ 

Ak to chcete urobiť, najskôr skontrolujte pravdivosť tvrdenia s číslom 1 - indukčná základňa, a potom sa preukáže, že ak je výpis s číslom n, potom nasledujúce tvrdenie s číslom n + 1 - indukčný krok, alebo indukčný prechod.

Dôkaz indukciou je možné vizualizovať formou tzv dominový princíp. Nech je ľubovoľný počet kociek domino umiestnený v rade tak, aby každé padajúce domino nevyhnutne prevrátilo nasledujúce domino (toto je indukčný prechod). Potom, ak zatlačíme prvú kosť (to je základ indukcie), všetky kosti v rade padnú.

Logickým základom pre tento spôsob dokazovania je tzv axióma indukcie, piata z Peanových axióm, ktoré definujú prirodzené čísla. Správnosť metódy indukcie je ekvivalentná skutočnosti, že v akejkoľvek podmnožine prirodzených čísel existuje minimálny prvok.

Existuje aj variácia, takzvaný princíp úplnej matematickej indukcie. Tu je jeho striktné znenie:

Princíp úplnej matematickej indukcie je tiež ekvivalentný axióme indukcie v Peanových axiómach.

Príklady

Úloha. Dokážte to, nech je to čokoľvek prirodzené n a skutočný q≠ 1, rovnosť

Dôkaz. Indukcia zapnutá n.

Základňa, n = 1:

Prechod: Predstierajme to

,

Q.E.D.

komentár: vernosť výpovede P n v tomto dôkaze je to isté ako platnosť rovnosti

pozri tiež

Variácie a zovšeobecnenia

Literatúra

• N. Ya Vilenkin Indukcia. Kombinatorika. Príručka pre učiteľov. M., Osveta, 1976.-48 s.
• L. I. Golovina, I. M. YaglomÚvod do geometrie, "Populárne prednášky z matematiky", číslo 21, Fizmatgiz 1961.-100 s.
• R. Courant, G. Robbins"Čo je matematika?" Kapitola I, §2.
• I. S. Sominskij Metóda matematickej indukcie. "Populárne prednášky z matematiky", číslo 3, Vydavateľstvo Nauka 1965.-58 s.

Nadácia Wikimedia. 2010.

Pozrite sa, čo je "Metóda matematickej indukcie" v iných slovníkoch:

Matematická indukcia v matematike patrí medzi dôkazové metódy. Používa sa na dokázanie pravdivosti niektorého tvrdenia pre všetky prirodzené čísla. Aby ste to urobili, najprv sa skontroluje pravdivosť tvrdenia s číslom 1, základ indukcie a potom ... ... Wikipedia

Metóda konštruovania teórie, pričom vychádza z niektorých jej ustanovení – axióm alebo postulátov – z ktorých sa usudzovaním odvodzujú všetky ostatné ustanovenia teórie (teorémy), nazývané dôkazy m i. Mimochodom, pravidlá ...... Filozofická encyklopédia

Indukcia (lat. indukčné vedenie) je proces inferencie založený na prechode z konkrétnej polohy do všeobecnej. Induktívne uvažovanie spája súkromné ​​premisy so záverom ani nie tak cez zákony logiky, ale skôr cez nejaké ... ... Wikipedia

GENETICKÁ METÓDA- spôsob stanovenia obsahu a podstaty skúmaného objektu nie konvenciou, idealizáciou alebo logickým záverom, ale štúdiom jeho pôvodu (na základe štúdia príčin, ktoré viedli k jeho vzniku, mechanizmu vzniku). Široký...... Filozofia vedy: Slovník základných pojmov

Metóda budovania vedeckej teórie, v ktorej je založená na niektorých počiatočných ustanoveniach (úsudkoch) axiómy (pozri axiómu) alebo postulátov, z ktorých musia byť odvodené všetky ostatné tvrdenia tejto vedy (vety (pozri vetu)). ... ... Veľká sovietska encyklopédia

axiomatická metóda- AXIOMATICKÁ METÓDA (z gréc. axióma) akceptovaná pozícia je metóda konštruovania vedeckej teórie, pri ktorej sa v dôkazoch používajú iba axiómy, postuláty a tvrdenia z nich predtým odvodené. Prvýkrát zobrazené... Encyklopédia epistemológie a filozofie vedy

Jedna z metód teórie chýb na odhadovanie neznámych veličín z výsledkov meraní obsahujúcich náhodné chyby. N. c. m. sa používa aj na približnú reprezentáciu danej funkcie inými (jednoduchšími) funkciami a často sa ukazuje ako ... Matematická encyklopédia

Matematická indukcia je jednou z metód matematického dôkazu, ktorá sa používa na dokázanie pravdivosti nejakého tvrdenia pre všetky prirodzené čísla. Ak to chcete urobiť, najprv skontrolujte ... Wikipedia

Tento výraz má iné významy, pozri Indukcia. Indukcia (lat. indukčné vedenie) je proces inferencie založený na prechode z konkrétnej polohy do všeobecnej. Induktívne uvažovanie spája súkromné ​​priestory ... ... Wikipedia

Indukcia je metóda získania všeobecného tvrdenia z konkrétnych pozorovaní. V prípade, že sa matematické tvrdenie týka konečného počtu objektov, možno ho dokázať kontrolou každého objektu. Napríklad tvrdenie: „Každé dvojciferné párne číslo je súčtom dvoch prvočísel,“ vyplýva zo série rovností, ktoré je celkom realistické stanoviť:

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

Metóda dôkazu, pri ktorej sa tvrdenie overuje pre konečný počet prípadov, vyčerpávajúc všetky možnosti, sa nazýva úplná indukcia. Táto metóda je relatívne zriedka použiteľná, pretože matematické výroky sa spravidla netýkajú konečných, ale nekonečných množín objektov. Napríklad tvrdenie o párnych dvojciferných číslach dokázaných vyššie úplnou indukciou je len špeciálnym prípadom vety: „Akékoľvek párne číslo je súčtom dvoch prvočísel.“ Táto veta zatiaľ nebola dokázaná ani vyvrátená.

Matematická indukcia je metóda dokazovania určitého tvrdenia pre ľubovoľné prirodzené n založená na princípe matematickej indukcie: „Ak je tvrdenie pravdivé pre n=1 a z jeho platnosti pre n=k vyplýva, že toto tvrdenie platí pre n= k+1, potom platí pre všetky n ". Metóda dôkazu matematickou indukciou je nasledovná:

1) základ indukcie: dokážte alebo priamo overte platnosť tvrdenia pre n=1 (niekedy n=0 alebo n=n 0);

2) indukčný krok (prechod): predpokladajú platnosť tvrdenia pre nejaké prirodzené n=k a na základe tohto predpokladu dokazujú platnosť tvrdenia pre n=k+1.

Problémy s riešeniami

1. Dokážte, že pre ľubovoľné prirodzené n je číslo 3 2n+1 +2 n+2 deliteľné 7.

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

základ indukcie. Ak n = 1, potom A(1) = 3 3 + 2 3 = 35 a je samozrejme deliteľné 7.

Indukčná hypotéza. Nech A(k) je deliteľné 7.

indukčný prechod. Dokážme, že A(k+1) je deliteľné číslom 7, teda platnosť zadania úlohy pre n=k.

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

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

Posledné číslo je deliteľné 7, keďže ide o rozdiel dvoch celých čísel deliteľných 7. Preto 3 2n+1 +2 n+2 je deliteľné 7 pre každé prirodzené n.

2. Dokážte, že pre každé kladné celé číslo n je číslo 2 3 n +1 deliteľné 3 n+1 a nie je deliteľné 3 n+2 .

Zavedieme si zápis: a i =2 3 i +1.

Pre n=1 máme a 1=2 3 +1=9. Takže 1 je deliteľné 3 2 a nie je deliteľné 3 3 .

Nech je pre n=k číslo a k deliteľné 3 k+1 a nedeliteľné 3 k+2 , teda a k =2 3 k +1=3 k+1 m, kde m nie je deliteľné 3. Potom

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

Je zrejmé, že k+1 je deliteľné 3 k+2 a nie je deliteľné 3 k+3.

Preto je tvrdenie dokázané pre akékoľvek prirodzené n.

3. Je známe, že x+1/x je celé číslo. Dokážte, že х n +1/х n je tiež celé číslo pre akékoľvek celé číslo n.

Predstavme si zápis: a i \u003d x i +1 / x i a hneď si všimnime, že a i \u003d a -i, takže budeme pokračovať v hovorení o prirodzených indexoch.

Poznámka: a 1 je celé číslo podľa podmienky; a 2 je celé číslo, pretože a 2 \u003d (a 1) 2 -2; a 0 = 2.

Predpokladajme, že a k je celé číslo pre akékoľvek kladné celé číslo k nepresahujúce n. Potom a 1 ·a n je celé číslo, ale a 1 ·a n =a n+1 +a n–1 a a n+1 =a 1 ·a n –a n–1. Avšak a n–1 je celé číslo podľa indukčnej hypotézy. Preto а n+1 je tiež celé číslo. Preto х n +1/х n je celé číslo pre akékoľvek celé číslo n, ktoré sa malo dokázať.

4. Dokážte, že pre každé kladné celé číslo n väčšie ako 1 je dvojitá nerovnosť

5. Dokážte, že pre prirodzené n > 1 a |x|

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

Pre n=2 je nerovnosť pravdivá. naozaj,

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

Ak nerovnosť platí pre n=k, potom pre n=k+1 máme

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

Nerovnosť je dokázaná pre ľubovoľné prirodzené číslo n > 1.

6. V rovine je n kruhov. Dokážte, že pri akomkoľvek usporiadaní týchto kruhov môže byť mapa nimi vytvorená správne vyfarbená dvoma farbami.

Využime metódu matematickej indukcie.

Pre n=1 je tvrdenie zrejmé.

Predpokladajme, že tvrdenie platí pre akúkoľvek mapu tvorenú n kružnicami a na rovine nech je n + 1 kružníc. Vymazaním jedného z týchto kruhov získame mapu, ktorá môže byť na základe predpokladu správne vyfarbená dvoma farbami (pozri prvý obrázok nižšie).

Vyradený kruh potom obnovíme a na jeho jednej strane, napríklad vo vnútri, zmeníme farbu každej plochy na opačnú (viď druhý obrázok). Je ľahké vidieť, že v tomto prípade dostaneme mapu správne vyfarbenú dvoma farbami, ale až teraz s n + 1 kruhmi, čo sa malo dokázať.

7. Konvexný polygón budeme nazývať „krásny“, ak sú splnené nasledujúce podmienky:

1) každý z jeho vrcholov je natretý jednou z troch farieb;

2) akékoľvek dva susedné vrcholy sú namaľované rôznymi farbami;

3) aspoň jeden vrchol mnohouholníka je zafarbený v každej z troch farieb.

Dokážte, že každý krásny n-uholník sa dá rozrezať nepretínajúcimi sa uhlopriečkami na „krásne“ trojuholníky.

Využime metódu matematickej indukcie.

základ indukcie. Pre najmenšie možné n=3 je vyjadrenie problému zrejmé: vrcholy „krásneho“ trojuholníka sú natreté tromi rôznymi farbami a nie sú potrebné žiadne rezy.

Indukčná hypotéza. Predpokladajme, že výrok o úlohe platí pre akýkoľvek „krásny“ n-uholník.

indukčný krok. Uvažujme ľubovoľný "krásny" (n + 1)-uholník a pomocou induktívneho predpokladu dokážte, že ho možno rozrezať o niekoľko uhlopriečok na "krásne" trojuholníky. Označme А 1 , А 2 , А 3 , … А n , А n+1 – po sebe idúce vrcholy (n+1)-uholníka. Ak je len jeden vrchol (n + 1)-uholníka zafarbený niektorou z troch farieb, potom spojením tohto vrcholu s uhlopriečkami so všetkými vrcholmi, ktoré s ním nesusedia, získame potrebné rozdelenie (n + 1)- rozdeľte sa na „krásne“ trojuholníky.

Ak sú aspoň dva vrcholy (n + 1)-uholníka vymaľované v každej z troch farieb, tak farbu vrcholu A 1 označíme číslom 1 a farbu vrcholu A 2 číslom 2 . Nech k je najmenšie číslo také, že vrchol A k je zafarbený treťou farbou. Je jasné, že k > 2. Odrežme trojuholník А k–2 А k–1 А k z (n+1)-uholníka s uhlopriečkou А k–2 А k . V súlade s výberom čísla k sú všetky vrcholy tohto trojuholníka namaľované tromi rôznymi farbami, to znamená, že tento trojuholník je „krásny“. Konvexný n-uholník A 1 A 2 ... A k–2 A k A k+1 ... A n+1 , ktorý zostane, bude tiež vďaka indukčnému predpokladu „krásny“, čo znamená, že je rozdelená na „krásne“ trojuholníky, ktoré a potrebovali dokázať.

8. Dokážte, že v konvexnom n-uholníku nie je možné vybrať viac ako n uhlopriečok tak, aby ľubovoľné dve z nich mali spoločný bod.

Urobme dôkaz metódou matematickej indukcie.

Dokážme všeobecnejšie tvrdenie: v konvexnom n-uholníku nie je možné vybrať viac ako n strán a uhlopriečok tak, aby akékoľvek dve z nich mali spoločný bod. Pre n = 3 je tvrdenie zrejmé. Predpokladajme, že toto tvrdenie platí pre ľubovoľný n-uholník a pomocou toho dokážme jeho platnosť pre ľubovoľný (n + 1)-uholník.

Predpokladajme, že pre (n + 1)-uholník toto tvrdenie neplatí. Ak z každého vrcholu (n+1)-uholníka nevychádzajú viac ako dve zvolené strany alebo diagonály, potom je ich vybratých najviac n+1. Z nejakého vrcholu A teda vychádzajú aspoň tri zvolené strany alebo uhlopriečky AB, AC, AD. Nech AC leží medzi AB a AD. Keďže akákoľvek strana alebo uhlopriečka, ktorá vychádza z C iná ako CA, nemôže pretínať AB a AD súčasne, z C vychádza iba jedna zvolená uhlopriečka CA.

Vynechaním bodu C spolu s uhlopriečkou CA dostaneme konvexný n-uholník, v ktorom je vybratých viac ako n strán a uhlopriečok, z ktorých ktorékoľvek dve majú spoločný bod. Dostávame sa teda k rozporu s predpokladom, že tvrdenie platí pre ľubovoľný konvexný n-uholník.

Takže pre (n + 1)-uholník je výrok pravdivý. V súlade s princípom matematickej indukcie platí tvrdenie pre akýkoľvek konvexný n-uholník.

9. V rovine je nakreslených n čiar, z ktorých žiadne dve nie sú rovnobežné a žiadne tri neprechádzajú tým istým bodom. Na koľko častí tieto čiary rozdeľujú rovinu.

Pomocou elementárnych výkresov sa dá ľahko uistiť, že jedna priamka rozdeľuje rovinu na 2 časti, dve priamky na 4 časti, tri priamky na 7 častí a štyri priame čiary na 11 častí.

Označme N(n) počet častí, na ktoré n čiar rozdeľuje rovinu. Je to vidieť

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

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

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

Je prirodzené to predpokladať

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

alebo, ako je ľahké stanoviť, pomocou vzorca pre súčet prvých n členov aritmetickej progresie,

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

Dokážme platnosť tohto vzorca metódou matematickej indukcie.

Pre n=1 je vzorec už overený.

Po vykonaní indukčného predpokladu uvažujme k + 1 riadkov, ktoré spĺňajú podmienku úlohy. Ľubovoľne z nich vyberieme k rovných čiar. Podľa indukčnej hypotézy rozdeľujú rovinu na 1+ k(k+1)/2 časti. Zostávajúca (k + 1)-tá čiara bude rozdelená vybranými k čiarami na k + 1 častí, a preto bude prechádzať cez (k + 1)-tu časť, na ktorú už bola rovina rozdelená, a každá z tieto časti sa rozdelia na 2 časti, čiže pribudne k+1 ďalších častí. takze

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

Q.E.D.

10. Vo výraze x 1: x 2: ...: x n sa umiestnia zátvorky na označenie poradia akcií a výsledok sa zapíše ako zlomok:

(v tomto prípade je každé z písmen x 1, x 2, ..., x n buď v čitateli zlomku alebo v menovateli). Koľko rôznych výrazov možno týmto spôsobom získať so všetkými možnými spôsobmi usporiadania zátvoriek?

V prvom rade je jasné, že vo výslednom zlomku bude v čitateli x 1. Je takmer rovnako zrejmé, že x 2 bude v menovateli akéhokoľvek usporiadania zátvoriek (znak delenia pred x 2 sa vzťahuje buď na samotné x 2, alebo na akýkoľvek výraz obsahujúci x 2 v čitateli).

Dá sa predpokladať, že všetky ostatné písmená x 3 , x 4 , ... , x n sa môžu v čitateli alebo menovateli nachádzať úplne ľubovoľne. Z toho vyplýva, že celkovo môžete získať 2 n-2 zlomkov: každé z n-2 písmen x 3, x 4, ..., x n môže byť nezávisle od ostatných v čitateli alebo menovateli.

Dokážme toto tvrdenie indukciou.

S n=3 môžete získať 2 zlomky:

takže tvrdenie je pravdivé.

Predpokladáme, že platí pre n=k a dokážeme to pre n=k+1.

Nech výraz x 1: x 2: ...: x k po určitom usporiadaní zátvoriek zapíšeme ako zlomok Q. Ak sa do tohto výrazu namiesto x k dosadí x k: x k+1, potom x k ​​bude v rovnaké miesto ako v zlomkoch Q a x k + 1 nebude tam, kde stálo x k (ak bolo x k v menovateli, potom x k ​​+ 1 bude v čitateli a naopak).

Teraz dokážme, že môžeme pridať x k+1 na rovnaké miesto ako x k . V zlomku Q bude po umiestnení zátvoriek nutne výraz v tvare q:x k, kde q je písmeno x k–1 alebo nejaký výraz v zátvorkách. Nahradením q: x k výrazom (q: x k): x k + 1 = q: (x k x k + 1) dostaneme zrejme rovnaký zlomok Q, kde namiesto x k je x k x k+1 .

Počet možných zlomkov v prípade n=k+1 je teda 2-krát väčší ako v prípade n=k a rovná sa 2 k–2 ·2=2 (k+1)–2 . Tým je tvrdenie dokázané.

Odpoveď: 2 n-2 zlomky.

Problémy bez riešení

1. Dokážte, že pre akékoľvek prirodzené n:

a) číslo 5 n -3 n + 2n je deliteľné 4;

b) číslo n 3 + 11 n je deliteľné 6;

c) číslo 7 n + 3n–1 je deliteľné 9;

d) číslo 6 2n +19 n –2 n+1 je deliteľné 17;

e) číslo 7 n+1 +8 2n–1 je deliteľné 19;

f) číslo 2 2n–1 –9n 2 +21n–14 je deliteľné 27.

2. Dokážte, že (n+1)·(n+2)· …·(n+n) = 2 n ·1·3·5·…·(2n–1).

3. Dokážte nerovnosť |sin nx| n|sinx| pre akékoľvek prirodzené n.

4. Nájdite prirodzené čísla a, b, c, ktoré nie sú deliteľné 10 a také, že pre ľubovoľné prirodzené n majú čísla a n + b n a c n rovnaké posledné dve číslice.

5. Dokážte, že ak n bodov neleží na tej istej priamke, tak medzi priamkami, ktoré ich spájajú, je aspoň n rôznych.

Pomocou metódy matematickej indukcie dokážte, že pre akékoľvek prírodné n nasledujúce rovnosti sú pravdivé:
a) ;
b) .

rozhodnutie.

a) Kedy n= 1 platí rovnosť. Za predpokladu platnosti rovnosti pre n, ukážme, že platí aj pre n+ 1. Naozaj,

Q.E.D.

b) Kedy n= 1 platnosť rovnosti je zrejmá. Z predpokladu jeho spravodlivosti pri n by mal

Vzhľadom na rovnosť 1 + 2 + ... + n = n(n+ 1)/2, dostávame

1 3 + 2 3 + ... + n 3 + (n + 1) 3 = (1 + 2 + ... + n + (n + 1)) 2 ,

t.j. výrok platí aj pre n + 1.

Príklad 1 Dokážte nasledujúce rovnosti

kde n O N.

rozhodnutie. a) Kedy n= 1 rovnosť bude mať tvar 1 = 1, preto P(1) pravda. Predpokladajme, že táto rovnosť je pravdivá, teda máme

. Musíme to overiť (dokázať).P(n+ 1), t.j. pravda. Pretože (s použitím indukčného predpokladu) dostaneme, tj. P(n+ 1) je pravdivé tvrdenie.

Teda podľa metódy matematickej indukcie platí pôvodná rovnosť pre akékoľvek prirodzené n.

Poznámka 2. Tento príklad by sa dal vyriešiť aj inak. Skutočne, súčet 1 + 2 + 3 + ... + n je súčet prvého nčlenov aritmetického postupu s prvým členom a 1 = 1 a rozdiel d= 1. Na základe známeho vzorca , dostaneme

b) Kedy n= 1 rovnosť bude mať tvar: 2 1 - 1 = 1 2 alebo 1 = 1, tj. P(1) pravda. Predpokladajme, že rovnosť

1 + 3 + 5 + ... + (2n - 1) = n 2 a dokázať toP(n + 1): 1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n+ 1) 2 alebo 1 + 3 + 5 + ... + (2 n - 1) + (2n + 1) = (n + 1) 2 .

Pomocou indukčnej hypotézy dostaneme

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

teda P(n+ 1) je pravdivé, a preto je dokázaná požadovaná rovnosť.

Poznámka 3. Tento príklad je možné vyriešiť (podobne ako predchádzajúci) bez použitia metódy matematickej indukcie.

c) Kedy n= 1 platí rovnosť: 1 = 1. Predpokladajme, že rovnosť je pravdivá

a ukázať to to je pravdaP(n) znamená pravduP(n+ 1). naozaj, a od 2 n 2 + 7 n + 6 = (2 n + 3)(n+ 2), dostávame a preto pôvodná rovnosť platí pre všetky prirodzenén.

d) Kedy n= 1 platí rovnosť: 1 = 1. Predpokladajme, že existuje

a dokázať to

naozaj,

e) Schválenie P(1) pravda: 2=2. Predpokladajme, že rovnosť

je pravda a dokážeme, že to znamená rovnosť naozaj,

Preto pôvodná rovnosť platí pre každého prirodzeného n.

f) P(1) pravda: 1/3 = 1/3. Nech je rovnosť P(n):

. Ukážme, že posledná rovnosť znamená nasledovné:

Naozaj, vzhľadom na to P(n) sa uskutoční, dostaneme

Rovnosť je teda dokázaná.

g) Kedy n= 1 máme a + b = b + a a preto je rovnosť pravdivá.

Nech platí Newtonov binomický vzorec n = k, t.j.

Potom Použitie rovnosti dostaneme

Príklad 2 Dokážte nerovnosti

a) Bernoulliho nerovnosť: (1 + a ) n ≥ 1 + n a , a > -1, n O N.

b) X 1 + X 2 + ... + X n ≥ n, ak X 1 X 2 · ... · X n= 1 a X i > 0, .

c) Cauchyho nerovnosť vzhľadom na aritmetický priemer a geometrický priemer kde X i > 0, , n ≥ 2.

d) hriech 2 n a + cos2 n a ≤ 1, n O N.

e)

f) 2 n > n 3 , n O N, n ≥ 10.

rozhodnutie. a) Kedy n= 1 získame skutočnú nerovnosť

1 + a ≥ 1 + a . Predpokladajme, že existuje nerovnosť

(1 + a) n ≥ 1 + n a

(1)

a ukázať, že potom máme(1 + a) n + 1 ≥ 1 + (n+ 1)a.

V skutočnosti, keďže a > -1 znamená a + 1 > 0, potom vynásobením oboch strán nerovnosti (1) (a + 1) dostaneme

(1 + a) n(1 + a) ≥ (1 + n a )(1 + a) alebo (1 + a) n + 1 ≥ 1 + (n+ 1)a + n a 2 Pretože n a 2 ≥ 0, teda(1 + a) n + 1 ≥ 1 + (n+ 1)a + n a 2 ≥ 1 + ( n+ 1)a.

Teda ak P(n) je teda pravda P(n+ 1) je pravda, preto podľa princípu matematickej indukcie platí Bernoulliho nerovnosť.

b) Kedy n= 1 dostaneme X 1 = 1, a preto X 1 ≥ 1 t.j. P(1) je pravdivé vyhlásenie. Predstierajme to P(n) je pravda, teda ak adica, X 1 ,X 2 ,...,X n - n kladné čísla, ktorých súčin sa rovná jednej, X 1 X 2 ·...· X n= 1 a X 1 + X 2 + ... + X n ≥ n.

Ukážme, že z tohto tvrdenia vyplýva, že platí nasledovné: ak X 1 ,X 2 ,...,X n ,X n+1 - (n+ 1) kladné čísla také, že X 1 X 2 ·...· X n · X n+1 = 1 teda X 1 + X 2 + ... + X n + X n + 1 ≥n + 1.

Zvážte nasledujúce dva prípady:

1) X 1 = X 2 = ... = X n = X n+1 = 1. Potom súčet týchto čísel je ( n+ 1) a požadovaná nerovnosť je splnená;

2) aspoň jedno číslo je iné ako jedna, nech je napríklad väčšie ako jedna. Potom, odkedy X 1 X 2 · ... · X n · X n+ 1 = 1, existuje aspoň jedno ďalšie číslo, ktoré je odlišné od jedného (presnejšie menej ako jedna). Nechať byť X n+ 1 > 1 a X n < 1. Рассмотрим n kladné čísla

X 1 ,X 2 ,...,X n-1 ,(X n · X n+1). Súčin týchto čísel sa rovná jednej a podľa hypotézy X 1 + X 2 + ... + X n-1 + X n X n + 1 ≥ n. Posledná nerovnosť sa prepíše takto: X 1 + X 2 + ... + X n-1 + X n X n+1 + X n + X n+1 ≥ n + X n + X n+1 alebo X 1 + X 2 + ... + X n-1 + X n + X n+1 ≥ n + X n + X n+1 - X n X n+1 .

Pokiaľ ide o

(1 - X n)(X n+1 - 1) > 0, potom n + X n + X n+1 - X n X n+1 = n + 1 + X n+1 (1 - X n) - 1 + X n =
= n + 1 + X n+1 (1 - X n) - (1 - X n) = n + 1 + (1 - X n)(X n+1 - 1) ≥ n+ 1. Preto X 1 + X 2 + ... + X n + X n+1 ≥ n+1, teda ak P(n) je teda pravdaP(n+ 1) je spravodlivé. Nerovnosť bola preukázaná.

Poznámka 4. Znamienko rovnosti sa vyskytuje vtedy a len vtedy X 1 = X 2 = ... = X n = 1.

c) Nechajte X 1 ,X 2 ,...,X n sú ľubovoľné kladné čísla. Zvážte nasledujúce n kladné čísla:

Pretože ich súčin sa rovná jednej: podľa predtým preukázanej nerovnosti b), vyplýva, že kde

Poznámka 5. Rovnosť platí vtedy a len vtedy X 1 = X 2 = ... = X n .

d) P(1) - spravodlivé tvrdenie: sin 2 a + cos 2 a = 1. Predpokladajme, že P(n) je pravdivé tvrdenie:

Hriech 2 n a + cos2 n a ≤ 1 a ukázať, že existujeP(n+ 1). naozaj, sin2( n+ 1) a + cos 2( n+ 1) \u003d hriech 2 n a hriech 2 a + cos 2 n a cos 2 a< sin 2n a + cos2 n a ≤ 1 (ak sin 2 a ≤ 1, potom cos 2 a < 1, и обратно: если cos 2 a ≤ 1, potom sin 2 a < 1). Таким образом, для любого n O N hriech 2 n a + cos2 n ≤ 1 a znamienko rovnosti sa dosiahne len vtedy, keďn = 1.

e) Kedy n= 1 tvrdenie je pravdivé: 1< 3 / 2 .

Predpokladajme, že a dokázať to

Pokiaľ ide o
Berúc do úvahy P(n), dostaneme

f) Berúc do úvahy poznámku 1, kontrolujeme P(10): 2 10 > 10 3, 1024 > 1000, teda pre n= 10 tvrdenie je pravdivé. Predpokladajme, že 2 n > n 3 (n> 10) a dokázať P(n+ 1), t.j. 2 n+1 > (n + 1) 3 .

Od hod n> 10 máme resp , nasleduje za tým

2n 3 > n 3 + 3n 2 + 3n+ 1 alebo n 3 > 3n 2 + 3n + 1. Berúc do úvahy nerovnosť (2 n > n 3), dostaneme 2 n+1 = 2 n 2 = 2 n + 2 n > n 3 + n 3 > n 3 + 3n 2 + 3n + 1 = (n + 1) 3 .

Teda podľa metódy matematickej indukcie pre akékoľvek prirodzené n O N, n≥ 10 máme 2 n > n 3 .

Príklad 3 Dokážte to pre kohokoľvek n O N

rozhodnutie. a) P(1) je pravdivé tvrdenie (0 je deliteľné 6). Nechať byť P(n) je spravodlivé, tzn n(2n 2 - 3n + 1) = n(n - 1)(2n- 1) je deliteľné 6. Ukážme, že potom máme P(n+ 1, teda ( n + 1)n(2n+ 1) je deliteľné 6. Skutočne, keďže

A ako n(n - 1)(2 n- 1) a 6 n 2 sú deliteľné 6, potom ich súčetn(n + 1)(2 n+ 1) je deliteľné 6.

teda P(n+ 1) je pravdivé vyhlásenie, a preto n(2n 2 - 3n+ 1) je deliteľné 6 pre ľubovoľné n O N.

b) Skontrolujte P(1): 6 0 + 3 2 + 3 0 = 11, teda P(1) je pravdivé vyhlásenie. Malo by sa dokázať, že ak 62 n-2 + 3 n+1 + 3 n-1 je deliteľné 11 ( P(n)), potom 6 2 n + 3 n+2 + 3 n je tiež deliteľné 11 ( P(n+ 1)). Skutočne, odvtedy

6 2n + 3 n+2 + 3 n = 6 2n-2+2 + 3 n+1+1 + 3 n-1+1 == 6 2 6 2 n-2 + 3 3 n+1 + 3 3 n-1 = 3 (62 n-2 + 3 n+1 + 3 n-1) + 33 6 2 n-2 a podobne ako 62 n-2 + 3 n+1 + 3 n-1 a 33 6 2 n-2 sú deliteľné 11, ich súčet je 6 2n + 3 n+2 + 3 n je deliteľné 11. Tvrdenie je dokázané. Indukcia v geometrii

Príklad 4 Vypočítajte stranu správnej 2 n-gon vpísaný do kruhu s polomerom R.