Leksioni 6. Metoda e induksionit matematik.
Njohuritë e reja në shkencë dhe në jetë merren në mënyra të ndryshme, por të gjitha ato (nëse nuk hyni në detaje) ndahen në dy lloje - kalimi nga e përgjithshme në të veçantë dhe nga e veçanta në të përgjithshme. E para është deduksion, e dyta është induksion. Arsyetimi deduktiv është ai që zakonisht quhet në matematikë arsyetimi logjik, dhe në matematikë, deduksioni është e vetmja metodë legjitime e kërkimit. Rregullat e arsyetimit logjik u formuluan dy mijëvjeçarë e gjysmë më parë nga shkencëtari i lashtë grek Aristoteli. Ai krijoi një listë të plotë të arsyetimit më të thjeshtë të saktë, silogjizmave- “tulla” logjike, ndërkohë që vë në dukje arsyetime tipike, shumë të ngjashme me të sakta, por të pasakta (me arsyetime të tilla “pseudologjike” hasim shpesh në media).
Induksion (induksion - latinisht duke synuar) ilustrohet qartë nga legjenda e famshme se si Isak Njutoni formuloi ligjin e gravitetit universal pasi një mollë i ra në kokë. Një shembull tjetër nga fizika: në një fenomen të tillë si induksioni elektromagnetik, një fushë elektrike krijon, "indukton" një fushë magnetike. "Molla e Njutonit" është një shembull tipik i një situate ku një ose më shumë raste të veçanta, d.m.th vrojtim, "Të çojë" në një deklaratë të përgjithshme, përfundimi i përgjithshëm bëhet në bazë të rasteve të veçanta. Metoda induktive është ajo kryesore për marrjen e modeleve të përgjithshme si në shkencat natyrore ashtu edhe në ato humanitare. Por ka një pengesë shumë domethënëse: në bazë të shembujve të veçantë, mund të nxirret përfundimi i gabuar. Hipotezat që dalin nga vëzhgimet private nuk janë gjithmonë të sakta. Merrni parasysh shembullin e Euler-it.
Do të llogarisim vlerën e trinomit për disa nga vlerat e para n:
|
|
Vini re se numrat e marrë si rezultat i llogaritjeve janë të thjeshta. Dhe ju mund ta shihni atë drejtpërdrejt për secilën n nga 1 në 39 vlera e polinomit 
është një numër i thjeshtë. Megjithatë, me n= 40 marrim numrin 1681 = 41 2, i cili nuk është i thjeshtë. Kështu, hipoteza që mund të lindte këtu, domethënë hipoteza se në secilin n numri 
është e thjeshtë rezulton e gabuar.
Leibniz-i në shekullin e 17-të e vërtetoi këtë me çdo pozitivitet të plotë n numri 
pjesëtueshëm me 3, numri 
pjesëtohet me 5 etj. Bazuar në këtë, ai sugjeroi që për çdo rast k dhe çdo natyrale n numri 
i ndarë nga k, por shpejt e vuri re vetë këtë 
nuk pjesëtohet me 9.
Shembujt e shqyrtuar na lejojnë të nxjerrim një përfundim të rëndësishëm: deklarata mund të jetë e vërtetë në një sërë rastesh të veçanta dhe në të njëjtën kohë e padrejtë në përgjithësi. Çështja e vlefshmërisë së deklaratës në rastin e përgjithshëm mund të zgjidhet duke aplikuar një metodë të veçantë arsyetimi, të quajtur nga induksioni matematik(induksion i plotë, induksion i përsosur).
6.1. Parimi i induksionit matematik.
♦ Metoda e induksionit matematik bazohet në parimi i induksionit matematik i përbërë nga sa vijon:
1) vërtetohet vlefshmëria e kësaj deklaraten=1 (bazë induksioni) ,
2) vlefshmëria e kësaj deklarate supozohet përn= k, kuk- një numër natyror arbitrar 1(hipoteza e induksionit) , dhe duke marrë parasysh këtë supozim, konstatohet se ai është i vlefshëm përn= k+1.
Dëshmi. Supozoni të kundërtën, domethënë supozoni se pohimi nuk është i vërtetë për çdo natyrë n... Pastaj ka një të tillë të natyrshme m, çfarë:
1) deklaratë për n=m jo e drejte,
2) për të gjithë n më pak m, deklarata është e vërtetë (me fjalë të tjera, mështë numri i parë natyror për të cilin pohimi nuk është i vërtetë).
Është e qartë se m> 1, sepse për n= 1 pohimi është i vërtetë (kushti 1). Prandaj, 
- numri natyror. Rezulton se për një numër natyror 
pohimi është i vërtetë, dhe për numrin tjetër natyror mështë e padrejtë. Kjo bie ndesh me kushtin 2. ■
Vini re se vërtetimi përdori aksiomën se çdo koleksion numrash natyrorë përmban numrin më të vogël.
Një vërtetim i bazuar në parimin e induksionit matematik quhet me induksion të plotë matematikor .
Shembull6.1.
Vërtetoni se për çdo të natyrshme n numri 
pjesëtohet me 3.
Zgjidhje.
1) Kur n= 1, pra a 1 pjesëtohet me 3 dhe pohimi është i vlefshëm për n=1.
2) Supozoni se deklarata është e vërtetë për n=k,
, pra ai numri 
është i pjesëtueshëm me 3, dhe ne do ta përcaktojmë atë për n=k Numri +1 pjesëtohet me 3.
Me të vërtetë,
Sepse çdo term pjesëtohet me 3, atëherë edhe shuma e tyre pjesëtohet me 3. ■
Shembull6.2. Vërtetoni se shuma e të parit n numrat tek natyrorë janë të barabartë me katrorin e numrit të tyre, d.m.th.
Zgjidhje. Do të përdorim metodën e induksionit të plotë matematikor.
1) Ne kontrollojmë vlefshmërinë e kësaj deklarate për n= 1: 1 = 1 2 - kjo është e drejtë.
2) Supozoni se shuma e të parës k
(
) e numrave tek është e barabartë me katrorin e numrit të këtyre numrave, d.m.th. Bazuar në këtë barazi, konstatojmë se shuma e të parës k+1 numra tek është 
, kjo eshte .
Ne përdorim supozimin tonë dhe marrim
. ■
Induksioni i plotë matematikor përdoret për të vërtetuar disa pabarazi. Le të provojmë pabarazinë e Bernulit.
Shembull6.3.
Vërtetoni këtë për 
dhe çdo natyrale n pabarazia është e vërtetë 
(Pabarazia e Bernulit).
Zgjidhje. 1) Kur n= 1 marrim 
e cila është e vërtetë.
2) Supozojmë se për n=k qëndron pabarazia 
(*). Duke përdorur këtë supozim, ne e vërtetojmë atë 
... Vini re se për 
kjo pabarazi qëndron, dhe për këtë arsye mjafton të shqyrtohet rasti 
.
Ne i shumëzojmë të dyja anët e pabarazisë (*) me numrin 
dhe merrni:
Kjo është (1+ 
.■
Prova me metodë induksioni matematik jo i plotë
disa deklarata në varësi të n, ku 
kryhet në mënyrë të ngjashme, por në fillim vendoset vlefshmëria për vlerën më të vogël n.
Në disa probleme, një pohim që mund të vërtetohet me metodën e induksionit matematik nuk është formuluar në mënyrë eksplicite. Në raste të tilla, është e nevojshme të vendosim vetë modelin dhe të formulojmë një hipotezë për vlefshmërinë e këtij modeli, dhe më pas, duke përdorur metodën e induksionit matematik, të testojmë hipotezën.
Shembull6.4.
Gjeni shumën 
.
Zgjidhje. Gjeni shumat S 1 ,
S 2 ,
S 3. Ne kemi 
,
,
... Ne supozojmë se për çdo natyrore n formula është e vlefshme 
... Për të testuar këtë hipotezë, ne do të përdorim metodën e induksionit të plotë matematikor.
1) Kur n= 1 hipotezë është e saktë, sepse 
.
2) Supozoni se hipoteza është e vërtetë për n=k,
, kjo eshte 
... Duke përdorur këtë formulë, ne do të vërtetojmë se hipoteza është gjithashtu e vërtetë për n=k+1, domethënë
Me të vërtetë,
Pra, duke u nisur nga supozimi se hipoteza është e vërtetë për n=k,
, vërtetohet se është e vërtetë edhe për n=k+1, dhe bazuar në parimin e induksionit matematik, konkludojmë se formula është e vlefshme për çdo natyrë n.
■
Shembull6.5.
Në matematikë, vërtetohet se shuma e dy funksioneve uniformisht të vazhdueshme është një funksion uniformisht i vazhdueshëm. Bazuar në këtë pohim, është e nevojshme të vërtetohet se shuma e çdo numri 
Funksioni uniformisht i vazhdueshëm është një funksion uniformisht i vazhdueshëm. Por meqenëse ende nuk e kemi prezantuar konceptin e "funksionit uniformisht të vazhdueshëm", ne e shtrojmë problemin në mënyrë më abstrakte: le të dihet se shuma e dy funksioneve që kanë disa veti. S, ka vet pronen S... Le të vërtetojmë se shuma e çdo numri funksionesh ka vetinë S.
Zgjidhje. Baza e induksionit këtu përmbahet në vetë formulimin e problemit. Duke bërë hipotezën e induksionit, merrni parasysh 
funksione f 1 ,
f 2 ,
…, f n ,
f n+1 me pronën S... Pastaj . Në anën e djathtë, termi i parë ka pronën S sipas hipotezës së induksionit, termi i dytë ka vetinë S sipas kushtit. Prandaj, shuma e tyre ka pronë S- për dy mandate, baza e induksionit "funksionon".
Kështu, deklarata vërtetohet dhe ne do ta përdorim atë më tej. ■
Shembull6.6. Gjeni gjithçka natyrale n për të cilat pabarazia
.
Zgjidhje. Merrni parasysh n= 1, 2, 3, 4, 5, 6. Kemi: 2 1> 1 2, 2 2 = 2 2, 2 3<3 2 ,
2 4 =4 2 ,
2 5 >5 2, 2 6> 6 2. Kështu, mund të bëhet një hipotezë: pabarazi 
vlen për të gjithë 
... Për të vërtetuar vërtetësinë e kësaj hipoteze, do të përdorim parimin e induksionit jo të plotë matematikor.
1) Siç u vërtetua më lart, kjo hipotezë është e vërtetë për n=5.
2) Supozoni se është e vërtetë për n=k,
, pra pabarazia 
... Duke përdorur këtë supozim, vërtetojmë se pabarazia 
.
T. te. 
dhe në 
qëndron pabarazia 
në 
,
atëherë e marrim atë 
... Pra, e vërteta e hipotezës për n=k+1 rrjedh nga supozimi se është e vërtetë për n=k,
.
Nga fq. 1 dhe 2, bazuar në parimin e induksionit jo të plotë matematikor, rezulton se pabarazia 
e vërtetë për çdo natyrë 
.
■
Shembull6.7.
Vërtetoni këtë për çdo numër natyror n formula e diferencimit është e vlefshme 
.
Zgjidhje. Në n= 1 kjo formulë ka formën 
, ose 1 = 1, domethënë është e saktë. Duke bërë hipotezën e induksionit, do të kemi:
Q.E.D. ■
Shembull6.8.
Vërtetoni se grupi i përbërë nga n elementet, ka 
nënbashkësi.
Zgjidhje. Një grup i përbërë nga një element a, ka dy nëngrupe. Kjo është e vërtetë, pasi të gjitha nëngrupet e tij janë grupi bosh dhe vetë ky grup, dhe 2 1 = 2.
Supozoni se çdo grup nga n elementet ka 
nënbashkësi. Nëse grupi A përbëhet nga n Elementet +1, atëherë ne rregullojmë një element në të - ne e shënojmë atë d, dhe ndani të gjitha nëngrupet në dy klasa - që nuk përmbajnë d dhe që përmban d... Të gjitha nëngrupet nga klasa e parë janë nënbashkësi të grupit B të përftuara nga A duke e hedhur poshtë elementin d.
Seti B përbëhet nga n elemente, dhe për këtë arsye, nga hipoteza e induksionit, ai ka 
nënbashkësi, pra në klasën e parë 
nënbashkësi.
Por në klasën e dytë ka të njëjtin numër nëngrupesh: secila prej tyre merret saktësisht nga një nëngrup i klasës së parë duke shtuar një element. d... Prandaj, në total, grupi A 
nënbashkësi.
Kjo dëshmon deklaratën. Vini re se ai është gjithashtu i vlefshëm për një grup të përbërë nga 0 elementë - një grup bosh: ai ka një nëngrup të vetëm - vetë, dhe 2 0 = 1. ■
Induksioni matematik është një nga metodat më të zakonshme të provës matematikore. Mund të përdoret për të vërtetuar shumicën e formulave me numra natyrorë n, për shembull, formula për gjetjen e shumës së termave të parë të progresionit S n = 2 a 1 + n - 1 d 2 n, formula binomiale e Njutonit a + bn = C n 0 an C n 1 an - 1 b +. ... ... + C n n - 1 a b n - 1 + C n n b n.
Në paragrafin e parë, ne do të analizojmë konceptet bazë, më pas do të shohim bazat e vetë metodës dhe më pas do t'ju tregojmë se si ta përdorni atë për të vërtetuar barazinë dhe pabarazinë.
Yandex.RTB R-A-339285-1
Konceptet e induksionit dhe deduksionit
Për të filluar, merrni parasysh se çfarë janë induksioni dhe deduksioni në përgjithësi.
Përkufizimi 1
Induksioni- ky është kalimi nga privatja në të përgjithshmen, dhe zbritja përkundrazi, nga e përgjithshme në të veçantë.
Për shembull, ne kemi një deklaratë: 254 mund të ndahet në dy fare. Prej tij mund të nxjerrim shumë përfundime, ndër të cilat do të ketë edhe të vërteta edhe të rreme. Për shembull, pohimi se të gjithë numrat e plotë që kanë shifrën 4 në fund mund të pjesëtohen me dy pa mbetje është i vërtetë, por fakti që çdo numër prej tre shifrash është i pjesëtueshëm me 2 është i gabuar.
Në përgjithësi, mund të themi se me ndihmën e arsyetimit induktiv, mund të merrni shumë përfundime nga një arsyetim i njohur ose i dukshëm. Induksioni matematik na lejon të përcaktojmë se sa të vërteta janë këto përfundime.
Le të themi se kemi një sekuencë numrash si 1 1 2, 1 2 3, 1 3 4, 1 4 5,. ... ... , 1 n (n + 1), ku n tregon një numër natyror. Në këtë rast, kur shtojmë elementët e parë të sekuencës, marrim sa vijon:
S 1 = 1 1 2 = 1 2, S 2 = 1 1 2 + 1 2 3 = 2 3, S 3 = 1 1 2 + 1 2 3 + 1 3 4 = 3 4, S 4 = 1 1 2 + 1 2 3 + 1 3 4 + 1 4 5 = 4 5,. ... ...
Duke përdorur induksionin, mund të konkludojmë se S n = n n + 1. Në pjesën e tretë do ta vërtetojmë këtë formulë.
Cila është metoda e induksionit matematik
Kjo metodë bazohet në parimin me të njëjtin emër. Është formuluar si më poshtë:
Përkufizimi 2
Një deklaratë e caktuar do të jetë e vërtetë për një vlerë natyrore të n nëse 1) do të jetë e vërtetë për n = 1 dhe 2) meqenëse kjo shprehje është e vërtetë për një vlerë natyrore arbitrare n = k, rrjedh se do të jetë gjithashtu e vërtetë për n = k + 1 ...
Aplikimi i metodës së induksionit matematik kryhet në 3 faza:
- Së pari, ne kontrollojmë korrektësinë e deklaratës origjinale në rastin e një vlere natyrore arbitrare prej n (zakonisht kontrolli bëhet për një).
- Pas kësaj, ne kontrollojmë besnikërinë me n = k.
- Dhe më tej vërtetojmë vlefshmërinë e pohimit në rastin kur n = k + 1.
Si të përdorim metodën e induksionit matematik për të zgjidhur pabarazitë dhe ekuacionet
Le të marrim shembullin për të cilin folëm më parë.
Shembulli 1
Vërtetoni formulën S n = 1 1 2 + 1 2 3 +. ... ... + 1 n (n + 1) = n n + 1.
Zgjidhje
Siç e dimë tashmë, për të aplikuar metodën e induksionit matematik, duhet të kryeni tre hapa të njëpasnjëshëm.
- Së pari, ne kontrollojmë nëse kjo barazi është e vlefshme kur n është e barabartë me një. Ne marrim S 1 = 1 1 2 = 1 1 + 1 = 1 2. Gjithçka është e saktë këtu.
- Më tej, ne bëjmë supozimin se formula S k = k k + 1 është e vërtetë.
- Në hapin e tretë, duhet të vërtetojmë se S k + 1 = k + 1 k + 1 + 1 = k + 1 k + 2, bazuar në vlefshmërinë e barazisë së mëparshme.
Ne mund të paraqesim k + 1 si shumën e termave të parë të sekuencës origjinale dhe k + 1:
S k + 1 = S k + 1 k + 1 (k + 2)
Meqenëse në veprimin e dytë kemi marrë se S k = k k + 1, atëherë mund të shkruajmë sa vijon:
S k + 1 = S k + 1 k + 1 (k + 2).
Tani ne kryejmë transformimet e nevojshme. Ne duhet të kryejmë reduktimin e thyesës në një emërues të përbashkët, zvogëlimin e termave të ngjashëm, të zbatojmë formulën për shumëzimin e reduktuar dhe të zvogëlojmë atë që ndodhi:
S k + 1 = S k + 1 k + 1 (k + 2) = kk + 1 + 1 k + 1 (k + 2) = = k (k + 2) + 1 k + 1 (k + 2) = k 2 + 2 k + 1 k + 1 (k + 2) = (k + 1) 2 k + 1 (k + 2) = k + 1 k + 2
Kështu, ne e kemi vërtetuar barazinë në pikën e tretë duke plotësuar të tre hapat e metodës së induksionit matematik.
Përgjigje: supozimi për formulën S n = n n + 1 është i saktë.
Le të marrim një problem më kompleks me funksionet trigonometrike.
Shembulli 2
Jepni një vërtetim të identitetit cos 2 α · cos 4 α ·. ... ... Cos 2 n α = sin 2 n + 1 α 2 n sin 2 α.
Zgjidhje
Siç e kujtojmë, hapi i parë duhet të jetë të kontrollojmë nëse barazia është e saktë kur n është e barabartë me një. Për ta zbuluar, duhet të kujtojmë formulat bazë trigonometrike.
cos 2 1 = cos 2 α sin 2 1 + 1 α 2 1 sin 2 α = mëkat 4 α 2 sin 2 α = 2 sin 2 α cos 2 α 2 sin 2 α = cos 2 α
Prandaj, për n të barabartë me një, identiteti do të jetë i vërtetë.
Tani, supozoni se vlefshmëria e tij mbetet e vlefshme për n = k, d.m.th. do të jetë e vërtetë që cos 2 α · cos 4 α ·. ... ... Cos 2 k α = sin 2 k + 1 α 2 k sin 2 α.
Vërtetojmë barazinë cos 2 α · cos 4 α ·. ... ... · Cos 2 k + 1 α = sin 2 k + 2 α 2 k + 1 sin 2 α për rastin kur n = k + 1, duke marrë si bazë supozimin e mëparshëm.
Sipas formulës trigonometrike,
sin 2 k + 1 α cos 2 k + 1 α = = 1 2 (sin (2 k + 1 α + 2 k + 1 α) + sin (2 k + 1 α - 2 k + 1 α)) = = 1 2 mëkat (2 2 k + 1 α) + mëkat 0 = 1 2 mëkat 2 k + 2 α
Prandaj,
cos 2 α cos 4 α. ... ... Cos 2 k + 1 α = = cos 2 α cos 4 α ... ... Cos 2 k α cos 2 k + 1 α = = mëkat 2 k + 1 α 2 k sin 2 α cos 2 k + 1 α = 1 2 sin 2 k + 1 α 2 k sin 2 α = mëkat 2 k + 2 α 2 k + 1 mëkat 2 α
Një shembull i zgjidhjes së problemit të vërtetimit të një pabarazie duke përdorur këtë metodë është dhënë në artikullin mbi metodën e katrorëve më të vegjël. Lexoni paragrafin në të cilin janë nxjerrë formulat për gjetjen e koeficientëve të përafrimit.
Nëse vëreni një gabim në tekst, ju lutemi zgjidhni atë dhe shtypni Ctrl + Enter
Prezantimi
Pjesa kryesore
1. Induksion i plotë dhe jo i plotë
2. Parimi i induksionit matematik
3. Metoda e induksionit matematik
4. Zgjidhja e shembujve
5. Barazia
6. Ndarja e numrave
7. Pabarazitë
konkluzioni
Lista e literaturës së përdorur
Prezantimi
Të gjitha kërkimet matematikore bazohen në metoda deduktive dhe induktive. Metoda deduktive e arsyetimit është arsyetimi nga e përgjithshmja tek e veçanta, d.m.th. arsyetimi, pikënisja e të cilit është rezultati i përgjithshëm, dhe pika përfundimtare është rezultati i veçantë. Induksioni përdoret kur kalohet nga rezultatet e veçanta në ato të përgjithshme, d.m.th. është e kundërta e metodës deduktive.
Metoda e induksionit matematik mund të krahasohet me progresin. Fillojmë nga më e ulta, si rezultat i të menduarit logjik arrijmë tek më e larta. Njeriu gjithmonë është përpjekur për përparim, për aftësinë për të zhvilluar mendimin e tij në mënyrë logjike, që do të thotë se vetë natyra e ka synuar të mendojë në mënyrë induktive.
Megjithëse fusha e aplikimit të metodës së induksionit matematik është rritur, pak kohë i kushtohet asaj në kurrikulën shkollore. Epo, thuaju atyre se dy ose tre mësime do t'i sjellin gjëra të dobishme një personi, për të cilat ai do të dëgjojë pesë fjalë teorike, do të zgjidhë pesë probleme primitive dhe, si rezultat, do të marrë një A për të mos ditur asgjë.
Dhe është kaq e rëndësishme të jesh në gjendje të mendosh në mënyrë induktive.
Pjesa kryesore
Sipas kuptimit të saj origjinal, fjala "induksion" zbatohet për arsyetimin me ndihmën e të cilit nxirren përfundime të përgjithshme, bazuar në një numër pohimesh të veçanta. Metoda më e thjeshtë e arsyetimit të këtij lloji është induksioni i plotë. Ja një shembull i këtij arsyetimi.
Le të kërkohet të përcaktohet se çdo numër çift natyror n brenda 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.
Këto nëntë barazime tregojnë se secili nga numrat me interes për ne përfaqësohet me të vërtetë si një shumë e dy termave të thjeshtë.
Kështu, induksioni i plotë do të thotë që pohimi i përgjithshëm vërtetohet veçmas në secilën prej një numri të kufizuar rastesh të mundshme.
Ndonjëherë është e mundur të parashikohet rezultati i përgjithshëm pasi të merren parasysh jo të gjitha, por një numër i madh i rasteve të veçanta (i ashtuquajturi induksion jo i plotë).
Rezultati i përftuar nga induksioni jo i plotë, megjithatë, mbetet vetëm një hipotezë derisa të vërtetohet me arsyetim të saktë matematikor që mbulon të gjitha rastet e veçanta. Me fjalë të tjera, induksioni jo i plotë në matematikë nuk konsiderohet një metodë legjitime e provës rigoroze, por është një metodë e fuqishme për zbulimin e të vërtetave të reja.
Supozoni, për shembull, që dëshironi të gjeni shumën e n numrave të parë tek. Le të shqyrtojmë raste të veçanta:
1+3+5+7+9=25=5 2
Pas shqyrtimit të këtyre pak rasteve të veçanta, sugjeron vetë përfundimi i përgjithshëm vijues:
1 + 3 + 5 +… + (2n-1) = n 2
ato. shuma e n numrave të parë tek është n 2
Sigurisht, ky vëzhgim nuk mund të shërbejë ende si një provë e vlefshmërisë së formulës së mësipërme.
Induksioni i plotë ka përdorim të kufizuar në matematikë. Shumë pohime interesante matematikore mbulojnë një numër të pafund rastesh të veçanta, por ne nuk jemi në gjendje të kontrollojmë për një numër të pafund rastesh. Induksioni jo i plotë shpesh çon në rezultate të gabuara.
Në shumë raste, mënyra për të dalë nga kjo lloj vështirësie është përdorimi i një metode të veçantë arsyetimi të quajtur metoda e induksionit matematik. Është si më poshtë.
Supozoni se ju duhet të provoni vlefshmërinë e disa pohimeve për çdo numër natyror n (për shembull, ju duhet të provoni se shuma e n numrave të parë tek është e barabartë me n 2). Verifikimi i drejtpërdrejtë i këtij pohimi për secilën vlerë të n-së është i pamundur, pasi bashkësia e numrave natyrorë është e pafundme. Për të vërtetuar këtë deklaratë, së pari kontrolloni vlefshmërinë e tij për n = 1. Më pas, vërtetohet se për çdo vlerë natyrore të k, vlefshmëria e pohimit në shqyrtim për n = k nënkupton vlefshmërinë e tij edhe për n = k + 1.
Atëherë deklarata konsiderohet e provuar për të gjitha n. Në të vërtetë, deklarata është e vërtetë për n = 1. Por atëherë është gjithashtu e vërtetë për numrin tjetër n = 1 + 1 = 2. Vlefshmëria e pohimit për n = 2 nënkupton vlefshmërinë e tij për n = 2 +
1 = 3. Kjo nënkupton vlefshmërinë e deklaratës për n = 4, etj. Është e qartë se në fund do të arrijmë çdo numër natyror n. Prandaj, pohimi është i vërtetë për çdo n.
Duke përmbledhur atë që u tha, ne formulojmë parimin e përgjithshëm vijues.
Parimi i induksionit matematik.
Nëse fjalia A ( n ) në varësi të numrit natyror n , e vërtetë për n = 1 dhe nga fakti që është e vërtetë për n = k (ku k -çdo numër natyror), rrjedh se është e vërtetë edhe për numrin pasardhës n = k + 1 , pastaj supozimi A ( n ) është e vërtetë për çdo numër natyror n .
Në një numër rastesh, është e nevojshme të vërtetohet vlefshmëria e një deklarate të caktuar jo për të gjithë numrat natyrorë, por vetëm për n> p, ku p është një numër natyror fiks. Në këtë rast, parimi i induksionit matematik formulohet si më poshtë. Nëse fjalia A ( n ) është e vërtetë për n = p dhe nëse A ( k ) Þ A( k + 1) për këdo k> p, pastaj fjalia A ( n) e vërtetë për këdo n> fq.Vërtetimi me metodën e induksionit matematik kryhet si më poshtë. Së pari, pohimi që vërtetohet verifikohet për n = 1, domethënë, vërtetohet e vërteta e pohimit A (1). Kjo pjesë e provës quhet baza e induksionit. Pastaj vjen pjesa e provës e quajtur hapi i induksionit. Në këtë pjesë, vërtetojmë vlefshmërinë e pohimit për n = k + 1 nën supozimin e vlefshmërisë së pohimit për n = k (hipoteza e induksionit), d.m.th. vërtetoni se A (k) ÞA (k + 1).
SHEMBULL 1
Vërtetoni se 1 + 3 + 5 +… + (2n-1) = n 2.
Zgjidhje: 1) Kemi n = 1 = 1 2. Prandaj,
pohimi është i vërtetë për n = 1, d.m.th. A (1) është e vërtetë.
2) Le të vërtetojmë se А (k) ÞA (k + 1).
Le të jetë k çdo numër natyror dhe le të jetë i vërtetë pohimi për n = k, d.m.th.
1 + 3 + 5 +… + (2k-1) = k 2.
Le të vërtetojmë se atëherë pohimi është i vërtetë edhe për numrin tjetër natyror n = k + 1, d.m.th. çfarë
1 + 3 + 5 +… + (2k + 1) = (k + 1) 2.
Me të vërtetë,
1 + 3 + 5 +… + (2k-1) + (2k + 1) = k 2 + 2k + 1 = (k + 1) 2.
Pra, A (k) ÞA (k + 1). Bazuar në parimin e induksionit matematik, arrijmë në përfundimin se supozimi A (n) është i vërtetë për çdo nÎN.
SHEMBULL 2
Vërtetoni këtë
1 + x + x 2 + x 3 + ... + x n = (x n + 1 -1) / (x-1), ku x¹1
Zgjidhje: 1) Për n = 1 marrim
1 + x = (x 2 -1) / (x-1) = (x-1) (x + 1) / (x-1) = x + 1
prandaj, për n = 1, formula është e saktë; A (1) është e vërtetë.
2) Le të jetë k çdo numër natyror dhe formula të jetë e vërtetë për n = k, d.m.th.
1 + x + x 2 + x 3 + ... + x k = (x k + 1 -1) / (x-1).
Le të vërtetojmë se atëherë barazia
1 + x + x 2 + x 3 + ... + x k + x k + 1 = (x k + 2 -1) / (x-1).
Me të vërtetë
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).
Pra, A (k) ÞA (k + 1). Bazuar në parimin e induksionit matematik, arrijmë në përfundimin se formula është e vërtetë për çdo numër natyror n.
SHEMBULL 3
Vërtetoni se numri i diagonaleve të një n-gon konveks është n (n-3) / 2.
Zgjidhje: 1) Për n = 3, pohimi është
Dhe 3 është dinak, sepse në një trekëndësh А 3 = 3 (3-3) / 2 = 0 diagonale;
A 2 A (3) është e vërtetë.
2) Supozoni se në ndonjë
konveks k-gon ka-
А 1 sy А k = k (k-3) / 2 diagonale.
А k Le të vërtetojmë se atëherë në konveks
(k + 1) -numri gon
diagonalet А k + 1 = (k + 1) (k-2) / 2.
Le të A 1 A 2 A 3… A k A k + 1 -konveks (k + 1) -gon. Vizatoni një diagonale A 1 A k në të. Për të numëruar numrin total të diagonaleve të këtij (k + 1) -gon, duhet të numëroni numrin e diagonaleve në k-gon A 1 A 2… A k, shtoni k-2 në numrin që rezulton, d.m.th. duhet të merret parasysh numri i diagonaleve të (k + 1) -gon që dalin nga kulmi А k + 1, dhe përveç kësaj, diagonalja А 1 А k.
Kështu,
k + 1 = k + (k-2) + 1 = k (k-3) / 2 + k-1 = (k + 1) (k-2) / 2.
Pra, A (k) ÞA (k + 1). Për shkak të parimit të induksionit matematik, pohimi është i vërtetë për çdo n-gon konveks.
SHEMBULL 4
Vërtetoni se për çdo n pohimi i mëposhtëm është i vërtetë:
1 2 +2 2 +3 2 +… + n 2 = n (n + 1) (2n + 1) / 6.
Zgjidhje: 1) Le të jetë n = 1, atëherë
X 1 = 1 2 = 1 (1 + 1) (2 + 1) / 6 = 1.
Prandaj, për n = 1 pohimi është i vërtetë.
2) Supozoni se n = k
X k = k 2 = k (k + 1) (2k + 1) / 6.
3) Konsideroni këtë pohim për n = k + 1
X k + 1 = (k + 1) (k + 2) (2k + 3) / 6.
X k + 1 = 1 2 +2 2 +3 2 +… + k 2 + (k + 1) 2 = k (k + 1) (2k + 1) / 6 + + (k + 1) 2 = (k (k + 1) (2k + 1) +6 (k + 1) 2) / 6 = (k + 1) (k (2k + 1) +
6 (k + 1)) / 6 = (k + 1) (2k 2 + 7k + 6) / 6 = (k + 1) (2 (k + 3/2) (k +
2)) / 6 = (k + 1) (k + 2) (2k + 3) / 6.
Ne kemi vërtetuar vlefshmërinë e barazisë për n = k + 1, prandaj, në bazë të metodës së induksionit matematik, pohimi është i vërtetë për çdo n natyral.
SHEMBULL 5
Vërtetoni se për çdo n natyrore barazia e mëposhtme është e vërtetë:
1 3 +2 3 +3 3 +… + n 3 = n 2 (n + 1) 2/4.
Zgjidhje: 1) Le të jetë n = 1.
Pastaj X 1 = 1 3 = 1 2 (1 + 1) 2/4 = 1.
Ne shohim se për n = 1 pohimi është i vërtetë.
2) Supozoni se barazia është e vërtetë për n = k
METODA E INDUKSIONIT MATEMATIK
Fjala induksion në rusisht do të thotë udhëzim, dhe induktiv quhen përfundime të bazuara në vëzhgime, eksperimente, d.m.th. e përftuar nga përfundimi nga e veçanta te e përgjithshme.
Për shembull, çdo ditë shohim Diellin duke lindur nga lindja. Prandaj, mund të jeni i sigurt se nesër do të shfaqet në lindje, dhe jo në perëndim. Ne nxjerrim këtë përfundim pa përdorur ndonjë supozim për arsyen e lëvizjes së Diellit nëpër qiell (për më tepër, vetë kjo lëvizje rezulton të jetë e dukshme, pasi globi në të vërtetë po lëviz). E megjithatë, ky përfundim induktiv përshkruan saktë vëzhgimet që do të bëjmë nesër.
Roli i konkluzioneve induktive në shkencat eksperimentale është shumë i madh. Ata japin ato propozime, nga të cilat më pas nxirren përfundime të mëtejshme me anë të deduksionit. Dhe megjithëse mekanika teorike bazohet në tre ligjet e lëvizjes së Njutonit, vetë këto ligje ishin rezultat i një mendimi të thellë të të dhënave eksperimentale, në veçanti ligjet e Keplerit për lëvizjen planetare, të cilat ai i nxori gjatë përpunimit të vëzhgimeve afatgjata të Astronomi danez Tycho Brahe. Vëzhgimi dhe induksioni rezultojnë të jenë të dobishëm në të ardhmen për sqarimin e supozimeve të bëra. Pas eksperimenteve të Michelson për matjen e shpejtësisë së dritës në një mjedis lëvizës, doli se ishte e nevojshme të sqaroheshin ligjet e fizikës, të krijohej një teori e relativitetit.
Në matematikë, roli i induksionit është kryesisht për shkak të faktit se ai qëndron në themel të aksiomatikës së zgjedhur. Pasi praktika e gjatë tregoi se një shteg i drejtë është gjithmonë më i shkurtër se një shteg i lakuar ose i thyer, ishte e natyrshme të formulohej një aksiomë: për çdo tre pika A, B dhe C, pabarazia
Koncepti i ndjekjes në bazë të aritmetikës u shfaq gjithashtu kur vëzhgohej formimi i ushtarëve, anijeve dhe grupeve të tjera të renditura.
Megjithatë, nuk duhet menduar se kjo e shteron rolin e induksionit në matematikë. Natyrisht, ne nuk duhet të verifikojmë eksperimentalisht teoremat që dalin logjikisht nga aksiomat: nëse nuk janë bërë gabime logjike në derivim, atëherë ato janë të vërteta për aq sa aksiomat që kemi pranuar janë të vërteta. Por shumë pohime mund të nxirren nga ky sistem aksiomash. Dhe përzgjedhja e atyre pohimeve për t'u vërtetuar nxitet përsëri nga induksioni. Është ajo që na lejon të ndajmë teoremat e dobishme nga ato të padobishme, tregon se cilat teorema mund të rezultojnë të vërteta dhe madje ndihmon për të përshkruar rrugën e provës.
Thelbi i metodës së induksionit matematik
Në shumë degë të aritmetikës, algjebrës, gjeometrisë, analizës, është e nevojshme të vërtetohet vërtetësia e fjalive A (n), në varësi të një ndryshoreje natyrore. Vërtetimi i së vërtetës së fjalisë A (n) për të gjitha vlerat e ndryshores shpesh mund të kryhet me metodën e induksionit matematik, i cili bazohet në parimin e mëposhtëm.
Fjalia А (n) konsiderohet e vërtetë për të gjitha vlerat natyrore të ndryshores nëse plotësohen dy kushtet e mëposhtme:
Pohimi A (n) është i vërtetë për n = 1.
Nga supozimi se A (n) është e vërtetë për n = k (ku k është çdo numër natyror), rrjedh se është gjithashtu e vërtetë për vlerën tjetër n = k + 1.
Ky parim quhet parimi i induksionit matematik. Zakonisht zgjidhet si një nga aksiomat që përcaktojnë serinë natyrore të numrave dhe, për rrjedhojë, pranohet pa prova.
Metoda e induksionit matematik kuptohet si metoda e mëposhtme e provës. Nëse kërkohet të vërtetohet vërtetësia e fjalisë A (n) për të gjitha n-të natyrore, atëherë, së pari, duhet të kontrollohet vërtetësia e pohimit A (1) dhe, së dyti, duke supozuar vërtetësinë e pohimit A (k) , përpiquni të vërtetoni se pohimi A (k +1) është i vërtetë. Nëse kjo mund të vërtetohet dhe prova mbetet e vlefshme për çdo vlerë natyrore të k, atëherë, në përputhje me parimin e induksionit matematik, fjalia A (n) njihet si e vërtetë për të gjitha vlerat e n.
Metoda e induksionit matematik përdoret gjerësisht në vërtetimin e teoremave, identiteteve, pabarazive, në zgjidhjen e problemave për pjesëtueshmërinë, në zgjidhjen e disa problemeve gjeometrike e shumë të tjera.
Metoda e induksionit matematik në zgjidhjen e problemeve në
pjesëtueshmëria
Duke përdorur metodën e induksionit matematik, mund të vërtetohen pohime të ndryshme në lidhje me pjesëtueshmërinë e numrave natyrorë.
Deklarata e mëposhtme mund të jetë relativisht e lehtë për t'u provuar. Le të tregojmë se si fitohet duke përdorur metodën e induksionit matematik.
Shembulli 1... Nëse n është një numër natyror, atëherë numri është çift.
Për n = 1 pohimi ynë është i vërtetë: - një numër çift. Supozoni se është një numër çift. Meqenëse, një 2k është një numër çift, atëherë 
madje. Pra, barazia vërtetohet për n = 1, barazia nxirret nga barazia 
Pra, edhe për të gjitha vlerat natyrore të n.
Shembulli 2.Vërtetoni se fjalia është e vërtetë
A (n) = (5 është shumëfish i 19), n është një numër natyror.
Zgjidhje.
Pohimi A (1) = (shumë i 19) është i vërtetë.
Supozoni se për një vlerë n = k
A (k) = (shumë e 19) është e vërtetë. Pastaj që
Natyrisht, A (k + 1) është gjithashtu e vërtetë. Në të vërtetë, termi i parë është i pjesëtueshëm me 19 për shkak të supozimit se A (k) është e vërtetë; termi i dytë është gjithashtu i pjesëtueshëm me 19, sepse përmban faktorin 19. Të dy kushtet e parimit të induksionit matematik janë të plotësuara, prandaj, propozimi A (n) është i vërtetë për të gjitha vlerat e n-së.
Zbatimi i metodës së induksionit matematik në
përmbledhja e serive
Shembulli 1.Provoni Formulën
, n është një numër natyror.
Zgjidhje.
Për n = 1, të dyja anët e barazisë bëhen një dhe, për rrjedhojë, kushti i parë i parimit të induksionit matematik plotësohet.
Supozoni se formula është e vërtetë për n = k, d.m.th.
.
Shtoni këtë barazi në të dy anët dhe transformoni anën e djathtë. Pastaj marrim
Kështu, duke qenë se formula është e vërtetë për n = k, rrjedh se ajo është gjithashtu e vërtetë për n = k + 1. Ky pohim është i vërtetë për çdo vlerë natyrore të k. Pra, plotësohet edhe kushti i dytë i parimit të induksionit matematik. Formula është e vërtetuar.
Shembulli 2.Vërtetoni se shuma e n numrave të parë të serisë natyrore është e barabartë me.
Zgjidhje.
Le të shënojmë shumën e kërkuar, d.m.th. 
.
Për n = 1, hipoteza është e vërtetë.
Le te jete 
... Le ta tregojmë atë 
.
Me të vërtetë,
Problemi është zgjidhur.
Shembulli 3.Vërtetoni se shuma e katrorëve të n numrave të parë të serisë natyrore është e barabartë me 
.
Zgjidhje.
Le te jete .
.
Le të pretendojmë se 
... Pastaj
Dhe së fundi.
Shembulli 4. Vërtetoni këtë.
Zgjidhje.
Nese atehere
Shembulli 5. Vërtetoni këtë
Zgjidhje.
Për n = 1, hipoteza është padyshim e vërtetë.
Le te jete .
Le ta vërtetojmë atë.
Vërtet,
Shembuj të aplikimit të metodës së induksionit matematik në
vërtetimi i pabarazive
Shembulli 1.Vërtetoni se për çdo numër natyror n> 1
.
Zgjidhje.
Ne shënojmë anën e majtë të pabarazisë me.
Prandaj, për n = 2, pabarazia është e vërtetë.
Le për disa k. Le të vërtetojmë se atëherë dhe. Ne kemi 
, .
Krahasimi dhe, kemi 
, d.m.th. 
.
Për çdo numër natyror k, ana e djathtë e barazisë së fundit është pozitive. Kjo është arsyeja pse. Por, prandaj, dhe.
Shembulli 2.Gjeni një gabim në arsyetim.
deklaratë. Për çdo numër natyror n, pabarazia vlen.
Dëshmi.
. (1)
Le të vërtetojmë se atëherë pabarazia është gjithashtu e vlefshme për n = k + 1, d.m.th.
.
Në të vërtetë, të paktën 2 për çdo numër natyror k. Ne shtojmë pabarazinë (1) në anën e majtë dhe 2 në anën e djathtë. Marrim një pabarazi të vlefshme, ose 
... Deklarata është e vërtetuar.
Shembulli 3.Vërtetoni këtë 
, ku> -1,, n është një numër natyror më i madh se 1.
Zgjidhje.
Për n = 2, pabarazia është e vlefshme, pasi.
Le të jetë e vlefshme mosbarazimi për n = k, ku k është një numër natyror, d.m.th.
. (1)
Le të tregojmë se atëherë pabarazia është gjithashtu e vlefshme për n = k + 1, d.m.th.
. (2)
Në të vërtetë, sipas hipotezës, pra, pabarazia
, (3)
përftohet nga pabarazia (1) duke shumëzuar çdo pjesë të tij me. Ne e rishkruajmë pabarazinë (3) si më poshtë:. Duke hequr termin pozitiv në anën e djathtë të pabarazisë së fundit, marrim pabarazinë e vlefshme (2).
Shembulli 4. Vërtetoni këtë
(1)
ku,, n është një numër natyror më i madh se 1.
Zgjidhje.
Për n = 2, pabarazia (1) merr formën
. (2)
Meqenëse, atëherë pabarazia është e vërtetë
. (3)
Duke i shtuar secilës pjesë të pabarazisë (3) në lidhje me, marrim pabarazinë (2).
Kjo vërteton se pabarazia (1) vlen për n = 2.
Le të jetë e vlefshme pabarazia (1) për n = k, ku k është një numër natyror, d.m.th.
. (4)
Le të vërtetojmë se atëherë pabarazia (1) duhet të jetë gjithashtu për n = k + 1, d.m.th.
(5)
Ne i shumëzojmë të dyja anët e pabarazisë (4) me a + b. Meqenëse, sipas kushtit, marrim pabarazinë e vlefshme të mëposhtme:
. (6)
Për të vërtetuar vlefshmërinë e pabarazisë (5), mjafton të tregohet se
, (7)
ose, e cila është e njëjtë,
. (8)
Pabarazia (8) është e barabartë me pabarazinë
. (9)
Nëse, atëherë, dhe në anën e majtë të pabarazisë (9) kemi produktin e dy numrave pozitivë. Nëse, atëherë, dhe në anën e majtë të pabarazisë (9) kemi produktin e dy numrave negativë. Në të dyja rastet, pabarazia (9) është e vlefshme.
Kjo vërteton se vlefshmëria e pabarazisë (1) për n = k nënkupton vlefshmërinë e saj për n = k + 1.
Metoda e induksionit matematik që zbatohet për të tjerët
detyrat
Zbatimi më i natyrshëm i metodës së induksionit matematik në gjeometri, afër përdorimit të kësaj metode në teorinë e numrave dhe në algjebër, është aplikimi për zgjidhjen e problemeve gjeometrike llogaritëse. Le të shohim disa shembuj.
Shembulli 1.Llogaritni anën e së djathtës - një katror të gdhendur në një rreth me rreze R.
Zgjidhje.
Për n = 2 saktë 2 n - gon është një katror; ana e tij. Më tej, sipas formulës së dyfishimit
gjejmë se brinja e një tetëkëndëshi të rregullt 
, faqe e një gjashtëkëndëshi të rregullt 
, faqe e një tridhjetë e rregullt 
... Prandaj, mund të supozojmë se ana e saktë e gdhendur 2 n - gon për çdo është e barabartë me
. (1)
Supozoni se ana e saktë e mbishkruar - gon shprehet me formulën (1). Në këtë rast, sipas formulës së dyfishimit
,
prej nga rezulton se formula (1) është e vlefshme për të gjitha n.
Shembulli 2.Në sa trekëndësha mund të ndahet një n-këndësh (jo domosdoshmërisht konveks) me diagonalet e tij të shkëputura?
Zgjidhje.
Për një trekëndësh, ky numër është i barabartë me një (asnjë diagonale nuk mund të vizatohet në një trekëndësh); për një katërkëndësh, ky numër është padyshim i barabartë me dy.
Supozoni se tashmë e dimë se çdo k-gon, ku k
Një n
A 1 A 2
Le të jetë А 1 А k një nga diagonalet e kësaj ndarjeje; ai e ndan n-gon A 1 А 2 ... А n në k-gon A 1 A 2 ... A k dhe (nk + 2) -gon А 1 А k A k + 1 ... A n. Në bazë të këtij supozimi, numri i përgjithshëm i trekëndëshave në ndarje do të jetë i barabartë me
(k-2) + [(n-k + 2) -2] = n-2;
kjo dëshmon pohimin tonë për të gjithë n.
Shembulli 3.Tregoni rregullin për llogaritjen e numrit P (n) në mënyrat në të cilat një n-këndësh konveks mund të ndahet në trekëndësha me diagonale të shkëputura.
Zgjidhje.
Për një trekëndësh, ky numër është padyshim i barabartë me një: P (3) = 1.
Supozoni se ne kemi përcaktuar tashmë numrat P (k) për të gjithë k
P (n) = P (n-1) + P (n-2) P (3) + P (n-3) P (4) +… + P (3) P (n-2) + P (n -1).
Duke përdorur këtë formulë, ne marrim me sukses:
P (4) = P (3) + P (3) = 2,
P (5) = P (4) + P (3) P (3) + P (4) +5,
P (6) = P (5) + P (4) P (3) + P (3) P (4) + P (5) = 14
etj.
Gjithashtu, duke përdorur metodën e induksionit matematik, mund të zgjidhni probleme me grafikë.
Le të ketë një rrjet vijash në aeroplan që lidh disa pika dhe nuk ka pika të tjera. Ne do ta quajmë një rrjet të tillë vijash një hartë, pikat e dhëna nga kulmet e saj, segmentet e kthesave midis dy kulmeve ngjitur - kufijtë e hartës, pjesët e rrafshit në të cilin ndahet me kufij - vendet e hartës.
Le të jepet një hartë në aeroplan. Do të themi se është lyer saktë nëse secili prej vendeve të tij është i lyer me një bojë të caktuar dhe çdo dy shtete që kanë një kufi të përbashkët janë lyer me ngjyra të ndryshme.
Shembulli 4.Ka n rrathë në aeroplan. Vërtetoni se për çdo rregullim të këtyre rrathëve, harta e formuar prej tyre mund të ngjyroset saktë me dy ngjyra.
Zgjidhje.
Për n = 1, deklarata jonë është e qartë.
Supozoni se pohimi ynë është i vërtetë për çdo tabelë të formuar nga n rrathë, dhe le të jepen n + 1 rrathë në plan. Duke hequr një nga këto rrathë, marrim një hartë, e cila, në bazë të supozimit të bërë, mund të ngjyroset saktë me dy ngjyra, për shembull, bardh e zi.
Induksioni është një metodë për të marrë një deklaratë të përgjithshme nga vëzhgime të veçanta. Në rastin kur një pohim matematikor ka të bëjë me një numër të kufizuar objektesh, ai mund të vërtetohet duke kontrolluar për secilin objekt. Për shembull, pohimi: "Çdo numër çift dyshifror është shuma e dy numrave të thjeshtë," - rrjedh nga një seri barazish që janë mjaft realiste për t'u vendosur:
10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.
Një metodë vërtetimi që kontrollon një deklaratë për një numër të kufizuar rastesh që shterojnë të gjitha mundësitë quhet induksion i plotë. Kjo metodë përdoret relativisht rrallë, pasi deklaratat matematikore kanë të bëjnë, si rregull, jo grupe të fundme, por të pafundme objektesh. Për shembull, pohimi për numrat çift dyshifrorë i vërtetuar më sipër me induksion të plotë është vetëm një rast i veçantë i teoremës: "Çdo numër çift është shuma e dy numrave të thjeshtë". Kjo teoremë as nuk është vërtetuar dhe as nuk është hedhur poshtë deri më tani.
Induksioni matematik është një metodë për të vërtetuar disa pohime për çdo n natyral bazuar në parimin e induksionit matematik: “Nëse pohimi është i vërtetë për n = 1 dhe nëse është i vërtetë për n = k, rrjedh se ky pohim është i vërtetë për n = k + 1, atëherë është e vërtetë për të gjitha n ". Metoda e vërtetimit me metodën e induksionit matematik është si më poshtë:
1) baza e induksionit: vërtetoni ose kontrolloni drejtpërdrejt vlefshmërinë e pohimit për n = 1 (ndonjëherë n = 0 ose n = n 0);
2) hapi i induksionit (tranzicioni): supozoni vlefshmërinë e pohimit për disa n = k natyrore dhe, bazuar në këtë supozim, provoni vlefshmërinë e pohimit për n = k + 1.
Problemet me zgjidhjet
1. Vërtetoni se për çdo n natyrore numri 3 2n + 1 + 2 n + 2 pjesëtohet me 7.
Shënojmë A (n) = 3 2n + 1 + 2 n + 2.
Baza e induksionit. Nëse n = 1, atëherë A (1) = 3 3 +2 3 = 35 dhe, padyshim, është i pjesëtueshëm me 7.
Hipoteza e induksionit. Le të jetë A (k) i pjesëtueshëm me 7.
Tranzicioni i induksionit. Le të vërtetojmë se A (k + 1) pjesëtohet me 7, domethënë vlefshmëria e pohimit të problemit për n = k.
A (k + 1) = 3 2 (k + 1) +1 +2 (k + 1) +2 = 3 2k + 1 3 2 +2 k + 2 2 1 = 3 2k + 1 9 + 2 k + 2 2 =
3 2k + 1 9 + 2 k + 2 (9–7) = (3 2k + 1 +2 k + 2) 9–7 2 k + 2 = 9 A (k) –7 2 k +2.
Numri i fundit plotpjesëtohet me 7, pasi është ndryshimi i dy numrave të plotë të pjesëtueshëm me 7. Prandaj, 3 2n + 1 + 2 n + 2 pjesëtohet me 7 për çdo n natyrale.
2. Vërtetoni se për çdo n natyrore numri 2 3 n +1 pjesëtohet me 3 n + 1 dhe nuk pjesëtohet me 3 n + 2.
Le të prezantojmë shënimin: а i = 2 3 i +1.
Për n = 1 kemi, dhe 1 = 2 3 + 1 = 9. Pra, një 1 pjesëtohet me 3 2 dhe nuk pjesëtohet me 3 3.
Le të jetë për n = k numri a k është i pjesëtueshëm me 3 k + 1 dhe i papjesëtueshëm me 3 k + 2, pra a k = 2 3 k + 1 = 3 k + 1 m, ku m nuk pjesëtohet me 3. Atëherë
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 ((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).
Natyrisht, një k + 1 pjesëtohet me 3 k + 2 dhe nuk pjesëtohet me 3 k + 3.
Prandaj, pohimi vërtetohet për çdo numër natyror n.
3. Dihet se x + 1 / x është një numër i plotë. Vërtetoni se x n + 1 / x n është gjithashtu një numër i plotë për çdo numër të plotë n.
Le të prezantojmë shënimin: a i = x i + 1 / x i dhe menjëherë të vërejmë se a i = a –i, prandaj, më tej do të flasim për indekset natyrore.
Shënim: a 1 është një numër i plotë sipas kushtit; a 2 është një numër i plotë, pasi a 2 = (a 1) 2 –2; a 0 = 2.
Supozoni se një k është numër i plotë për çdo numër natyror k që nuk e kalon n. Atëherë a 1 · a n është një numër i plotë, por a 1 · a n = a n + 1 + a n – 1 dhe a n + 1 = a 1 · a n –a n – 1. Sidoqoftë, dhe n – 1, sipas hipotezës së induksionit, është një numër i plotë. Prandaj, një n + 1 është gjithashtu një numër i plotë. Prandaj, x n + 1 / x n është një numër i plotë për çdo numër të plotë n, siç kërkohet.
4. Vërtetoni se për çdo n natyrore më të madhe se 1 vlen pabarazia e dyfishtë:
5. Vërtetoni se për n natyrore n> 1 dhe | х |
(1 – x) n + (1 + x) n
Për n = 2, pabarazia është e vërtetë. Vërtet,
(1 – x) 2 + (1 + x) 2 = 2 + 2 x 2
Nëse pabarazia është e vërtetë për n = k, atëherë për n = k + 1 kemi
(1 – x) k + 1 + (1 + x) k + 1
Jobarazia vërtetohet për çdo numër natyror n> 1.
6. Ka n rrathë në aeroplan. Vërtetoni se për çdo rregullim të këtyre rrathëve, harta e formuar prej tyre mund të ngjyroset saktë me dy ngjyra.
Le të përdorim metodën e induksionit matematik.
Për n = 1, deklarata është e qartë.
Supozoni se pohimi është i vërtetë për çdo tabelë të formuar nga n rrathë dhe le të jepen n + 1 rrathë në plan. Duke hequr një nga këto rrathë, ne marrim një hartë, e cila, për shkak të supozimit të bërë, mund të ngjyroset saktë me dy ngjyra (shih foton e parë më poshtë).
Pastaj rivendosni rrethin e hedhur dhe në njërën anë të tij, për shembull, brenda, ndryshoni ngjyrën e secilës zonë në të kundërtën (shih figurën e dytë). Është e lehtë të shihet se në këtë rast do të marrim një hartë, të ngjyrosur saktë me dy ngjyra, por vetëm tani për rrathët n + 1, gjë që duhej të vërtetonim.
7. Një shumëkëndësh konveks do të quhet "i bukur" nëse plotësohen kushtet e mëposhtme:
1) secila nga kulmet e saj është e ngjyrosur në një nga tre ngjyrat;
2) çdo dy kulme ngjitur janë të ngjyrosura me ngjyra të ndryshme;
3) të paktën një kulm i shumëkëndëshit është i ngjyrosur në secilën nga tre ngjyrat.
Vërtetoni se çdo n-gon i bukur mund të pritet me diagonale të shkëputura në trekëndësha "të bukur".
Le të përdorim metodën e induksionit matematik.
Baza e induksionit. Për n = 3 më të vogël të mundshme, pohimi i problemit është i qartë: kulmet e një trekëndëshi "të bukur" ngjyrosen në tre ngjyra të ndryshme dhe nuk nevojiten prerje.
Hipoteza e induksionit. Supozoni se deklarata e problemit është e vërtetë për çdo n-gon "të bukur".
Hapi i induksionit. Konsideroni një "e bukur" arbitrare (n + 1) -gon dhe provoni, duke përdorur hipotezën e induksionit, se mund të pritet nga disa diagonale në trekëndësha "të bukur". Le të shënojmë me А 1, А 2, А 3, ... А n, А n + 1 - kulme të njëpasnjëshme të (n + 1) -gon. Nëse vetëm një kulm i (n + 1) -gon është i ngjyrosur në ndonjë nga tre ngjyrat, atëherë, duke e lidhur këtë kulm me diagonalet me të gjitha kulmet që nuk janë ngjitur me të, marrim ndarjen e nevojshme të (n + 1) - shkoni në trekëndësha "të bukur".
Nëse të paktën dy kulme të (n + 1) -gon janë të ngjyrosura në secilën nga tre ngjyrat, atëherë shënojmë me numrin 1 ngjyrën e kulmit A1 dhe me numrin 2 ngjyrën e kulmit A2. Le të jetë k numri më i vogël i tillë që kulmi А k të ngjyroset në ngjyrën e tretë. Është e qartë se k> 2. Prerë nga (n + 1) -gon nga diagonalja А k – 2 А k trekëndëshi А k – 2 А k – 1 А k. Në përputhje me zgjedhjen e numrit k, të gjitha kulmet e këtij trekëndëshi janë ngjyrosur në tre ngjyra të ndryshme, domethënë ky trekëndësh është "i bukur". n-gon konveks А 1 А 2 ... А k – 2 А k А k + 1 ... А n + 1, i cili mbetet, gjithashtu, në bazë të supozimit induktiv, do të jetë "i bukur", që do të thotë ndahet në trekëndësha "të bukur", të cilët dhe kërkohej të vërtetoheshin.
8. Vërtetoni se nuk mund të zgjidhen më shumë se n diagonale në një kënd konveks, në mënyrë që çdo dy prej tyre të ketë një pikë të përbashkët.
Le ta bëjmë vërtetimin me metodën e induksionit matematik.
Le të provojmë një pohim më të përgjithshëm: në një kënd konveks n, nuk mund të zgjidhni më shumë se n anë dhe diagonale në mënyrë që çdo dy prej tyre të ketë një pikë të përbashkët. Për n = 3, deklarata është e qartë. Supozoni se ky pohim është i vërtetë për një n-këndor arbitrar dhe, duke përdorur këtë, ne vërtetojmë vlefshmërinë e tij për një gon arbitrar (n + 1).
Supozoni se ky pohim nuk është i vërtetë për një (n + 1) -gon. Nëse jo më shumë se dy anë ose diagonale të zgjedhura dalin nga çdo kulm i një (n + 1) -gon, atëherë zgjidhen jo më shumë se n + 1 prej tyre. Prandaj, të paktën tre anë ose diagonale të zgjedhura AB, AC, AD dalin nga një kulm A. Lëreni AC të shtrihet midis AB dhe AD. Meqenëse çdo anë ose diagonale që del nga pika C dhe është e ndryshme nga CA nuk mund të presë AB dhe AD në të njëjtën kohë, atëherë vetëm një diagonale e zgjedhur CA del nga pika C.
Duke rënë pikën C së bashku me diagonalen CA, marrim një n-këndësh konveks në të cilin janë zgjedhur më shumë se n anë dhe diagonale, çdo dy prej të cilave kanë një pikë të përbashkët. Kështu, arrijmë në një kontradiktë me supozimin se pohimi është i vërtetë për një n-gon konveks arbitrar.
Pra, për (n + 1) -gon deklarata është e vërtetë. Në përputhje me parimin e induksionit matematik, pohimi është i vërtetë për çdo n-gon konveks.
9. Në rrafsh vizatohen n drejtëza nga të cilat nuk ka dy paralele dhe nuk kalojnë tre në një pikë. Në sa pjesë e ndajnë avionin këto vija?
Me ndihmën e vizatimeve elementare, është e lehtë të siguroheni që një vijë e drejtë e ndan avionin në 2 pjesë, dy vija të drejta - në 4 pjesë, tre vija të drejta - në 7 pjesë, katër vija të drejta - në 11 pjesë.
Le të tregojmë N (n) numrin e pjesëve në të cilat n rreshta ndajnë rrafshin. Ju mund ta shihni atë
N (2) = N (1) + 2 = 2 + 2,
N (3) = N (2) + 3 = 2 + 2 + 3,
N (4) = N (3) + 4 = 2 + 2 + 3 + 4.
Është e natyrshme të supozohet se
N (n) = N (n – 1) + n = 2 + 2 + 3 + 4 + 5 +… + n,
ose, siç është e lehtë të përcaktohet, duke përdorur formulën për shumën e n termave të parë të një progresion aritmetik,
N (n) = 1 + n (n + 1) / 2.
Le të vërtetojmë vlefshmërinë e kësaj formule me metodën e induksionit matematik.
Për n = 1, formula tashmë është verifikuar.
Duke bërë hipotezën e induksionit, merrni parasysh k + 1 rreshta që plotësojnë kushtin e problemit. Le të zgjedhim k rreshta prej tyre në mënyrë arbitrare. Sipas hipotezës së induksionit, ata e ndajnë planin në 1+ k (k + 1) / 2 pjesë. Drejtëza e mbetur (k + 1) -të do të ndahet nga k drejtëzat e zgjedhura në k + 1 pjesë dhe, për rrjedhojë, do të kalojë përgjatë pjesës së (k + 1) -të, në të cilën plani tashmë është ndarë. , dhe ndani secilën nga këto pjesë në 2 pjesë, domethënë do të shtohet një pjesë tjetër k + 1. Kështu që,
N (k + 1) = N (k) + k + 1 = 1 + k (k + 1) / 2 + k + 1 = 1 + (k + 1) (k + 2) / 2,
Q.E.D.
10. Në shprehjen x 1: x 2:…: x n, vendosen kllapa për të treguar rendin e veprimeve dhe rezultati shkruhet si thyesë:
(në këtë rast, secila nga shkronjat x 1, x 2, ..., x n është ose në numëruesin e thyesës, ose në emërues). Sa shprehje të ndryshme mund të merrni në këtë mënyrë me të gjitha llojet e kllapave?
Para së gjithash, është e qartë se në thyesën që rezulton x 1 do të jetë në numërues. Është pothuajse po aq e qartë se x 2 do të shfaqet në emërues për çdo kllapa (shenja e pjesëtimit përpara x 2 i referohet ose vetë x 2, ose ndonjë shprehjeje që përmban x 2 në numërues).
Mund të supozohet se të gjitha shkronjat e tjera x 3, x 4, ..., x n mund të vendosen në numërues ose emërues në një mënyrë krejtësisht arbitrare. Nga kjo rrjedh se gjithsej mund të merrni 2 n – 2 thyesa: secila prej n – 2 shkronjave x 3, x 4,…, x n mund të shfaqet në mënyrë të pavarur nga të tjerat në numërues ose emërues.
Le ta vërtetojmë këtë deklaratë me induksion.
Me n = 3, mund të merrni 2 fraksione:
kështu që deklarata është e vërtetë.
Supozoni se është e vlefshme për n = k dhe provojeni për n = k + 1.
Le të shkruhet shprehja x 1: x 2:…: xk, pas një rregullimi të kllapave, në formën e një thyese Q. Nëse xk: xk + 1 zëvendësohet në këtë shprehje në vend të xk, atëherë xk do të jetë në i njëjti vend ku ishte në thyesën Q, dhe x k + 1 nuk do të jetë aty ku qëndronte x k (nëse x k ishte në emërues, atëherë x k + 1 do të jetë në numërues dhe anasjelltas).
Tani do të vërtetojmë se është e mundur të shtojmë х k + 1 në të njëjtin vend ku qëndron х k. Në thyesën Q, pas vendosjes së kllapave, do të jetë domosdoshmërisht një shprehje e formës q: x k, ku q është shkronja x k – 1 ose ndonjë shprehje në kllapa. Duke zëvendësuar q: x k me shprehjen (q: x k): x k + 1 = q: (x k x k + 1), padyshim marrim të njëjtën thyesë Q, ku në vend të x k është x k x k + 1.
Kështu, numri i të gjitha thyesave të mundshme në rastin n = k + 1 është 2 herë më i madh se në rastin n = k dhe është i barabartë me 2 k – 2 · 2 = 2 (k + 1) –2. Kjo dëshmon deklaratën.
Përgjigje: 2 n – 2 thyesa.
Detyra pa zgjidhje
1. Vërtetoni se për çdo numër natyror n:
a) numri 5 n –3 n + 2n pjesëtohet me 4;
b) numri n 3 + 11n pjesëtohet me 6;
c) numri 7 n + 3n – 1 pjesëtohet me 9;
d) numri 6 2n +19 n –2 n + 1 pjesëtohet me 17;
e) numri 7 n + 1 +8 2n – 1 pjesëtohet me 19;
f) numri 2 2n – 1 –9n 2 + 21n – 14 plotpjesëtohet me 27.
2. Vërtetoni se (n + 1) · (n + 2) ·… · (n + n) = 2 n · 1 · 3 · 5 ·… · (2n – 1).
3. Vërtetoni pabarazinë | sin nx | n | mëkat x | për çdo n natyrore.
4. Gjeni numra natyrorë a, b, c që nuk janë të pjesëtueshëm me 10 dhe të tillë që për çdo n natyrore numrat a n + b n dhe c n të kenë dy shifrat e fundit të njëjta.
5. Vërtetoni se nëse n pika nuk shtrihen në një vijë të drejtë, atëherë midis vijave që i lidhin ato, ka të paktën n të ndryshme.