استقرای ریاضی

اصل استقراء ریاضی شیوه‌ای برای اثبات قضایای ریاضی بر روی اعداد طبیعی است. این شیوه (استقراء ساده) از دو مرحله تشکیل شده است. در مرحله اول درستی قضیه ‎$P(n)$‎ برای عددی پایه به اثبات می‌رسد. حال می‌دانیم که لااقل برای تعدادی از ابتدای اعداد طبیعی ‎$P(n)$‎ درست است. اکنون با فرض آنکه ‎$P(k)$‎ برای حکم درست باشد، درستی ‎$P(k+1)$‎ را نتیجه می‌گیریم. این روش اثبات برای اولین بار توسط ریاضی‌دان ایرانی ابوبکر کرجی معرفی شده بود.

اصل استقرا

اصل استقرا در زبان فرمال ریاضی به‌صورت زیر نوشته می‌شود.

$(\forall P)[P(0) \land ( \forall k \in \mathbb{N}) (P(k) \Rightarrow P(k+1))] \Rightarrow ( \forall n \in \mathbb{N} ) [ P(n) ]$

منابع

• ریچارد جانسون با. ساختمان‌های گسسته. ترجمهٔ حسین ابراهیم‌زاده قلزم. ویرایش پنجم. چاپ اول. سیمای دانش، ۱۳۸۰. 

• Introductory Mathematics: Algebra and Analysis by Geoff Smith