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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

اصل استقراء ریاضی شیوه‌ای برای اثبات قضایای ریاضی بر روی اعداد طبیعی است. این شیوه (استقراء ساده) از دو مرحله تشکیل شده است. در مرحله اول درستی قضیه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