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

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

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

استقرای کامل[ویرایش]

نوعی از استقرای ریاضی، که استقرای کامل (یا استقرای قوی یا روش استقرای ارزش ها)نامیده می شود، می گوید که در مرحله دوم ممکن است ما فرض کنیم که نه تنها این حالت برای n = k صحیح است بلکه برای همه nهای کمتر یا مساوی با k نیز درست می باشد.

استقرای کامل زمانی که موارد متعددی از فرض استقرائی برای هر مرحله استقرا مورد نیاز است، بسیار مفید است. به عنوان مثال، استقرای کامل می تواند برای نشان دادن (Fn = (φn – ψn) / (φ – ψ استفاده شود که در آن Fn عدد فیبوناچی n ام، φ = (1 + √5) / 2 (نسبت طلایی) و ψ = (1 - √5) / 2 ریشه های چند جمله ای x2 - x - 1 می باشند. با استفاده از این واقعیت که Fn + 2 = Fn+1 + Fn برای هر n ∈ N، تایید فوق را می توان با محاسبه مستقیم Fn+2 اگر فرض کنیم که در حال حاضر برای هر دوی Fn + 1 Fn صحیح است، تعریف کرد. برای تکمیل اثبات، تعریف باید در دو حالت پایه n = 0 و n = 1 تایید شود.

یکی دیگر از اثبات ها با استقرای کامل از این فرضیه که این حالت برای همه n های کوچکتر به طور کامل صحیح است، استفاده می کند. حالتی که هر عدد طبیعی بزرگتر از 1 حاصل از (یک یا چند) عدد اول است را در نظر بگیرید و فرض کنید که برای یک m داده شده که m > 1 ، برای همه n > 1 های کوچکتر صحیح است. اگر m اول باشد پس قطعا یک محصول از اعداد اول است، و اگر نه، پس بنابه تعریف آن محصول m = n1n2 است ، که در آن هیچ یک از عوامل برابر با 1 نیست. از این رو با m برابر نیست، و به همین ترتیب هر دو کوچکتر از m می باشند. حال فرض استقرا به n1 و n2 اعمال می شود، بنابراین هر یک محصولی از اعداد اول اند. پس m محصولی از محصولات اعداد اول است. به عنوان مثال یک محصول از اعداد اول.

این تعمیم استقرای کامل، معادل است با استقرای عادی ریاضی. فرض کنید (P(n حالتی است که ما قصد داریم آن را با استقرای کامل اثبات کنیم. اجازه دهید (Q(n به معنای (P(m برای همه m ها به طوری که 0 ≤ m و m ≤ n باشد. پس (Q(n برای همه n ها درست است اگر و تنها اگر (P(n برای تمام n ها درست باشد، و یک اثبات (P(n با استقرای کامل با یک اثبات (Q(n توسط استقرا(عادی) کاملا یکسان است.

اصل استقرا[ویرایش]

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

(\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