موضوع مقاله: استقرای ریاضی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # استقرای ریاضی | مقدمه: تاریخچه در یونان باستان مثال‌های منطقی‌ای از استقرا را می‌توان دید، ولی اولین کاربرد ریاضی استقرا در حدود ۱۰۰۰ میلادی توسط ابوبکر کرجی هنگام کار بر روی بسط دو جمله‌ای یافته می‌شود.Rashed, R. | ## بخش 1: استقرای ریاضی | به‌ این‌ ترتیب با ترکیب شرط ۱ و ۲ (در حالت ویژه ) می‌توان گفت که هم درست است، در نتیجه بنابر شرط ۲ (در حالت ویژه )، هم درست است. روشن است که با تکرار چندبارهٔ این کردارها می‌توان ویژگی را برای هر عددی ثابت کرد، از این رو برای همهٔ اعداد درست است. فرمول ساده و کاربردی‌‌ای که برای محاسبهٔ عدد اول طبیعی است را می‌توان با استقرای ریاضی ثابت کرد. سپس فرض می‌شود که فرمول برای درست باشد: آنگاه: (تجزیهٔ دوجمله‌ای صورت) بنابراین، فرمول برای درست می‌باشد. بنابر استقرای ریاضی، این امر نشان‌دهندهٔ این است که فرمول بالا برای هر کدام از اعداد طبیعی درست است. روش پدیداری‌تر (صوری‌‌تر) برای بیان استقرای ریاضی (بدون استفاده از «ویژگی»های عدد) این است که یک مجموعهٔ ناتُهی در نظر گرفته شود و شرط گذاشته شود که عدد ۱ وندی از مجموعهٔ باشد. شرط ناتهی بودن مجموعهٔ به این دلیل است که مجموعه تهی «کوچک‌ترین عضو» ندارد و هر مجموعهٔ ناتهی «کوچک‌ترین عضو» دارد. | ## بخش 2: استقرای ریاضی | این اصل را، که به نام اصل خوش‌ترتیبی آشنا است، می‌توان با استقرای ریاضی ثابت نمود. فرض کنیم که «کوچک‌ترین عضو» نداشته باشد و مجموعهٔ همهٔ اعداد طبیعی‌ باشد که عضو نیستند. مشخص است که عدد ۱ عضو نیست (چرا که اگر ۱ عضو می‌بود، «کوچک‌ترین عضو» داشت)، و افرون براین اگر ۱ تا عضو نباشند، هم عضو نیست (وگرنه کوچک‌ترین عضو می‌بود)، پس ۱ تا در نیستند. «اصل استقرای ریاضی کامل» را هم می‌توان به عنوان نتیجهٔ اصل استقرای ریاضی به‌دست آورد. این اصل زمانی به کار می‌آید که برای اثبات ، علاوه بر ، باید نیز برای همهٔ اعداد طبیعی فرض شود. در این حالت بر اساس «اصل استقرای ریاضی کامل»، اگر گردآورشی از اعداد طبیعی باشد، عدد ۱ عضوی از گردآورشی A باشد. برای مثال، عدد که فاکتوریل خوانده می‌شود، به عنوان حاصل‌ضرب همهٔ اعداد طبیعی کوچک‌تر یا مساوی با تعریف می‌شود: مفهوم فاکتوریل را می‌توان به شکل دقیق‌تر زیر بیان کرد: حاصل‌جمع همهٔ اعداد طبیعی کوچک‌تر یا مساوی با نیز (که با نماد نشان داده می‌شود) تعریفی بازگشتی است و می‌توان آن را به شکل زیر بیان کرد: استقرای کامل نوعی از استقرای ریاضی، که استقرای کامل (یا استقرای قوی یا روش استقرای ارزش‌ها) نامیده می‌شود، می‌گوید که در مرحلۀ دوم ممکن است ما فرض کنیم که نه تنها این حالت برای درست است، بلکه برای همۀ -های کمتر یا مساوی با نیز درست می‌باشد. | ## بخش 3: استقرای ریاضی | در واقع تفاوت این نوع از استقرا با استقرای ساده، تنها در فرض استقرا است.موحد، درآمدی به منطق جدید (چاپ سیزدهم)، صفحۀ 127، علمی و فرهنگی. استقرای کامل زمانی که موارد بیشماری از فرض استقرایی برای هر مرحلۀ استقرا نیاز است، بسیار مفید می‌باشد. فرمول فیبوناچی برای -اُمین عدد با عبارت پایین برابر است (در اینجا (فی) همان عدد طلایی است که با برابر است): درستی جملۀ عمومی را می‌توان از روش استقرای کامل ریاضی اثبات کرد. برای داریم: برای داریم: حال فرمول را برای که برآیه و است، ثابت می‌کنیم: یکی دیگر از اثبات‌ها با استقرای کامل از این فرضیه، که این حالت برای همۀ -های کوچک‌تر به‌طور کامل درست است، استفاده می‌کند. حالتی که هر عدد طبیعی بزرگ‌تر از ۱ برآمده از (یک یا چند) عدد اول است را در نظر بگیرید و فرض کنید که برای یک داده شده و ، برای همۀ -های کوچک‌تر درست است. اگر عدد اول باشد، پس قطعاً یک برآمده از اعداد اول است، و اگر نه، پس بنابر تعریف آن برآمدۀ است، که در آن هیچ‌یک از عوامل برابر با ۱ نیست. | ## جمع‌بندی | پس برای همه -ها درست است اگر و تنها اگر برای تمام -ها درست باشد، و یک اثبات با استقرای کامل با یک اثبات توسط استقرا (عادی) کاملاً یکسان است.