5-mavzu: fibonachchi sonlari reja

1- misol. Elementlari 0 va 1 raqamlaridan iborat bo‘lib, ikkita 1 raqami yonma-yon joylashmydigan kortejlarni qaraymiz. Shunday tartibda tuziladigan uzunlikka ega barcha kortejlar soni Fibonachchi qatorining ( )- hadiga tengligini, ya’ni tenglik o‘rinli bo‘lishini ko‘rsatamiz.

Buning uchun matematik induksiya usulidan foydalanaymiz. Matematik induksiya usulining bazasi sifatida bo‘lgan holni qaraymiz. Bu holda misol shartlarini qanoatlantiruvchi ikkita ( va ) kortejlar tuzish mumkin, ya’ni . Fibonachchi qatorining tuzilishiga asosan bo‘lgan hol uchun . Demak, bo‘lganda tasdiq to‘g‘ri.

Induksion o‘tish: bo‘lganda misol shartlarini qanoatlantiruvchi kortejlar soni uchun isbotlanayotgan tenglik o‘rinli bo‘lsin, ya’ni . Bu tenglikning uchun ham to‘g‘riligini ko‘rsatamiz. Ravshanki, uzunligi bo‘lgan barcha kortejlarni, tuzilishiga ko‘ra, ikki guruhga quyidagicha ajratish mumkin.

Birinchi guruhga talab qilingan shartlar asosida tuzilgan va uzunligi ga teng kortejlarning har biriga o‘ng tomondan 0 raqamini joylashtirish usuli bilan hosil qilingan kortejlarni kiritamiz. Shuning uchun,birinchi guruhdagi kortejlar soni uzunligi ga teng kortejlar soniga teng. Bu yerda induksiya farazini hisobga olsak birinchi guruhda ta kortejlar bor degan xulosaga kelamiz.

Ikkinchi guruhga oxirgi elementi 1 raqamidan iborat bo‘lgan kortejlarni kiritamiz. Kortejlarni tuzishning misolda talab qilinayotgan shartiga ko‘ra ikkinchi guruhdagi har bir kortejda oxirgi 1 raqamidan oldin faqat 0 raqami joylashishi mumkinligi kelib chiqadi. Shuning uchun,ikkinchi guruhdagi kortejlarning uzunligi ( )ga teng bo‘lgan va talab qilingan shartlar asosida tuzilgan kortejlarning har biriga o‘ng tomondan 0, 1 raqamlarini (aynan shu tartibda) joylashtirib hosil qilish mumkin. Demak, induksion farazni hisobga olsak, ikkinchi guruhdagi kortejlar soni bo‘ladi.

Shunday qilib, uzunlikka ega barcha kortejlar soni . Fibonachchi qatorining aniqlanishiga ko‘ra, . Bu yerdan . ■