Matematik induksiya metodi va uning bazi tadbiqlari

Umumlashgan matematik induksiya metodi
Induktiv mulohazalar yordamida bayon etilgan A(n) tasdiq ,ko'pincha ,barcha natural sonlar uchun o'rinli bo'lmasdan ,biror p(p˃1) natural sondan boshlab o'rinli bo'lishi mumkin.
Bu holda ham matematik induksiya metodi qo'llanaveradi,lekin I punkt biroz o'zgaradi ,yani A(n)tasdiq barcha n (n ≥ p ˃ 1) natural sonlarda o'rinli ekanini ko'rsatish mumkin .
I-a .n=p da A(n) mulohazaning rostligi tekshiradi.
II.n=k (k≥p) da A(k) rost bo'lsin deb faraz qilib,A(k+1) ning rostligini, yani A(k)=>A(k+1) munosabat isbotlanadi.
Shundan so'ng ,A(n) mulohaza ixtiyoriy natural n(n≥p) son uchun rost deb xulosa qilinadi.
14-misol .Ixtiyoriy n≥3 natural son uchun
2ⁿ˃2n+1
tengsizlik o'rinli bo'lishini isbotlang .
Isbot .I-a .A(1),A(2) lar o'rinli emasligi (3.1) dan ko'rinib turibdi .n=3 bo'lsin,u holda 2³˃[2*2+1] ya'ni A (3) o'rinli .
II.n=k (k≥3 )da
2ᵏ˃2k+1 (3.2)
o'rinli bo'lsin,yani A(k) bajarilsin.n=k+1 da
2ᵏ⁺¹˃2(k+1)+1 (3.3)
tengsizlik bajarilishini ,yani A(k) =>A(k+1)
munabatni isboladlaymiz.
Shu mahsadda (3.2) ning ikkala tomonini 2 ga ko'paytiramiz va (3.3) hosil qilamiz :
2ᵏ*2>(2k+1)*2˃2(k+1)+1.
Demak ,A(k)=˃A(k+1),bundan esa (3.1)A(n) tasdiqning istalgan n(n≥3) natural son uchun to'g'riligi kelib chiqadi.
Bazi masalalarni xal etishda II punktning isboti A(n) tasdiqning faqat n=k uchun emas ,balki n=k-1 da ham o'rinli bo'lishiga asoslanadi .Bu holda matematik induksiya metodining I punkti n ning ketma-ket ikkita qiymati uchun tekshirilishi kerak bo'ladi.
Ayrim misollarni yechishda esa isbotning II punkti talab qilinayotgan mulohazaning n dan kichik bo'lgan barcha natural k sonlar uchun to'g'ri bo'lishiga asoslanadi.Buni misolda ko'raylik .
15-misol .Agar V₀=2,V₁=3 va har qanday k natural son uchun
Vₖ₊₁=3Vₖ-2Vₖ₋₁ (3.4)
Munasabat o'rinli bo'lsa ,
Vₙ=2ⁿ+1 (3.5)
ekanini isbotlang .
Isboti: (3.5) ni A(n) deb belgilaylik.
I.A(0) va A(1) shaartga asosan o'rinli.
II.Faraz qilaylik A(k-1),A(k) lar o'rinli bo'lsin, yani
Vₖ₋₁=2ᵏ⁻¹+1, Vₖ=2ᵏ+1
tengliklar bajarilsin .
{A(k-1),A(k)}=>A(k+1) bo'lishini bo'lishini isbotlaymiz Buning uchun (3.4) formulada A(k-1) va A(k) larni e'tiborga olamiz,u holda
Vₖ₊₁=3 (2ᵏ+1)-2 (2ᵏ⁻¹+1)=2ᵏ⁺¹+1.
tengliklar bajarilsin.
{A(k-1),A(k)}=>A(k+1) bo'lishini isbotlaymiz.Buning uchun (3.4) formulada A(k-1) va A(k) larni e'tiborga ,u holda
Vₖ₊₁=3(2ᵏ+1)-2(2ᵏ⁻¹+1)=2ᵏ⁺¹+1
Oxirgi munosabat A(k+1) tasdiqdan iborat.Demak,A(n) tasdiq iborat .Demak , A(n) tasdiq istalgan n natural son uchun o'rinli .
Matematik induksiya prinsipining yuqorida bayon etilgan barcha hollarida mulohazalar n dan n+1 ga olib boriladi. Bu hollar to'g'ri induksiya deyiladi.
Ba'zi masalalarni hal etishda faqat to'g'ri induksiyani qo'llash orqali maqsadga to'la erishib bo'lmaydi.Bunday xollarda teskari induksiya deb ataluvchi n dan n-1 ga mulohaza yurutish orqali tegishli masalani mufassal hal etish mumkin bo'ladi. Aytilganlarni ushbu teoremani isbotida yaqqol ko'rish mumkin.
16-misol.n ta sonning o'rta arifmetigi va o'rta geometrigi haqida teorema .Ixtiyoriy n ta manfiy bo'lmagan a₁ ,a₂,…….,aₙ sonlarning o'rta arifmetigi shu sonlarning o'rta geometrigidan kichik emas,yani
(a₁+a₂+…….+aₙ)/n≥ (3.6)
a₁=a₂=………=aₙ bo'lganda va faqat shu holdagina texnik o'rinli bo'ladi.
(3.6) Koshi tengsizligi deyiladi, uni Aₙ(n) deylik.
Isboti .I A(1) o'rinli ,chunki a₁=a₂ bo'ladi.A(2) quyidagicha bo'ladi:
≤(a₁+a₂)/2 (3.7)
(3.7) da quyidagicha shakl almashtiramiz:
a₁-2 +a₂≥0,
( -2 +( )²≥0
( - )≥0
Oxirgi tengsizlik hamma vaqt o'rinli ,demak , unga teng kuchli A(2) munosabat ham har doim bajariladi .a₁=a₂ bo'lgan tenglik hosil bo'ladi.
II.A(k) o'rinli bo'lsin ,yani n=k uchun
a₁+a₂+……..aₖ)/k (3.8)
Tengsizlik o'rinli bo'lib,a₁=a₂=……=aₖ bo'lgandagina tenglik bajarilsin deb faraz qilaylik.
A(k)=>A(2k) o'rinli bo'lishini ko'rsatamiz.
a₁,a₂,…….aₖ,aₖ₊₁,….,a₂ₖ manfiy bo'lmagan sonlarni olaylik va ularni ikkita a₁,a₂,….aₖ va aₖ₊₁,aₖ₊₂,…….,a₂ₖ gruppalarga ajrataylik.
U holda (3.7) va (3.8) larga asosan :
= =
= =
Shuni isbotlash kerak edi.Barcha tengsizliklarni tenglik bilan almashtirish mumkin bo'lganda ,ya'ni a₁=…….=aₖ va aₖ₊₁=……=a₂ₖ (biz bu sonlar uchun (3.8) dan foydalandik),hamda (a₁+……+aₖ)/k=(aₖ₊₁+.........+a₂ₖ)/k bo'lgandagina tenglik hosil bo'ladi.Bundan esa a₁=…..=aₖ=aₖ₊₁=……=a₂ₖ kelib chiqadi.
Hozirgi isbotimizda (3.6) tengsizlik k ta son uchun o'rinli bo'lishidan 2k ta son uchun o'rinli bo'lishini ko'rsatdik.Olingan sonlarning soni k ga karrali bo'lmagan hollar uchun ,hozircha (3.6) tengsizlik isbotlangani yo'q.Bu kamchilikni yo'qotish uchun teskari induksiya metodidan foydalanamiz,yani n=k uchun o'rinli bo'lgan (3.8) tengsizlikdan n=k-1 uchun o'rinli bo'lgan ushbu
≤(a₁+a₂+…..aₖ₋₁)/(k-1) (3.9)
Tengsizlikni keltirib chiqaramiz,boshqacha aytganda ,A(k)=>A(k-1) ni isbotlaymiz.
a₁,a₂…..,aₖ₋₁ sonlar berilgan bo'lsin.

aₖ=

deb faraz qilamiz va (3.8) tengsizlikdan foydalanamiz :


≤ = ₖ.
ya'ni ≤ = tengsizlik hosil bo'ladi. Bundan
≤ aₖ
yoki
a₁a₂……aₖ₋₁≤ ,
va nihoyat
≤ aₖ=
tengsizlik hosil bo'ladi bu esa , Bu tengsizlik n=k bo'lgan ( 3.8) tengsizlikka keltirilgani uchun a₁=a₂=….=aₖ₋₁=aₖ bo'lgandagina tenglikka aylanadi.
(3.6) tengsizlik ,tenglik o'rinli bo'ladigan holi bilan birgalikda to'la isbotlandi.
Endi matematikaning turli bo'limlarida matematik induksiya matematik induksiya metodining ishlatishiga doir misollar ko'ramiz.
Matematik induksiya metodi induktik farazlar orqali aniqlangan gipotezalarning chin yoki yolg'on ekanini aniqlashda yakunlovchi bosqichdir.