Berdaq nomidagi qoraqalpoq davlat universiteti fakulteti

II BOB. Matematik induksiya printsipi.

Agar A jumlasi (n) natural songa qarab n, uchun to'g'ri n=1 va u uchun haqiqat ekanligidann=k(qaerdak-har qanday natural son), bundan keyingi son uchun ham to‘g‘ri ekanligi kelib chiqadin=k+1, keyin A farazi (n) har qanday natural son uchun to'g'rin.

Bir qator hollarda, ma'lum bir fikrning to'g'riligini barcha natural sonlar uchun emas, balki faqat n>p uchun isbotlash kerak bo'lishi mumkin, bu erda p - qat'iy belgilangan natural son. Bunda matematik induksiya tamoyili quyidagicha tuzilgan. Agar A jumlasi (n) uchun to'g'rin=pva agar A(k) Þ LEKIN(k+1)har kim uchunk>p,keyin A jumlasi(n)har kim uchun to'g'rin>p.

Matematik induksiya usuli bilan isbotlash quyidagicha amalga oshiriladi. Birinchidan, isbotlanishi kerak bo'lgan tasdiq n=1 uchun tekshiriladi, ya'ni. A(1) gapning haqiqati aniqlanadi. Isbotning bu qismi induksiya asosi deb ataladi. Buning ortidan induksiya bosqichi deb ataladigan dalilning bir qismi keladi. Bu qismda n=k+1 uchun mulohazaning to'g'riligi n=k uchun (induktiv faraz) to'g'ri degan faraz ostida isbotlanadi, ya'ni. A(k)ÞA(k+1) ekanligini isbotlang.

MISOL 1

1+3+5+…+(2n-1)=n 2 ekanligini isbotlang.

Yechish: 1) Bizda n=1=1 2 . Binobarin,

bayonot n=1 uchun to'g'ri, ya'ni. A (1) to'g'ri.

2) A(k)ÞA(k+1) ekanligini isbotlaymiz.

k har qanday natural son bo'lsin va n=k uchun bayonot to'g'ri bo'lsin, ya'ni.

1+3+5+…+(2k-1)=k 2 .

Isbot qilaylikki, u holda tasdiq keyingi natural son n=k+1 uchun ham to'g'ri, ya'ni. nima

1+3+5+…+(2k+1)=(k+1) 2 .

Haqiqatdan ham,

1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 .

Shunday qilib, A(k)ÞA(k+1). Matematik induksiya tamoyiliga asoslanib, A(n) faraz har qanday nnN uchun to‘g‘ri, degan xulosaga kelamiz.

2-MISOL

Buni isbotlang

1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), bunda x¹1

Yechish: 1) n=1 bo‘lganda olamiz

1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1

shuning uchun n=1 uchun formula to'g'ri; A (1) to'g'ri.

2) k har qanday natural son bo‘lsin va n=k uchun formula to‘g‘ri bo‘lsin, ya’ni.

1 + x + x 2 + x 3 + ... + x k \u003d (x k + 1 -1) / (x-1).

Keling, tenglikni isbotlaylik

1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1).

Haqiqatdan ham

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).

Shunday qilib, A(k)ÞA(k+1). Matematik induksiya tamoyiliga asoslanib, formula har qanday natural n soni uchun to‘g‘ri degan xulosaga kelamiz.

MISOL 3

Qavariq n-burchakning diagonallari soni n(n-3)/2 ekanligini isbotlang.

Yechish: 1) n=3 bo‘lganda gap to‘g‘ri bo‘ladi

Va 3 to'g'ri, chunki uchburchakda

 A 3 =3(3-3)/2=0 diagonal;

A 2 A(3) to'g'ri.

2) Faraz qilaylik, har qandayida

qavariq k-gon bor-

A 1 sya A k \u003d k (k-3) / 2 diagonal.

A k Buni qavariqda isbotlaylik

(k+1)-gon raqami

diagonallar A k+1 =(k+1)(k-2)/2.

