Kombinatorika fani rivojlanish tarixi

2- misol. Ixtiyoriy natural son uchun

tenglikning o‘rinli bo‘lishini matematik induksiya usuli yordamida isbotlaymiz.
Baza: bo‘lsin, u holda yuqoridagi tenglik to‘g‘ri ekanligi ravshan: .
Induksion o‘tish: isbotlanish kerak bo‘lgan tenglik uchun to‘g‘ri, ya’ni

tenglik o‘rinli bo‘lsin. Bu tenglikning chap va o‘ng tomonlariga ifodani qo‘shib, uni

ko‘rinishda yozamiz. Oxirgi tenglikning o‘ng tomonida quyidagicha o‘zgartirishlarni bajaramiz:


.
Demak,
.
Oxirgi munosabat isbotlanishi kerak bo‘lgan tenglikning bo‘lgan holidir.
Shuni ta’kidlash kerakki, biror tasdiqni isbotlash uchun matematik induksiya usuli qo‘llanilganda, bu usulning ikkala qismini ham tekshirib ko‘rish muhimdir, ya’ni baza va induksion o‘tish albatta tekshirilishi shart. Ulardan biri tekshirilmasa noto‘g‘ri natijalar hosil bo‘lishi ham mumkin. Bundan tashqari, baza birorta xususiy qiymatdan boshqa ko‘p, hattoki, juda ko‘p xususiy hollar uchun tekshirilib, ijobiy natija olinganda ham, bu hollarni umumlashtiruvchi natijaviy tasdiq noto‘g‘ri bo‘lib chiqishi mumkin. Bu mulohazalarning o‘rinli ekanligini quyida keltirilgan misollar ko‘rsatadi.
3- misol. “Ixtiyoriy natural son uchun son 2ga qoldiqsiz bo‘linadi” degan tasdiqni tekshirishda matematik induksiya usulining baza qismi talabini bajarmasdan faqat induksion o‘tishni tekshiramiz.
Bu tasdiq uchun to‘g‘ri bo‘lsin, ja’ni son 2ga qoldiqsiz bo‘linsin deb faraz qilamiz. U holda son ham, qo‘shiuvchilarining har biri 2ga qoldiqsiz bo‘linganligi sababli, 2ga qoldiqsiz bo‘linadi. Shuning uchun tenglik asosida son 2ga qoldiqsiz bo‘linadi degan xulosa kelib chiqadi. Demak, yuqoridagi tasdiq uchun to‘g‘ri, ya’ni induksion o‘tish bajarildi deb hisoblash mumkin.
Shunday qilib, matematik induksiya usulining baza qismini tekshirmasdan “ixtiyoriy natural son uchun son 2ga qoldiqsiz bo‘linadi” degan xulosa qilish noto‘g‘ridir, chunki ixtiyoriy natural son uchun sonni 2ga bo‘lganda 1 qoldiq qoladi.