Rekurrent munosabatlar. Rekurrent munosabatlarni yechish usullari. Nyuton binomi. Binomial koeffitsientlar. Polinomial formula

REKURRENT MUNOSABATLAR. REKURRENT MUNOSABATLARNI YECHISH USULLARI. NYUTON BINOMI. BINOMIAL KOEFFITSIENTLAR. POLINOMIAL FORMULA.
Nyuton binomi - ikki qoʻshiluvchi yigʻindisining ixtiyoriy butun musbat darajasini qoʻshiluvchilar darajalari yigʻindisi koʻrinishda ifodalovchi formula. Binomial koeffitsiyentlari arifmetik uchburchak tashkil qiladi.
Nyuton binomi formulasi I. Nyutondan ancha avval ham maʼlum boʻlgan. Masalan, Umar Xayyom (11 — 12-asrlar), Jamshid Koshiy (14—15-asrlar) binomial koeffitsiyentlarni hisoblash qoidasini bilganlar. I. Nyuton esa binom yoyilmasini ixtiyoriy koʻrsatkich uchun umumlashtirgan. Nyuton binomi matematik analiz, sonlar nazariyasi, ehtimollar nazariyasi va boshqa sohalarda muhim ahamiyatga ega
1. Paskal uchburchagi haqida umumiy ma’lumotlar Berilgan n ta elementdan m tadan gruppalashlar soni m Cn uchun bir necha qatorlarni 1- jadvaldagidek yozamiz: 1-jadval n Gruppalashlar soni m Cn ( m  0,n ) 1 1 0 C1  , 1 1 C1  2 1 0 C2  , 2 1 C2  , 1 2 C2  3 1 0 C3  , 3 1 C3  , 3 2 C3  , 1 3 C3  4 1 0 C4  , 4 1 C4  , 6 2 C4  , 4 3 C4  , 1 4 C4  5 1 0 C5  , 5 1 C5  , 10 2 C5  , 10 3 C5  , 5 4 C5  , 1 4 C4  … …………………………………………………………. Bu jadvalda gruppalashlar sonining quyidagi xossalarini kuzatish mumkin: – har bir qatorning chetlarida birlar joylashgan (bu tasdiq 1 0   n Cn Cn formula bilan ifodalanadi); – har bir qatordagi m Cn sonlar qatorning teng o‘rtasiga nisbatan simmetrik joylashgan, ya’ni qatorning boshidan va oxiridan baravar uzoqlikda turgan sonlar o‘zaro teng ( n m n m Cn C   ); – ikkinchi qatordan boshlab har bir qatordagi birlardan tashqari ixtiyoriy son bu qatordan yuqorida joylashgan qatordagi biri shu son ustida, ikkinchisi esa undan chapda joylashgan ikkita gruppalashlar sonining yig‘indisiga teng ( 1 1 1      m n m n m Cn C C ); – har bir qatordagi m Cn sonlar shu qator teng o‘rtasigacha o‘sib, so‘ng kamayadi. Ta’rif sifatida 1 0 C0  deb qabul qilinsa va bu son yuqoridagi jadvalning n 1 raqamli qatoridan oldin n  0 raqamli qatori sifatida joylashtirilsa, uchburchak figurasiga o‘xshash 1-shakldagi sonlar jadvalini hosil qilish mumkin. 1-shakldagi sonlar jadvali Paskal uchburchagi deb ataladi. Bu jadval arifmetik uchburchak nomi bilan ham yuritiladi. Uning Paskal nomi bilan atalishiga qaramasdan, bunday sonlar jadvali juda qadimdan dunyoning turli mintaqalarida, jumladan, sharq mamlakatlarida ham ma’lum bo‘lgan. Masalan, Erondagi Tus shahrida (hozirgi Mashhadda)  1 7 21 35 35 21 7 1 1 6 15 20 15 6 1 1 5 10 10 5 1 1 4 6 4 1 1 3 3 1 1 2 1 1 1 1 1- shakl 2 yashab ijod qilgan Nosir at-Tusiy1 XIII asrda bu jadvaldan foydalanib, berilgan ikkita son yig‘indisining natural darajasini hisoblash usulini o‘zining ilmiy ishlarida keltirgan bo‘lsa, g‘arbda Al-Kashi nomi bilan mashhur Samarqandlik olim Ali Qushchi2 butun sonning istalgan natural ko‘rsatkichli arifmetik ildizi qiymatini taqribiy hisoblashda bu jadvaldan foydalana bilganligi haqida ma’lumotlar bor. Keyinchalik G‘arbiy Yevropada bu sonlar uchburchagi haqida M. Shtifel3 arifmetika bo‘yicha qo‘llanmalarida yozgan va u ham butun sondan istalgan natural ko‘rsatkichli arifmetik ildizning taqribiy qiymatini hisoblashda bu uchburchakdan foydalana bilgan. 1556 yilda bu sonlar jadvali bilan N. Tartalya4 , keyinroq logarifmik lineyka ijodkori U. Otred5 (1631 yil) ham shug‘ullanganlar. 1654 yilga kelib B. Paskal o‘zining “Arifmetik uchburchak haqidagi traktat” nomli asarida bu sonlar jadvali haqidagi ma’lumotlarni e’lon qildi. Paskal uchburchagidagi qatorlar istalgancha davom ettirilishi mumkin. Shunisi qiziqki, Paskal uchburchagi yordamida istalgan n ta elementdan m tadan gruppalashlar sonini faqat qo‘shish amali yordamida hosil qilish mumkin ( m Cn sonni hisoblash !( )! ! m n m n C m n   , 1 2 ...( ) ( 1)...( 1) n m n n m C m n       va m n n n m C m n        1 2 ... ( 1)...( 1) formulalariga qarang). Bu amal m n m n m Cn C C 1 1 1      formulaga asoslanadi. Paskal uchburchagi ko‘plab ajoyib xossalarga ega. B. Paskal yuqorida zikr etilgan traktatda: “Bu xossalarning haqiqatdan ham bitmas-tuganmasligi naqadar ajoyibdir” deb yozgan edi. 2. Nyuton binomi haqida umumiy ma’lumotlar O‘rta maktab matematikasi kursidan quyidagi ikkita qisqa ko‘paytirish formulalarini eslaylik: 2 2 2 (a  b)  a  2ab b – yig‘indining kvadrati; 3 3 2 2 3 (a  b)  a  3a b  3ab  b – yig‘indining kubi. Yig‘indining navbatdagi ikkita, ya’ni 4-va 5-darajalarini hisoblaymiz: (  )  (  )(  )  (  )(  3  3  )  4 3 3 2 2 3 a b a b a b a b a a b ab b 4 3 2 2 3 4  a  4a b  6a b  4ab  b ,      5 4 (a b) (a b)(a b) 5 4 3 2 2 3 4 5  a  5a b 10a b 10a b  5ab  b . Shunday qilib, yig‘indining bikvadrati (ya’ni to‘rtinchi darajasi) 4 4 3 2 2 3 4 (a  b)  a  4a b  6a b  4ab  b va yig‘indining beshinchi darajasi 1 At-Tusiy (Nosir ad-Din-Muhammad ibn Muhammad ibn-al-Hasan, 1201-1274) – Eron astronomi va matematigi. 2 Ali Qushchi (Jamshid ibn Ma’sud, tug‘ilgan yili noma’lum–taxminan 1436 yoki 1437 yilda vafot etgan) – o‘zbek matematigi va astronomi, 1420-30 yillarda Samarqandda Mirzo Ulug‘bek observatoriyasida ishlagan. 3 Shtifel Mixel (Michel, 1487-1567) – olmon matematigi. 4 Tartalya Nikkolo (Tartalia Nic-colo, 1499 yil atrofida tug‘ilgan-1557) – italyan matematigi va mexanigi. 5 Otred Uilyam (Outred William, 1574-1660) – ingliz matematigi. 3 5 5 4 3 2 2 3 4 5 (a  b)  a  5a b 10a b 10a b  5ab  b formulalariga ega bo‘lamiz. Yuqorida keltirilgan yig‘indining kvadrati, kubi, bikvadrati va beshinchi darajasi formulalari o‘ng tomonlaridagi ko‘phad koeffitsientlari Paskal uchburchagining mos qatorlaridagi m Cn ( n  2,3,4,5 ) sonlar ekanligini payqash qiyin emas. 1-t e o r e m a . Barcha haqiqiy a va b hamda natural n sonlar uchun n n n n n n n n n n a  b  a C a b C a b  C ab  b 1 1 2 2 2 1 1 ( ) ... formula o‘rinlidir. I s bo t i . Matematik induksiya usulini qo‘llaymiz. Baza: n 1 bo‘lganda formula to‘g‘ri: a  b  a  b 1 ( ) . Induksion o‘tish: isbotlanishi kerak bo‘lgan formula n  k uchun to‘g‘ri bo‘lsin, ya’ni k k k k k k k k k k a  b  a C a b C a b  C ab  b 1 1 2 2 2 1 1 ( ) ... . Formula n  k 1 bo‘lganda ham to‘g‘ri ekanligini isbotlaymiz. Haqiqatdan ham, 1 1 1      m n m n m Cn C C formuladan foydalanib, quyidagilarni hosil qilamiz:      k k (a b) (a b)(a b) 1             ( )( ... ) 1 1 2 2 2 k 1 k 1 k k k k k k k a b a C a b C a b C ab b         k k k k k k k k a C a b C a b ... C ab 1 1 2 1 2       0 1 1 2 1 1 ... k k k k k k k Ck a b C a b C ab b ( ) ( ) ... 1 0 1 1 2 1 2         a C C a b C C a b k k k k k k k     1 1 ... ( ) k k k k k Ck C ab b 1 1 2 1 2 1 1 1 1 ...             k k k k k k k k k a C a b C a b C ab b . ■ Ixtiyoriy a va b haqiqiy sonlar hamda n natural son uchun n (a  b) ifodaning ko‘phad shaklidagi yoyilmasi (tasvirlanishi) Nyuton6 binomi deb ataladi. Umuman olganda, “Nyuton binomi” iborasiga tanqidiy nuqtai nazardan yondoshilsa, undagi ikkala so‘zga nisbatan ham shubha tug‘iladi: birinchidan, n (a  b) ifoda birdan katta natural n sonlar uchun binom (ya’ni ikkihad) emas; ikkinchidan, natural sonlar uchun bu ifodaning yoyilmasi Nyutongacha ma’lum edi7 . Greklar n (a  b) ifodaning qatorga yoyilmasini n ning faqat n  2 bo‘lgan holida (ya’ni, yig‘indi kvadratining formulasini) bilar edilar. Umar Hayyom8 va Ali Qushchi n (a  b) ifodani n  2 bo‘lgan natural sonlar uchun ham qatorga yoya bilganlar. Nyuton esa 1767 yilda yoyilma formulasini isbotsiz manfiy va kasr n sonlar uchun ham qo‘llagan. L. Eyler 1774 yilda Nyuton binomi formulasini kasr n sonlar uchun isbotladi, K. Makloren9 esa bu formulani darajaning ratsional ko‘rsatkichlari uchun qo‘lladi. Nihoyat, 1825 yilda N. Abel10 daraja ko‘rsatkichining istalgan kompleks qiymatlari uchun binom haqidagi teoremani isbotladi. 6 Isaak Nyuton (Newton, 1643-1727) – ingliz fizigi, mexanigi va matematigi. 7 Ushbu paragrafning 3.1 bandidagi xronologik ma’lumotlarga qarang. 8 Umar Hayyom G‘iyosiddin Abul-Fatx ibn Ibrohim (خیام عمر, 1048 yil atrofida tug‘ilgan-1122 yildan so‘ng vafot etgan) – fors va tojik shoiri, matematigi va faylasufi. 9 Makloren Kolin (Maclaurin Colin, 1698-1746) – Shotlandiya matematigi. 10 Abel Nils Xenrik (Niels Henric, 1802-1829) – Norvegiya matematigi. 4 m Cn sonlarni binomial koeffitsientlar deb ham atashadi. Bunday ta’rif bu koefitsientlarning Nyuton binomi formulasida tutgan o‘rniga qarab berilgan bo‘lib, m Cn son     n m m n m m n n a b C a b 0 ( ) yoyilmadagi n m m a b  ifodaning koeffitsientidir. 2-t e o r e m a . Barcha haqiqiy a va b hamda natural n sonlar uchun      n m m n m m n n m a b C a b 0 ( ) ( 1) formula o‘rinlidir. I s b o t i . Nyuton binomi formulasida b ni (  b )ga almashtirsak kerakli formulani hosil qilamiz. ■ 1-m i s o l . Oxirgi formuladan xususiy holda quyidagi qisqa ko‘paytirish formulalari kelib chiqadi: n  2 bo‘lganda ayirmaning kvadrati formulasi 2 2 2 (a b)  a  2ab b ; n  3 bo‘lganda ayirmaning kubi formulasi 3 3 2 2 3 (a  b)  a  3a b  3ab  b . ■ Nyuton binomi formulasini kombinatorik amallar yordamida ham hosil qilish mumkin. Haqiqatdan ham, ixtiyoriy a b b bn , , ,..., 1 2 sonlar uchun ( )( )...( ) a  b1 a  b2 a  bn ifodani           ( )( )...( ) ( ... ) 1 2 1 1 2 n n n a b a b a bn a a b b b        ( ... ) 1 2 1 3 1 2 n n n a bb bb b b n n n n n a (b1b2b3 ... b 2b 1b ) ... b1b2 ...b 3         . ko‘rinishda yozish mumkin. Bu tenglikning o‘ng tomonida joylashgan n a oldidagi koeffitsient birga ( 0 1 Cn ) teng. Birinchi qavslar ichidagi qo‘shiluvchilar soni n ga ( 1 n  Cn ) tengligi yaqqol ko‘rinib turibdi. Ikkinchi qavslar ichidagi qo‘shiluvchilar b b bn , ,..., 1 2 ( n ta) elementlardan ikkitadan ko‘paytmalar (soni 2 Cn ga teng gruppalashlar) ekanligini ham payqash qiyin emas. Uchinchi qavslar ichidagi qo‘shiluvchilar esa o‘sha n ta elementlardan uchtadan ko‘paytmalar bo‘lib, ularning soni 3 Cn ga teng va hokazo. Oxirgi qo‘shiluvchi oldidagi koeffitsient birga ( n 1 Cn ) teng. Yuqoridagi tenglikda b1  b2  ...  bn  b deb olsak, Nyuton binomi formulasini hosil qilamiz. 3. Binomial koeffitsientlarning xossalari Binomial koeffitsientlarning ba’zi xossalarini keltiramiz. Bu xossalar bevosita gruppalashlarga oid bo‘lib, tabiiyki, ular Paskal uchburchagining xossalarini ham ifodalaydi. 1-xossa . 1 1     m n m C C m n m n ( m  0,1,2,..., n 1 ) tenglik o‘rinlidir. Haqiqatdan ham, 5             ( 1)!( 1)! !( )! !( )! ! ( 1)!( 1)! ! 1 m n m m n m m n m n m n m n C C m n m n !( 1)( 1)! 1 !( 1)!( )           m n m m m n m m n m n m . ■ Bu xossa binomial koeffitsientlar qatoridagi istalgan ketma-ket ikki elementning biri ma’lum bo‘lsa, boshqasini osonlik bilan hisoblash mumkinligini ko‘rsatadi: m n m n C m n m C 1 1     , 1 1    m n m n C n m m C , bu yerda m  0,1,2,..., n 1. 2-xossa . Ixtiyoriy natural n son uchun barcha m Cn ( m  0,n ) binomial koeffitsientlar yig‘indisi n 2 ga teng, ya’ni n n n n Cn Cn Cn ... Cn C 2 0 1 2 1        . Bu tenglik Nyuton binomi formulasida a  b 1 deb olganda hosil bo‘ladi. ■ 3-xossa . Toq o‘rinlarda turgan binomial koeffitsientlar yig‘indisi juft o‘rinlarda turgan binomial koeffitsientlar yig‘indisiga teng. Haqiqatdan ham, Nyuton binomi formulasida a 1 va b  1 deb olganda n n n 0 Cn Cn Cn Cn ... ( 1) C 0 1 2 3        tenglikni hosil qilamiz. Bu tenglikdan xossadagi tasdiqning to‘g‘riligi kelib chiqadi. ■ 2-va 3-xossalar asosida quyidagi xossani hosil qilamiz. 4-xossa . n natural sondan oshmaydigan eng katta toq m son uchun 1 3 1 ... 2      m n Cn Cn Cn tenglik hamda n sondan oshmaydigan eng katta juft m son uchun 0 2 1 ... 2      m n Cn Cn Cn tenglik o‘rinlidir. 5-xossa . Toq n son uchun 1 2 1 2 1 0 1 ...        n n n Cn Cn Cn C , n n n n n Cn  C   C     ... 2 2 1 1 2 1 , juft n son uchun esa 0 1 2 ... n Cn  Cn   Cn , n n n n n Cn  C   C  ... 1 2 2 , munosabatlar o‘rinlidir. Haqiqatdan ham, 2 1  n m shartni qanoatlantiruvchi ixtiyoriy natural n va m sonlar uchun 1 1    m n m tengsizlik o‘rinlidir, 2 1  n m bo‘lganda esa 1 1    m n m tengsizlikka ega bo‘lamiz. Bu yerda m n m n C m n m C 1 1     formulani (1-xossaga qarang) qo‘llab, xossadagi barcha tengsizliklarni hosil qilamiz. 6 Agar n toq son bo‘lsa, 2 1  n m butun son bo‘lib, 1 1 1 1 2 2 1 1 2 1 2 1 1                 n n n n n n n n m n m munosabat o‘rinlidir. Demak, m n m n C m n m C 1 1     formuladan 2 1  n m bo‘lganda 2 1 1 2 1     n n n Cn C tenglik kelib chiqadi. ■ Binomial koeffitsientlarning 5-xossasi Paskal uchburchagining yuqorida keltirilgan xossalari tasdig‘i bo‘lib, unga ko‘ra binomial koeffitsientlar oldin 1 0 Cn  dan       2 n Cn gacha11 o‘sadi, keyin esa 1 n Cn gacha kamayadi hamda n toq bo‘lganda binomial koeffitsientlar qatorining o‘rtasidagi ikkita hadi tengdir va n juft bo‘lganda uning o‘rtadasigi hadi eng katta va yagonadir.