A 1 A 2 A 3 …A k A k+1 -qavariq (k+1)-burchak bo‘lsin. Unda A 1 A k diagonali chizamiz. Bu (k + 1)-gon diagonallarining umumiy sonini hisoblash uchun siz k-gondagi diagonallar sonini hisoblashingiz kerak A 1 A 2 ...A k, natijada paydo bo'lgan songa k-2 qo'shing, ya'ni. (k+1)-burchakning A k+1 tepasidan keladigan diagonallari soni va bundan tashqari, A 1 A k diagonalini hisobga olish kerak.

Shunday qilib,

A( k+1) =A( k) +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.

Shunday qilib, A(k)ÞA(k+1). Matematik induksiya printsipi tufayli bu bayonot har qanday qavariq n-gon uchun to'g'ri bo'ladi.

MISOL 4

Har qanday n gap uchun to'g'ri ekanligini isbotlang:

1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6.

Yechish: 1) U holda n=1 bo‘lsin

X 1 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1.

Demak, n=1 uchun gap to'g'ri.

2) n=k deb faraz qilaylik

X k \u003d k 2 \u003d k (k + 1) (2k + 1) / 6.

3) n=k+1 uchun ushbu bayonotni ko'rib chiqing

Xk+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.

Biz n=k+1 uchun tenglikning to‘g‘riligini isbotladik, shuning uchun matematik induksiya usuli tufayli bu gap har qanday natural n uchun to‘g‘ri bo‘ladi.

5-Misol
Har qanday natural n uchun tenglik to‘g‘ri ekanligini isbotlang:

1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4.

Yechish: 1) n=1 bo‘lsin.

U holda X 1 =1 3 =1 2 (1+1) 2 /4=1.

Biz n=1 uchun bayonot to'g'ri ekanligini ko'ramiz.

Teorema 1. Ushbu bayonot n =1 uchun to'g'ri.

Teorema 2. Bu gap n =k +1 uchun to'g'ri bo'ladi, agar u n=k uchun to'g'ri bo'lsa, bu erda k - ixtiyoriy natural son.

Agar bu ikkala teorema isbotlangan bo'lsa, matematik induksiya printsipiga asoslanib, bayonot har qanday teorema uchun to'g'ri bo'ladi.

tabiiy n.

Shuni ta'kidlash kerakki, matematik induksiya bilan isbotlash, albatta, 1 va 2-teoremalarni ham isbotlashni talab qiladi. 2-teoremani e'tiborsiz qoldirish noto'g'ri xulosalarga olib keladi (1-2-misollar). Keling, 1-teoremani isbotlash qanchalik zarurligini misol orqali ko'rsatamiz.

3-misol. "Teorema": har bir natural son undan keyingi natural songa teng.

Isbotlash matematik induksiya usuli bilan amalga oshiriladi.

Faraz qilaylik, k =k +1 (1).

k +1=k +2 (2) ekanligini isbotlaylik. Buning uchun "tenglik" (1) ning har bir qismiga 1 qo'shing.Biz "tenglik" (2) olamiz. Ma’lum bo‘lishicha, agar n =k uchun gap to‘g‘ri bo‘lsa, n =k +1 uchun ham to‘g‘ri bo‘ladi. va hokazo.

“Teorema”dan aniq “natija”: barcha natural sonlar tengdir.

Xato shundan iboratki, matematik induksiya tamoyilini qo‘llash uchun zarur bo‘lgan 1-teorema isbotlanmagan va haqiqat emas, faqat ikkinchi teorema isbotlangan.

1 va 2 teoremalar alohida ahamiyatga ega.

1-teorema induksiya uchun asos yaratadi. 2-teorema ushbu bazani cheksiz avtomatik ravishda kengaytirish huquqini, ushbu aniq holatdan keyingisiga, n dan n + 1 ga o'tish huquqini beradi.

