Matematik induksiya metodi va uning bazi tadbiqlari

Natural sonlar arifmetikasi va matematik induksiya metodi
Matematik induksiya metodi degan nom bir oz noqulayroq tanlangan bo'lib, uning induksiya metodi bilan hech qanday umumiyligi yo'q.
Matematik induksiya metodi ₋deduktiv metod , u induktiv mulohazalar yordamida aniqlangan tasdiqlarning qatiy isbotini beradi yoki uni qatiyan rad etadi.
Bu metodning asosini aniqlaylik. Matematik induksiya bilan isbotlaganimizda :agar biror A(n) tasdiq n=1 uchun o'rinli bo'lsa ,n=k uchun A(n) tasdiqni to'g'ri deb faraz qilib,n=k+1 uchun uning to'g'riligini isbotladik va shundan so'ng aytilgan A(n) tasdiq istalgan n natural son uchun to'g'ri deb hulosa qildik.
Bu mulohazalardan ,agar A(n) tasdiq n=1 da to'g'ri bo'lsa ,u n=2 ,n=3,n=4 va hokazalar uchun o'rinli bo'ladi,demak,u barcha n natural son uchun to'g'ri bo'ladi.
Bu yerda natural sonlar tushunchasi o'z-o'zidan ayon ,izoh talab qilmaydigan tushuncha deb hisoblangan edi.Ammo hozirgi zamon matematikasida o'z-o'zidan ayon tushunchalardan foydalanilmasdan ,har qanday tushuncha avvaldan ma'lum tushunchalar yordamida aniqlangan bo'lishi yoki aksiomatik kiritilishi kerak .
Arifmetika uchun bunday boshlang'ich tushunchalar birlik,natural son va «bundan keyin keladi » tushunchalari bo'lib ,bu tushunchalarning asosiy xossalari₋Peano aksiomalaridir.
Bu aksiomalar natural son tushunchasini aniqlashga bag'ishlanadi.
«Bundan keyin keladi » degan munosabat o'rinli bo'lgan (n dan keyin keluvchi sonni n' orqali belgilaymiz ) har qanday bo'sh bo'lmagan N to'plamning elementlari natural sonlar deb ataladi .Bu munosabat quyidagi aksiomalarga bo'ysunishi kerak:
1-aksioma. Hech qanday sondan keyin kelmaydigan 1 raqami mavjud .
2-aksioma .Har qanday n son uchun undan keyin keladigan bitta va faqat bittagina n' son mavjud , yani n=m ekanligidan n'=m' ekani kelib chiqadi.
3-aksioma .Har qanday son bittadan ortiq bo'lmagan sondan keyin keladi,yani n'=m' dan n=m ekani kelib chiqadi.
4-aksioma.Natural sonlarning M to'plami quyidagi hossalarga ega bo'lsin:
a)bir soni M ga tegishli :
b) agar n soni M ga tegishli bo'lsa ,u holda n'=n+1 ham M ga tegishli bo'lsa,u holda M to'plamda hamma natural sonlar bo'ladi,yani barcha natural sonlar to'plami M ustma-ust tushadi.
To'rtinchi aksioma matematik induksiya aksiomasi deyiladi,matematik induksiya metodi shu aksiomaga asoslangandir.
Haqiqatan ham A(1) tasdiq rost bo'lsin ,A(k) ning rostligidan A(k+1) ning rostligi kelib chiqsin. A(n) tasdiq o'rinli bo'lgan natural sonlar to'plami M deylik.
Farazga ko'ra 1€M (tasdiq n=1 da o'rinli), k€M dan k'€M kelib chiqadi.(agar n=k da A(n) o'rinli bo'lsa ,u holda u n=k'=k+1 uchun ham o'rinli).U holda 4-aksiomaga asosan M to'plam barcha natural sonlar to'plami bilan ustma-ust tushadi.Demak,A(n) tasdiq barcha natural sonlar uchun o'rinlidir.
Natural sonlar arifmetikasida matematik induksiya metodiasosiy metoddir.Arifmetikani aksiomatik qurishda natural sonlar ustida bajariladigan barcha amallar shu metod yordamida aniqlanadi.
Natural sonlarni qo'shish va ayirish amallari va bu amallar hossalarining isboti ,katta va kichik munosabatlari va ular xossalarining isboti matematik induksiya metodi orqali beriladi.
17-misol Birdal farqli har qanday n son uchun undan oldin keluvchi m son mavjud ,yani m'=n.
ISBOTI.O'zidan oldin keluvchi sonlari bor bo'lgan natural sonlar to'plami bilan 1 ni birlashtirib ,hosil bo'lgan to'plamni M orqali belgilaylik.
M to'plamning tuzilishiga ko'ra 1€M.k€M bo'lsin , u holda k' sondan avval keluvchi k son bor bo'lganligidan k'€kelib chiqadi.Demak ,M to'plam barcha natural sonlar to'plami bilan ustma-ust tushadi.Bundan esa ,1 dan boshqa barcha natural sonlar o'zidan oldin keluvchi songa ega (3-aksiomaga asosan, bundan oldin keluvchi son yagonadir.)
18-misol .Natural sonlar to'plamining ixtiyoriy bo'shmas qism to'plami B ga eng kichik son mavjud .
Bu xossa natural sonlar to'plamining to'la tartiblanganlik xossasi deyiladi.
Isboti.Agar 1€B bo'lsa,u holda 1 soni B to'plamga eng kichik son bo'ladi. 1 tegishlimas B va M B to'plamning b sonidan kichik bo'lgan natural sonlar to'plami bo'lsa , u holda M to'plam har qanday a soni bilan birgalikda undan bevosita keyin keluvchi a' sonini ham o'z ichiga ololmaydi ,aks holda 4-aksiomaga asosan ,M to'plam barcha natural sonlarni o'z ichiga olib,B to'plam esa bo'sh bo'lar edi.Shu sababli M to'plamda shunday n son topiladiki ,n' son M da yotmaydi .nBu misoldan matematik induksiya aksiomasiga teng kuchli bo'lgan ushbu tasdiq kelib chiqadi.
19-misol .Agar A(n) tasdiq n=1 da o'rinli bo'lsa va uning barcha nIsboti.Natural sonlar to'plamining A(n) tasdiq bajarilmaydigan qismini M deb belgilaylik.Agar bu to'plam bo'sh bo'lmasa ,18-misoldagi tasdiqga asosan bu to'plamda eng kichik k son mavjud bo'ladi.k chunki , shartga asosan, A(1) rost .Demak ,k>1.Ammo A(n) tasdiq bajarilmaydigan eng kichik natural son bo'lgani sababli ,n< k tengsizlikni qanoatlantiruvchi barcha n lar uchun A(n) bajariladi ,u holda teorema shartiga asosan A(n) tasdiq n=k da o’rinli. Bir vaqtning ozida A(k) tasdiq ham rost, ham yolgon bolib chiqdi. Hosil bolgan ziddiyatdan M , deb qilgan farazimiz noto'g'riligi kelib chiqdi.Demak ,M= yani A(n) tasdiq bajarilmaydigan natural son yo'q.Bu esa A(n) tasdiq barcha n natural sonlar uchun o'rinli ekanini bildiradi.
20-misol .n³+2n ifoda qanday songa karrali ekanini aniqlashni vazifa qilib olaylik.
Yechilishi .n ga ketma-ket qiymatlar berib n³+2n ifodaning qiymatlarini tekshiraylik va biror qonuniyatni aniqlashga harakat qilaylik.
n=1 bo'lsa,1³+2*1=3-3 ga karrali son hosil bo'ldi.
n=2 bo'lsa, 2³+2*2=12=3*4—yana 3 ga karrali son hosil bo'ldi.
n=3 bo'lsa,3³+2*3=33=3*11—bu son ham 3 ga bo'linadi.
n=4 bo'lsa,4³+2*4=72=3*24 –yana 3 ga karrali son hosil bo'ladi .Demak , n=1,2,3,4 bo'lganda n³+2n yig'indi 3 ga bo'linar ekan.
Ushbu gipoteza o'rinli emasmikin?
n³+2n yig'indi ixtiyoriy n natural songa 3 ga karrali.
Endi bu gipotezaning rost yoki yolg'onligini aniqlaylik.Tekshirishni matematik induksiya metodi yordamida o'tkazamiz.
I.n=1 da 1³+2*1=3—3 ga karrali.
II.n=k da k³+2k—3 ga karrali bo'lsin,bundan foydalanib n=k+1 da (k+1)³+2(k+1) ifodaning 3 ga bo'linishini ko'rsatamiz.
Haqiqatan ham ,(k+1)³+2(k+1) =k³+3k²+3k+1+2k+2=(k³+2k)+3(k²+k+1) ifoda 3ga bo'linadi, chunki k³+2k 3ga karrali(farazga asosan),ikkinchi qo'shiluvchining 3 ga karrali ekani ko'rinib turildi.
Demak ,ixtiyoriy n natural son uchun n³+2n ifoda 3ga karrali ekan.
21-misol . N uchun n(n²+5) ifoda 6 ga karrali ekanligini isbotlang.
(Bu yerda va bundan keying misollarda N orqali natural sonlar to'plamini belgilaymiz.)
II .n=k da k(k²+5)—6 ga karrali bo'lsin deb faraz qilaylik,(k+1)[(k+1)²+5] ifodaning 6 ga qoldiqsiz bo'linishini ko'rsatamiz.Haqiqatan ham (k+1)[(k+1)²+5]=k(k²+5)+3k(k+1)+6 ifoda 6 ga karrali,chunki k(k²+5) farazga asosan 6 ga bo'linadi.k(k+1) ketma-ket sonlar ko'paytmasi juft bo'lgani uchun 3k(k+1) ham 6 ga bo'linadi, oxigi qo'shiluvchi esa 6 ning o'zi .Demak,matematik induksiya prinsipiga asosan da n(n²+5)-6 ga karrali.
22-misol . uchun
(n-1)³+n³+(n+1)³ (4.1)
Ifoda 9 ga bo'linishini ko'rsating.
Isboti. I.n=1 da 0³+1³+2³=9 ga karrali.
II.n=k da (k-1)³+k³+(k+1)³ ifoda 9 ga bo'linsin deb faraz qilib ,n=k+1 da k³+(k+1)³+(k+2)³ yig'indi 9 ga karrali bo'lishini ko'rsatamiz.Oxirgi ifodaning shaklini o'zgartiramiz:
k³+(k+1)³+(k+2)³=[(k-1)³+k³+(k+1)³]+(k+2)³-(k-1)³= [(k-1)³+k³+(k+1)³]+9*(k²+k+1).
Oxirgi ifodada o'rta qavs ichidagi yig'indi farazga asosan 9 ga bo'linadi,ikkinchi qo'shiluvchining 9 ga bo'linishi ko'rinib turibdi, demak (4.1) ifoda 9 ga karrali.
23-misol . uchun n⁷+6n ifoda 7ga karrali ekanini isbotlang.
Isboti.1.n=1 da tasdiq o'rinli
II.n=k (k≥1) da k⁷+6k 7 ga karrali bo'lsin deb faraz qilamiz va n=k+1 bo'lganda (k+1)⁷+6(k+1) yig'indi 7 ga bo'linishini isbotlaymiz.
Ushbu Nyuton binomi formulasidan foydalanamiz.(a+b)ⁿ=aⁿ aⁿ⁻¹+…….+ abⁿ⁻¹+bⁿ, (4.2)
Bunda
= , (n =1*2*3*………*n). (4.3)
(4.2) va (4.3) formulalarning isboti keying tegishli paragraflarda beriladi.
(4.2) va (4.3) ga binoan:
(k+1)⁷=k⁷+ k⁶+ k⁵+ k⁴+ + k²+ k+1=k⁷+7k⁶+21k⁵+35k⁴+21k²+7k+1.
Oxirgi munosabatni e'tiborga olsak,
(k+1)⁷+6(k+1)=(k⁷+6k)+7(k⁶+3k⁵+5k⁴+5k³+3k²+k+1)
Ifoda hosil bo'lib ,u 7 ga bo'linadigan ikkita qo'shiluvchidan iborat.
24-misol . uchun 3³ⁿ⁺²+2⁴ⁿ⁺¹ yig'indining 11 ga bo'linishini isbotlang .
Isboti .I.n=1 da 3³'¹⁺²+2⁴'¹⁺¹=275=11*25 tasdiq o'rinli .
II.n=k da 3³ᵏ⁺²+2⁴ᵏ⁺¹ 11ga karrali bo'lsin deb faraz qilamiz va n=k+1 bo'lganda 3³ⁿ⁺²+2⁴ⁿ⁺¹ ning 11 ga bo'linishini isbotlaymiz.So'nggi yig'indida shakl almashtirishlar bajaramiz: + = =27* +16* =11* +16( + ),
natijada qo'shiluvchilari 11 ga bo'linadigan yig'indini hosil qilamiz.
25-misol. -1 ikkihad 10 ning qanday darajasiga bo'linishini aniqlang.
Yechilishi .Induksiya yuritamiz ,ya'ni n ga turli qiymatlar berib yuqoridagi ayirmaning harakterini o'rganamiz.
n=1 bo'lsin,u holda
-1= -1=(11-1)(11⁹+11⁸+……+11¹+11º)=10(11⁹+11⁸+…..+11¹+11º).
Qavs ichidagi ifodada 10 ta qo'shiluvchi bor va ularning har biri 1 raqami bilan tugaydi ,shuning uchun ularning yig'indisi ham 10 ga bo'linadi.Demak ,
ayirma 10² ga bo'linadi.
n =2 bo'lsin,u holda
-1=(11¹º)¹º-1=(11¹º-1)[(11¹º)⁹+(11¹º)⁸+.....+(11¹º)¹+(11¹º)º].
Bunda 11¹º-1ning 10² ga bo'linishini yuqorida ko'rdik.2-qavsdagi 10 ta qo'shiluvchi 1 bilan tugagani sababli ularning yig'indisi 10 ga bo'linadi , demak, -1 ayirma 10³ ga bo'linadi.
n=3 bo'lsin :
-1=( )¹º-1=( -1)[( )⁹+( )⁸+….+( )¹+( )º].
Yuqoridagi mulohazalarni takrorlasak,birinchi qavsning 10³ga,o rta qavsdagi yig'indining 10 ga va -1 ayirmaning 10⁴ ga bo'linishiga ishonch hosil qilamiz.
O'rganilgan n=1,2,3 hollarda ushbu gipotezani aytish imkonini beradi:
da ( -1)
(Bu yerda qoldiqsiz bo'linish belgisi.)
Aytilgan tasdiqni isbotlaylik.
I.A(1) o'rinli ,chunki n=1 hol yuqorida tahlil qilindi.
II.A(k)=>A(k+1) ni isbotlaymiz ,yani n=k da ( -1) 10ᵏ⁺¹ deb faraz qilib,n=k+1 uchun ( -1) 10ᵏ⁺² bo'lishini ko'rsatamiz.
Haqiqatan ham ,
( -1)= )¹º-1=( -1)[( )⁹+ ( )⁸+……+ ( )¹+ ( )º]
Ifodada ( -1) 10ᵏ⁺¹ farazga ko'ra o'rta qavs ichidagi yig'indi esa yuqorida aytilganlarga asosan 10 ga karrali ,demak ,
( -1) 10ᵏ⁺²
Bu esa A(k+1)ning bajarilishini ko'rsatadi.
Ushbu misol matematik induksiyaga asoslanmay isbotlandi,lekin uning natijasini keyingi misolda foydalanamiz.
26-misol.(Fermaning kichik teoremasi) Agar p tub son bo'lsa, -n son p ga bo'linadi .
Isboti I.n=1 da -1=0 p.
II.n=k da ( -k) p.deb faraz qilib ,[ -(k+1)] p bo'lishini ko'rsataylik.Shu maqsadda ushbu
-(k+1)- -k)
Ayirmani qaraymiz.(4.2)Nyuton binomi formulasiga asosan
-(k+1)- -k)= - -1=
= + +….+ k.
Ammo 1 ≤j
uchun
=
formula o'rinli va p tub son bo'lgani uchun maxrajdagi 1,2,3…,j sonlarning birortasiga ham bo'linmaydi.Shu sababli (1≤j≤p) p ga bo'linadi.Buni e'tiborga olsak (4.4) tenglikning o'ng tomonidagi barcha hollar p ga bo'linadi,demak ,chap tomon ham p ga bo'linadi,demak,chap tomon ham p ga bo'linadi.Farazga ko'ra,
( -k) bo'lganligidan -(k+1)] ekani kelib chiqadi.
31-misol.(Arifmatikaning asosiy teoremasining .)
Noldan farqli har qanday butun son tub sonlar ko'paytmasi ko'rinishida ifodalanishi mumkin va bu ifoda ko'paytuvchilarning tartibi hamda ishorasi aniqligida yagonadir.
Mavjudligining isboti .I.n=1 da 1=1 .1 bo'sh to'plamdagi tub sonlar ko'paytmasidir.
II.mn murakkab son bo'lsin,u holda n son ikkita n₁ va n₂ butun sonlar ko'paytmasidan iborat bo'ladi,yani n=n₁*n₂ hamda bu sonlar 1 va n dan farqli bo'ladi, shu sababli n₁n₁=p₁*p₂…..*pₜ , n₂=q₁*q₂……*qₛ,
bunda p₁,p₂,…,pₜ,q₁,q₂,….,qₛ-tub sonlar.U holda izlanayotgan yoyilmaga ega bo'lamiz:
n=p₁*p₂..*pₜ* q₁*q₂……*qₛ.
Agar n manfiy butun son bo'lsa,-n musbat son bo'ladi va yuqoridagi isbotlanganiga ko'ra –n=p₁*p₂*…….*pₖ (k=r+s)
yoyilma o'rinli bo'ladi.U holda
n=(-1) p₁*p₂*…….*pₖ
yoki
n=- p₁*p₂*…….*pₖ
shunday qilib mavjudlik isbotlandi.
Yagonalikning isboti.Tub sonlarning ushbu xossasidan foydalanamiz.
Agar n son p tub songa bo'linsa,u holda n son tub ko'paytuvchilarga har qanday usulda ajratilganda ham ko'paytuvchilarning bittasi p gat eng bo'ladi.
Haqiqatan ham n son p ga bo'linsin va
n=q₁*q₂…qₘ
bo'lsin,bunda q₁,q₂,…,qₘ -tub sonlar.U holda ,tub sonlarning yuqoridagi xossasiga asosan q₁,q₂,..,qₘ ko'paytuvchilarning biri ,masalan,q₁ p ga bo'linishi kerak,ammo q₁ tub son bo'lgani uchun q₁=p bo'lishi kerak.
Endi yagonalikni isbotlaymiz.
I.⃒n⃒=1 bo'lsa,u holda n= da 1=1 va -1=-1 ,yani 1 va-1 sonlar uchun yoyilmaning yagonaligi o'rinli bo'ladi.
II. Isbotlanayotgan xossa ⃒m⃒<⃒n⃒ shartni qanoatlantiruvchi barcha m butun sonlar uchun ham o'rinli bo'lishini ko'rsatamiz.
N son quyidagicha 2 xil usulda tub sonlar ko'paytmasiga yoyilgan bo'lsin,yani
n=p₁*p₂*…pₖ=q₁*q₂*…..
pₖ tub son q₁,q₂,…, tub sonlar ichida uchraydi (ishorasi qarama-qarshi ham bo'lishi mumkin).
Agar pₖ tub son q₁,q₂,…,qₗ sonlarning birortasiga teng bo'lmasa,yani pₖ ,i=1, bo'lsa, u holda pₖ tub son q₁,q₂,… sonlarning har biri bilan ,demak ularning ko'paytmasi n= q₁*q₂*….. bilan ham tub bo'ladi,bunday bo'lishi mumkin emas,chunki pₖ tub son n ning bajaruvchisidir.
Shunday qilib , pₖ (i=1, ) tub sonlarning birortasiga teng.
pₖ= deb hisoblaylik,aks holda larning o'rinlarini ,zarur bo'lsa ishoralarini o'zgartirib ,bunga erishish mumkin.Shunday qilib
n=p₁*p₂*…pₖ=q₁*q₂*….. *pₖ
ifoda hosil bo'ladi,bundan
m= = p₁*p₂*…pₖ₋₁= q₁*q₂*…..
Ammo ⃒m⃒<⃒n⃒ va induktiv farazga ko'ra m uchun teoremaning tasdig'i o'rinli,yani k-1= -1, p₁,p₂,…pₖ₋₁ va q₁,q₂,….. ketma-ketliklar ,ishoragacha aniqlik bilan,bir hil tub sonlardan tuzilgan bo'ladi va mos sonlar har ikki yoyilmada faqat bir martadan qatnashadi, pₖ= bo'lganidan ,shundan tenglik
p₁,p₂,…pₖ₋₁pₖ va q₁,q₂,….. ketma-ketliklar uchun ham o'rinli bo'ladi.Teorema isbotlandi.
4-§ Ayniyatlarni isbotlash va yig'indi hamda ko'paytmalarni hisoblashda
matematik induksiya
32-misol.Birinchi n ta toq natural sonlarning yig'indisini toping.
Yechilishi izlanyotgan yig'indi Sₙ bo'lsin:
Sₙ=1+2+…….+(2n-1)
n ga ketma-ket 1,2,3,4,5,6,7,…… berib Sₙ ning mos qiymatlarini topaylik:
S₁=1;