Matematik induksiya metod

2 Natural sonlar arifmetikasi va matematik induksiya metodi.

1-misol. n N uchun

(n-1)³+n³+(n+1)³ (1)

ifoda 9 ga bo’lishini ko’rsating.

Isboti. I.n=1 da 0³+1³+2³=9 – 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índi 9 ga karrali bo’lishini ko’rsatamiz:

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, (1) ifoda 9 ga karrali.

2-misol. n N uchun 3^{3 n+2}+2⁴ⁿ⁺¹ yigíndining 11 ga bo’linishini isbotlang.

Isboti.I.n=1 da 3³ +2 =275=11^.25 tasdiq o’rinli.

II.n=k da 3^3k+2+2^4k+111 ga karrali bo’lsin deb faraz qilamiz va n=k+1 bo’lganda 3^3k+2+2^4k+1ning 11 ga bo’linishini isbotlaymiz. So’nggi yig’indida shakl almashtirishlar bajaramiz: 3^3(k+1)+2+2^4(k+1)+1=3^3k+5+2^4k+5=27^.3^3k+2+16^.2^4k+1=11^.3^3k+2+16^.(3^3k+2+2^4k+1),

natijada qo’shiluvchilar 11 ga bo’linadigan yigíndini hosil qilamiz.

3-misol. n N uchun xⁿ –yⁿ (x y) ayirma x-y ga qoldiqsiz bo’linishini ko’rsating.

Isboti. I.A(1) o’rinli, chunki n=1 da x¹-y¹=x-y.

II. A(k) A(k+1) ni isbotlaymiz, ya’ni n=k da x^k-y^k ga qoldiqsiz bo’linsin deb faraz qilib, n=k+1 bo’lganda x^k+1-y ^k+1 ayirma x-y ga karrali bo’lishini isbotlaymiz.

x^k+1-y ^k+1 ayirmaning shaklini quyidagicha o’zgartiramiz:

x^k+1-y ^k+1 = x^k+1 -xy^k+xy^k –y^k+1=x(x^k-y^k)+y^k(x-y).

Hosil bo’lgan yig’indi x-y ga karrali, chunki x^k-y^k farazga ko’ra x – y ga bo’linadi, ikkinchi qo’shiluvchida esa x – y ifoda bor, ya’ni A(k+1) o’rinli.

4-misol. 11¹⁰ⁿ – 1 ikkihad 10 ning qanday darajasiga bo’linishini aniqlang.

Yechilishi. Induksiya yuritamiz, ya’ni n ga turli qiymatlar berib yuqoridagi ayirmaning xarakterini o’rganamiz.

n=1 bo’lsin, u holda

11¹⁰ -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, 11¹⁰ - 1 ayirma 10² ga bo’linadi.

n=2 bo’lsin, u holda

11¹⁰ - 1=(11¹⁰)¹⁰ - 1=(11¹⁰ – 1)[(11¹⁰)⁹+(11¹⁰ )⁸+…+(11¹⁰)⁰].

Bunda 11¹⁰-1 ning 10²ga bo’linishini yuqorida ko’rdik, 2-qavsdagi 10ta qo’shiluvchi 1 bilan tugagani sababli ularning yig’indisi 10 ga bo’linadi, demak, 11¹⁰ -1 ayirma 10³ga bo’linadi.

n=3 bo’lsin:

11¹⁰ -1=(11¹⁰ )¹⁰-1=(11¹⁰ - 1)[(11¹⁰ )⁹+(11¹⁰ )⁸+…+(11¹⁰ )¹+(11¹⁰ )⁰]

Yuqoridagi mulohazalarni takrorlasak, birinchi qavsning 10³ga, o’rta qavsdagi yigíndining 10 ga va 11¹⁰ -1 ayirmaning 10⁴ ga bo’linishiga ishonch hosil qilamiz. O’rganilgan n=1,2,3 hollar ushbu gipotezani aytish imkonini beradi:

n N da (11¹⁰ -1) 10ⁿ⁺¹

(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(9k+1) ni isbotlaymiz, ya’ni n=k da (11¹⁰ -1) 10^k+1 deb faraz qilib, n=k+1 uchun (11¹⁰ -1) 10^k+2 bo’lishini ko’rsatamiz.

Haqiqatan ham :

11¹⁰ -1=(11¹⁰ )¹⁰-1=(11¹⁰ -1)[(11¹⁰ )⁹ (11¹⁰ )⁸+…+(11¹⁰ )¹+(11¹⁰ )⁰]

ifodada (11¹⁰ -1) 10^k+1 farazga ko’ra, o’rta qavs ichidagi yigíndi esa yuqorida aytilganlarga asosan 10 ga karrali, demak,

(11¹⁰ -1) 10^k+2,

bu esa A(k+1) ning bajarilishini ko’rsatadi.