Agar 1-teorema isbotlanmagan bo'lsa-da, lekin 2-teorema isbotlangan bo'lsa, demak, induksiyani o'tkazish uchun asos yaratilmagan va keyin 2-teoremani qo'llashning ma'nosi yo'q, chunki aslida kengaytirish uchun hech narsa yo'q. .

Agar 2-teorema isbotlanmagan bo'lsa va faqat 1-teorema isbotlangan bo'lsa, u holda induksiyani o'tkazish uchun asos yaratilgan bo'lsa-da, bu asosni kengaytirish huquqi yo'q.

Izohlar.

Ba'zan isbotning ikkinchi qismi faqat n =k uchun emas, balki n =k -1 uchun ham bayonotning haqiqiyligiga asoslanadi. Bunday holda, birinchi qismdagi bayonot n ning keyingi ikkita qiymati uchun sinovdan o'tkazilishi kerak.

Ba'zida gap har qanday natural n uchun emas, balki n > m uchun isbotlanadi, bu erda m qandaydir butun sondir. Bunday holda, isbotning birinchi qismida tasdiq n = m +1 uchun, agar kerak bo'lsa, n ning bir nechta keyingi qiymatlari uchun tekshiriladi.

Aytilganlarni umumlashtirib, bizda shunday bo'ladi: matematik induksiya usuli umumiy qonunni izlashda bu holatda paydo bo'ladigan gipotezalarni sinab ko'rish, yolg'onni rad etish va haqiqatni tasdiqlash imkonini beradi.

Har bir inson individual kuzatishlar va tajribalar natijalarini umumlashtirish jarayonlarining rolini biladi (ya'ni induksiya) empirik, eksperimental fanlar. Boshqa tomondan, matematika uzoq vaqtdan beri sof deduktiv usullarni amalga oshirishning klassik namunasi hisoblanadi, chunki har doim aniq yoki bilvosita barcha matematik takliflar (boshlang'ich sifatida qabul qilinganlardan tashqari - aksiomalar) isbotlangan va maxsus qo'llanmalar mavjud deb taxmin qilinadi. bu mulohazalar umumiy holatlar uchun mos dalillardan (chegirma) olingan.

Gipoteza bo'yicha induksiya (yo'l-yo'riq) matematikada juda muhim, ammo sof evristik rol o'ynaydi: bu yechim qanday bo'lishi kerakligini taxmin qilish imkonini beradi. Ammo matematik takliflar faqat deduktiv tarzda o'rnatiladi. Matematik induksiya usuli esa sof deduktiv isbot usulidir. Darhaqiqat, bu usul bilan amalga oshirilgan isbot ikki qismdan iborat:

"asos" deb ataladigan narsa - bir (yoki bir nechta) natural sonlar uchun kerakli jumlaning deduktiv isboti;

umumiy gapning deduktiv isbotidan iborat induktiv qadam. Teorema barcha natural sonlar uchun aniq isbotlangan. Isbotlangan asosdan, masalan, 0 raqami uchun, biz induksiya bosqichida 1 raqamiga dalil olamiz, keyin xuddi shu tarzda 2 uchun, 3 uchun ... - va shuning uchun bayonotni oqlash mumkin. har qanday natural son.

Boshqacha qilib aytganda, "matematik induksiya" nomi bu usulning bizning ongimizda oddiygina an'anaviy induktiv fikrlash bilan bog'langanligi bilan bog'liq (oxir-oqibat, asos faqat ma'lum bir holat uchun isbotlangan); induktiv qadam, tabiiy va ijtimoiy fanlar tajribasiga asoslangan induktiv fikrlashning ishonchlilik mezonlaridan farqli o'laroq, hech qanday alohida asosga muhtoj bo'lmagan va deduktiv fikrlashning qat'iy qonunlariga muvofiq isbotlangan umumiy bayonotdir. Shuning uchun matematik induktsiya deduktiv, to'liq ishonchli isbot usuli bo'lgani uchun "to'liq" yoki "mukammal" deb ataladi.

Muammoni hal qilishga misollar

