Matematik induksiya metod

II.Asosiy qism.

1 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, ya’ni A(n) tasdiq barcha n(n p>1) natural sonlarda o’rinli ekanini ko’rsatish uchun:

I. n = p da A (n) mulohazaning rostligi tekshiriladi.

II. n = k(k p) da A(k) rost bo’lsin deb faraz qilib, A(k+1) ning rostligi ya’ni A(k) A(k+1) munosabat isbotlanadi.

Shundan so’ng, A(n) mulohaza ixtiyoriy natural n(n p) son uchun rost degan xulosa qilinadi.

1-misol. Ixtiyoriy n 3 natural son uchun

2 ⁿ> 2n+1 (1)

tengsizlik o’rinli bo’lishini isbotlang.

Isbot. I. A(1), A(2) lar o’rinli emasligi (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^k >2k+1 (2)

o’rinli bo’lsin, ya’ni A(k) bajarilsin. n=k+1 da

2^k+1 >2(k+1)+1 (3)

tengsizlik bajarilishini, ya’ni A(k) A(k+1) munosabatni isbotlaymiz.

Shu maqsadda (2) ning ikkala tomonini 2 ga ko’paytiramiz va (3)ni hosil qilamiz:

2^{k .}2>(2k+1)^.2>2^.(k+1)+1.

Demak, A(k) A(k+1), bundan esa (1) A(n) tasdiqning istalgan n(n 3) natural son uchun to’g’riligi kelib chiqadi.

Ba’zi masalalarni hal 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 metodikining 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.

2-misol. Agar V₀=2,V₁=3 va har qanday k natural uchun

V_k+1=3V_k-2V_k-1 (4)

munosabat o’rinli bo’lsa,

V_n=2ⁿ+1 (5)

ekanini isbotlang.

Isbot. (5) ni A(n)deb belgilaylik.

I. A(0) va A(1) shartga asosan o’rinli.

II. Faraz qilaylik A(k-1), A(k)lar o’rinli bo’lsin, ya’ni

V_k-1=2^k-1+1,V_k+2^k+1

tengliklar bajarilsin.

{A(k-1), A(k)} A(k+1) bo’lishini isbotlaymiz. Buning uchun (4) formulada A(k-1) va A(k) larni e’tiborga olamiz, u holda

V_k+1=3^.(2^k+1)-2^.(2^k-1+1)=2^k+1+1.

Oxirgi munosabat A(k+1) tasdiqdan iborat. Demak, A(n) tasdiq istalgan n natural son uchun o’rinli. Matematik induksiya prinspining 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 hollarda teskari induksiya deb ataluvchi n dan n-1 ga mulohaza yuritish orqali tegishli masalani mufassal hal etish mumkin bo’ladi.