Matematik induksiya metodi va uning bazi tadbiqlari

Matematik induksiya metodi
Xususiy hollar cheksiz ko'p bo'lgani uchun to'la induksiyani qo'llash imkoniyatiga ega emasmiz,xususiy hollarga asoslanib chiqarilgan tasdiq esa xato bo'lishini mumkin.
Bu savolga,ba'zi hollarda ,matematik induksiya metodi deb ataluvchi alohida mulohaza yordamida javob beriladi.
Induksiya yordamida biror A(n) gipoteza bayon etilgan bo'lib ,bu mulohazaning ixtiyoriy n natural son uchun rostligini isbotlash kerak bo'lsin hamda A(n) mulohazaning to'g'ligini barcha n lar uchun bevosita tekshirib ko'rishning iloji bo'lmasin.
A(n) mulohaza ,matematik induksiya prinsipiga asosan,quyidagicha isbotlanadi;
Bu tasdiqning to'g'riligi ,avvalo ,n=1 uchun tekshiriladi .So'ngra aytilgan tasdiqni n=k uchun rost bo'lsin deb faraz qilib ,uning rostligi n=k+1 uchun isbotlanadi.Shundan so'ng ,A(n) tasdiq barcha n(n€N ) lar uchun isbotlangan hisoblanadi.
Bularga asosan agar A(n) tasdiq n=1 da rost bo'lsa, u navbatdagi n=1+1=2 son uchun ham rost bo'ladi.Tasdiqning n=2 uchun rostligidan uning n=2+1=3 uchun rostligi kelib chiqadi.
Bundan esa tasdiqning ,o'z navbatida ,n=4 uchun rostligi kelib chiqadi va hakozo. Shu yo'sinda ,ixtiyoriy n natural songacha yetib boramiz.Demak,A(n) tasdiq ixtiyoriy n uchun o'rinlidir.
Aytilganlarni umumlashtirib ,ushbu umumiy prinsipni ifodalaylik;

1. 
   n=1 da A(n)mulohazaning rostligi tekshiriladi;
   
2. 
   n=k da A(n) mulohaza rost bo'lsin deb faraz qilib ,n=k+1 uchun A(n) mulohazaning rostligi,ya'ni A(k) A(k+1) isbotlanadi.Shundan so'ng , A(n)mulohaza barcha n lar uchun rost deb xulosa qilinadi.
   

11-misol Yuqoridagi prinsipga asoslanib ,ixtiyoriy n natural son uchun ushbu tenglikni isbotlang:
1+2+3+………+n=n(n+2)/2
Isboti.
Bu yerda va bundan keyin misoldagi tasdiqni A(n) deb belgilaymiz.
I.n=1 bo'lganda 1=1(1+1)/2, demak,A(1) to'g'ri .
II. Ixtiyoriy k natural son uchun A(k) ning to'g'ligidan A(k+1) ning kelib chiqishini isbotlaymiz.
1+2+3+…….+k=k(k+1)/2 (2.2)
to'g'ri bo'lsin.(2.2) munosabatdan foydalansak :
1+2+3+….+k+k+1=k(k+1)/2+k+1=(k+1)(k(k+1)+1)/2
hosil bo'ladi .Bu esa A(k+1) ning o'zidir.
Matematik induksiya prinsipiga asoslanib (2.1) dan iborat tasdiq har qanday n natural son uchun to'g'ri deb xulosa qilamiz.
Matematik induksiya prinsipiga asoslangan isbotlar isbotlashning matematik induksiya metodi deyiladi.
Matematik induksiya metodiga asoslanib biror tasdiqni isbotlashda yuqorida ko'rsatilgan I va II punktlarning har birini tekshirish juda muhimdir.Agar ulardan birortasini hisobga olmasak,chiqarilgan xulosa to'g'ri qolishi mumkin.Masalan ,3-6 misollarda induksiya prinsipining faqat I qismiga asoslanib xulosalar chiqarildi ,natijada chiqarilgan xulosalar noto'g'ri ekani aniqlandi .Xuddi shuningdek ,I punktni isbotlamasdan faqat II punktga asoslanib xulosa chiqarsak ,chiqarilgan xulosa xato bo'lishi mumkin.
12-misol.Har qanday natural son o'zidan keyin keluvchi natural songa teng.
Isboti .
k=k+1 (2.3)
bo'lsin deb faraz qilaylik.U holda
k+1=k+2 (2.4)
hosil bo'ladi.Haqiqatan ham (2.3) ning ikkala tomoniga 1 ni qo'shsak ,(2.4) kelib chiqadi.Bundan ,agar tasdiq n=k uchun rost bo'lsa,u holda u n=k+1 uchun ham rost ekani kelib chiqadi.
Natija .Barcha natural sonlar o'zaro teng.Natijaning xatoligi o'z-o'zidan ravshan .Bu xato qayerdan kelib chiqdi?
Xato shunday iboratki ,matematik induksiya prinsipini qo'llash uchun zarur bo'lgan I punkt isbotlanmadi,faqat II punkt isbotlandi ,xolos.
I punkt induksiya bazasi (asosi) deyiladi.II punktda esa induksiya bazasi istalgan n natural son uchun kengaytiriladi.
Agar I punkt tekshirilmay,faqat II ning o'zi isbotlansa, u holda induksiya bajarish uchun asos yaratilmaydi,shu sababli isbotlangan narsaning manosi bo'lmaydi,chunki kengaytirishi kerak bo'lgan bazaning o'zi yo'q.
Agar II punkt isbotlanmay faqat I punktning o'zigina isbotlansa (3-6-misollar), u holda induksiya bajarish uchun baza yaratilgan bo'lsada ,bu
bazani istalgan n son uchun kengaytirish qoidasi yo'q.
Matematik induksiya metodi bilan isbotlash jarayonida quyidagi hollar bo'lishi mumkin.(11-misol)
Agar induksiya yordamida bayon etilgan A(n) mulohaza no'g'ri bo'lsa , uning xatoligi II puktni isobotlash jarayonida osongina aniqlash mumkin.
13-misol Ushbu Sₙ=1+2+3+…….+n yig'indi uchun
Sₙ=n(n²+1)/2 (2.5)
Tenglik to'g'ri degan gipoteza aytilgan bo'lsin.n=1 bo'lganda S₁=1=1(1²+1)/2,demak ,A(1) to'g'ri .(2.5) formula n=k uchun
Sₖ=k(k²+1)/2 (2.6)
yani A(k) to'g'ri bo'lsin,u holda A(k+1) ning ,yani
Sₖ₊₁=(k+1)((k²+1)=1)/2 (2.7)
Formulaning to'g'ri bo'lishini isbotlashga harakat qilaylik.(2.6) ni e'tiborga olsak ,
Sₖ₊₁=Sₖ+(k+1)=k(k²+1)/2+k+1=(k³+3k+2)/2. (2.8)
(k+1)[(k+1)²+1]=k³+3k²+4k+2≠k³+3k+2 ekanini e'tiborga olsak ,hosil bo'lgan (2.8)ifoda biz isbotlamoqchi bo'lgan (2.7)dan farqli ekanini ko'ramiz.
Demak ,A(k)≠˃A(k+1),shu sababli (2.5)tasdiq xato .Yuqorida bayon etilgan matematik induksiya prinsipi n dan n+1 ga mulohaza yurutish usuli deyiladi.Bu xol matematik induksiya metodining oson holidir.