Algebrada induksiya

Algebraik masalalarning bir nechta misollarini, shuningdek, matematik induksiya usuli yordamida yechish mumkin bo'lgan turli xil tengsizliklarni isbotlashni ko'rib chiqing.
Vazifa 1. Yig‘indining formulasini toping va isbotlang.

LEKIN( n )= 2 * 1 2 + 3* 2 2 + …..+(n +1) n 2 .

Yechim.

1. A(n) yig‘indisi uchun ifodani o‘zgartiramiz:

A(n)= 2 * 1 2 + 3 * 2 2 + ….+ (n+1) n 2 = (1+1) 1 2 + (2+1) 2 2 + …. + (n+1) n 2 = =1 * 1 2 + 2 * 2 2 + …+n* n 2 + 1 2 + 2 2 +… +n 2 =1 3 + 2 3 +… +n 3 +1 2 + 2 2 +… +n 2 = V(n) + C(n), bunda B(n) = 1 3 + 2 3 + …..+ n 3 , C(n)= 1 2 + 2 2 + …+ n 2.

2. C (n) va B (n) yig'indilarini ko'rib chiqing.

a) C( n ) = 1 2 + 2 2 +…+ n 2 . Matematik induksiya usulida tez-tez uchraydigan masalalardan biri bu har qanday natural n uchun tenglikni isbotlashdir.

1 2 + 2 2 +…+ n 2 = (1)

Faraz qilaylik (1) hamma n uchun to‘g‘ri N.

b ) B(n) = 1 3 + 2 3 + …..+ n 3 . Keling, B (n) qiymatlari n ga qarab qanday o'zgarishini kuzatamiz.

B(1) = 1 3 = 1 .

B(2) = 1 3 + 2 3 = 9 = 3 2 = (1 + 2) 2

B(3) = 1 3 + 2 3 + 3 3 = 36 =

Shunday qilib, shunday deb taxmin qilish mumkin
B (n) = (1 + 2 + ….+ n) 2 =
(2)

c) Natijada A(n) yig‘indiga erishamiz

LEKIN( n ) ==

= (*)

3. Olingan formulani (*) matematik induksiya usuli bilan isbotlaymiz.
a) n = 1 uchun tenglikni (*) tekshiring.
A(1) = 2 A =2,
Shubhasiz, (*) formula n = 1 uchun to'g'ri.

b) faraz qilaylik (*) formula n=k uchun to'g'ri bo'lsin, bu Yerda k= N, ya'ni tenglik.

A(k)=

Farazga asoslanib, n =k +1 uchun formulaning to'g'riligini isbotlaymiz. Haqiqatan ham,

A(k+1)=

(*) formula n =1 uchun to'g'ri bo'lgani uchun va u qandaydir natural k uchun to'g'ri degan farazdan kelib chiqadiki, u n =k +1 uchun to'g'ri bo'ladi, matematik induksiya tamoyiliga asoslanib, shunday xulosaga kelamiz: tenglik har qanday tabiiy n uchun amal qiladi.

Xulosa

Xususan, matematik induksiya usulini o‘rganib, matematikaning ushbu yo‘nalishi bo‘yicha bilimlarimni oshirdim, shuningdek, ilgari qo‘limdan kelmagan masalalarni yechish usullarini ham o‘rgandim.

Asosan, bu mantiqiy va qiziqarli vazifalar edi, ya'ni. faqat matematikaning o'ziga fan sifatida qiziqishni oshiradiganlar. Bunday muammolarni hal qilish qiziqarli faoliyatga aylanadi va ko'proq qiziquvchan odamlarni matematik labirintlarga jalb qilishi mumkin. Menimcha, bu har qanday fanning asosidir.

Matematik induksiya usulini o‘rganishni davom ettirar ekanman, uni nafaqat matematikada, balki fizika, kimyo va hayotning o‘ziga tegishli masalalarni yechishda ham qo‘llashni o‘rganishga harakat qilaman.