استقرای ریاضی کیست؟ توضیح بده.
استقرای ریاضی شیوه‌ای برای اثبات قضایای ریاضی راجع به اعداد طبیعی است. این شیوه (استقرای ساده) از دو مرحله تشکیل شده‌است. در مرحلۀ اول، درستی قضیۀ formula_1 برای عددی پایه به اثبات می‌رسد. اکنون می‌دانیم که حداقل برای شماری از اولین اعداد طبیعی formula_1 درست است. اکنون با این فرض که formula_3 برای حکم درست باشد، درستی formula_4 را نتیجه می‌گیریم. این روش اثبات، برای اولین بار توسط اقلیدس معرفی شده بود.تاریخچه.در یونان باستان مثال‌های منطقی‌ای از استقرا را می‌توان دید، ولی اولین کاربرد ریاضی استقرا در حدود ۱۰۰۰ میلادی توسط ابوبکر کرجی هنگام کار بر روی بسط دو جمله‌ای یافته می‌شود.اصل استقرای ریاضی.استقرای ریاضی بیان می‌کند که اگر formula_5 به معنای درستی ویژگی formula_6 برای عدد formula_7 باشد، برای اینکه formula_5 برای همهٔ اعداد طبیعی درست باشد، باید:به‌ این‌ ترتیب با ترکیب شرط ۱ و ۲ (در حالت ویژه formula_12) می‌توان گفت که formula_13 هم درست است، در نتیجه بنابر شرط ۲ (در حالت ویژه formula_14)، formula_15 هم درست است. روشن است که با تکرار چندبارهٔ این کردارها می‌توان ویژگی formula_6 را برای هر عددی ثابت کرد، از این رو formula_3 برای همهٔ اعداد formula_18 درست است.فرمول ساده و کاربردی‌‌ای که برای محاسبهٔ formula_19 عدد اول طبیعی است را می‌توان با استقرای ریاضی ثابت کرد.formula_20برای اثبات این فرمول، اول باید توجه کرد که فرمول برای formula_21 درست است (formula_22). سپس فرض می‌شود که فرمول برای formula_23 درست باشد:formula_24آنگاه:formula_25formula_26formula_27formula_28 (تجزیهٔ دوجمله‌ای صورت)بنابراین، فرمول برای formula_29 درست می‌باشد. بنابر استقرای ریاضی، این امر نشان‌دهندهٔ این است که فرمول بالا برای هر کدام از اعداد طبیعی درست است.روش پدیداری‌تر (صوری‌‌تر) برای بیان استقرای ریاضی (بدون استفاده از «ویژگی»های عدد) این است که formula_30 یک مجموعهٔ ناتُهی در نظر گرفته شود و شرط گذاشته شود کهبه‌این‌ترتیب ثابت می‌شود که formula_30 مجموعهٔ همهٔ اعداد طبیعی است.شرط ناتهی بودن مجموعهٔ formula_30 به این دلیل است که مجموعه تهی «کوچک‌ترین عضو» ندارد و هر مجموعهٔ ناتهی «کوچک‌ترین عضو» دارد. این اصل را، که به نام اصل خوش‌ترتیبی آشنا است، می‌توان با استقرای ریاضی ثابت نمود. فرض کنیم که formula_30 «کوچک‌ترین عضو» نداشته باشد و formula_39 مجموعهٔ همهٔ اعداد طبیعی‌ باشد که عضو formula_30 نیستند. مشخص است که عدد ۱ عضو formula_30 نیست (چرا که اگر ۱ عضو formula_30 می‌بود، formula_30 «کوچک‌ترین عضو» داشت)، و افرون براین اگر ۱ تا formula_18 عضو formula_30 نباشند، formula_46 هم عضو formula_30 نیست (وگرنه formula_46 کوچک‌ترین عضو formula_30 می‌بود)، پس ۱ تا formula_46 در formula_30 نیستند. از این امر نتیجه می‌شود که ۱ تا formula_19 برای هر عدد طبیعی formula_19 عضو formula_30 نیستند و ثابت می‌شود که formula_55.همچنین می‌توان اصل استقرای ریاضی را با استفاده از اصل خوش‌ترتیبی ثابت کرد.«اصل استقرای ریاضی کامل» را هم می‌توان به عنوان نتیجهٔ اصل استقرای ریاضی به‌دست آورد. این اصل زمانی به کار می‌آید که برای اثبات formula_4، علاوه بر formula_3، باید formula_58 نیز برای همهٔ اعداد طبیعی formula_59 فرض شود. در این حالت بر اساس «اصل استقرای ریاضی کامل»، اگر formula_30 گردآورشی از اعداد طبیعی باشد،آنگاه formula_30 گردآورش همهٔ اعداد طبیعی است.تعریف بازگشتی.تعریف بازگشتی، بگرتی (concept) نزدیک به اصل استقرای ریاضی است. برای مثال، عدد formula_66 که formula_19 فاکتوریل خوانده می‌شود، به عنوان حاصل‌ضرب همهٔ اعداد طبیعی کوچک‌تر یا مساوی با formula_19 تعریف می‌شود:formula_69مفهوم فاکتوریل را می‌توان به شکل دقیق‌تر زیر بیان کرد:حاصل‌جمع همهٔ اعداد طبیعی کوچک‌تر یا مساوی با formula_19 نیز (که با نماد formula_73 نشان داده می‌شود) تعریفی بازگشتی است و می‌توان آن را به شکل زیر بیان کرد:استقرای کامل.نوعی از استقرای ریاضی، که استقرای کامل (یا استقرای قوی یا روش استقرای ارزش‌ها) نامیده می‌شود، می‌گوید که در مرحلۀ دوم ممکن است ما فرض کنیم که نه تنها این حالت برای formula_23 درست است، بلکه برای همۀ formula_19-های کمتر یا مساوی با formula_18 نیز درست می‌باشد. در واقع تفاوت این نوع از استقرا با استقرای ساده، تنها در فرض استقرا است.استقرای کامل زمانی که موارد بیشماری از فرض استقرایی برای هر مرحلۀ استقرا نیاز است، بسیار مفید می‌باشد. برای نمونه، استقرای کامل می‌تواند برای اثبات فرمول فیبوناچی استفاده شود. فرمول فیبوناچی برای formula_19-اُمین عدد با عبارت پایین برابر است (در اینجا formula_80 (فی) همان عدد طلایی است که با formula_81 برابر است):formula_82درستی جملۀ عمومی را می‌توان از روش استقرای کامل ریاضی اثبات کرد.برای formula_83 داریم:formula_84برای formula_85 داریم:formula_86در نتیجه برای formula_83 و formula_85 فرمول درست است.حال با فرض درستی رابطه برای formula_89، می‌خواهیم فرمول را برای formula_90 ثابت کنیم.برای formula_91 داریم:formula_92برای formula_93 داریم:formula_94حال فرمول را برای formula_95 که برآیه formula_96 و formula_97 است، ثابت می‌کنیم:formula_98یکی دیگر از اثبات‌ها با استقرای کامل از این فرضیه، که این حالت برای همۀ formula_19-های کوچک‌تر به‌طور کامل درست است، استفاده می‌کند. حالتی که هر عدد طبیعی بزرگ‌تر از ۱ برآمده از (یک یا چند) عدد اول است را در نظر بگیرید و فرض کنید که برای یک formula_100 داده شده و formula_101، برای همۀ formula_102-های کوچک‌تر درست است. اگر formula_100 عدد اول باشد، پس قطعاً یک برآمده از اعداد اول است، و اگر نه، پس بنابر تعریف آن برآمدۀ formula_104 است، که در آن هیچ‌یک از عوامل برابر با ۱ نیست. از این رو با formula_100 برابر نیست، و به همین ترتیب هر دو کوچک‌تر از formula_100 می‌باشند. حال فرض استقرا به formula_107 و formula_108 اعمال می‌شود، بنابراین هر یک برآمده‌ای از اعداد اول استند. پس formula_100 برآمده‌ای از اعداد اول است. برای نمونه یک برآمده از اعداد اول.این تعمیم از استقرای کامل، برابر است با استقرای عادی ریاضی. فرض کنید که formula_1 حالتی است که ما قصد داریم آن را با استقرای کامل اثبات کنیم. اجازه دهید formula_111 به معنای formula_112 برای همۀ formula_100-ها به‌طوری‌ که formula_114 و formula_115 باشد. پس formula_111 برای همه formula_19-ها درست است اگر و تنها اگر formula_1 برای تمام formula_19-ها درست باشد، و یک اثبات formula_1 با استقرای کامل با یک اثبات formula_111 توسط استقرا (عادی) کاملاً یکسان است.تعریف صوری اصل استقرا.اصل استقرا در زبان صوری ریاضی به‌صورت زیر نوشته می‌شود.