استقرای ریاضی
استقرای ریاضی شیوه‌ای برای اثبات قضایای ریاضی بر روی اعداد طبیعی است. این شیوه (استقراء ساده) از دو مرحله تشکیل شده‌است. در مرحلهٔ اول، درستی قضیه formula_1 برای عددی پایه به اثبات می‌رسد. حال می‌دانیم که لااقل برای تعدادی از ابتدای اعداد طبیعی formula_1 درست است. اکنون با فرض آنکه formula_3 برای حکم درست باشد، درستی formula_4 را نتیجه می‌گیریم. این روش اثبات برای اولین بار توسط اقلیدس معرفی شده بود.
در یونان باستان مثال‌های منطقی از استقرا را می‌توان مشاهده کرد ولی اولین کاربرد ریاضی استقرا در حدود ۱۰۰۰ میلادی توسط ابوبکر کرجی هنگام کار بر روی بسط دو جمله‌ای یافته می‌شود.
استقرای ریاضی بیان می‌کند که اگر formula_5 به معنای صدق ویژگی P برای عدد x باشد، برای اینکه formula_5 برای همهٔ اعداد طبیعی صدق کند باید:
به‌این‌ترتیب با ترکیب شرط ۱ و ۲ (در حالت خاص formula_10) می‌توان گفت که formula_11 هم صادق است، در نتیجه بنابر شرط ۲ (در حالت خاص formula_12)، formula_13 هم صادق است. واضح است که با تکرار چندبارهٔ این عملیات می‌توان ویژگی P را برای هر عددی ثابت کرد، ازین‌رو formula_3 برای همهٔ اعداد k صادق است.
فرمول ساده و کاربردی‌ای که برای محاسبهٔ n عدد اول وجود دارد را می‌توان با استقرای ریاضی ثابت کرد. بنابر این فرمول: formula_15 برای اثبات این فرمول، نخست باید توجه کرد که فرمول برای ۱ صادق است (formula_16). سپس فرض می‌شود که فرمول برای k عدد طبیعی اول صادق باشد: formula_17 آن‌گاه: formula_18 formula_19 formula_20 formula_21(تجزیهٔ دوجمله‌ای صورت) بنابراین فرمول برای formula_22 صدق می‌کند. بنابر استقرای ریاضی این امر نشان‌دهندهٔ این است که فرمول فوق برای هر کدام از اعداد طبیعی صادق است.
روش صوری‌تر برای بیان استقرای ریاضی (بدون استفاده از «ویژگی» های عدد) این است که A یک مجموعهٔ ناتُهی در نظر گرفته شود و شرط گذاشته شود که به‌این‌ترتیب ثابت می‌شود که A مجموعهٔ همهٔ اعداد طبیعی است.
شرط ناتهی بودن مجموعهٔ A به این دلیل است که مجموعه تهی «کوچکترین عضو» ندارد و هر مجموعهٔ ناتهی «کوچکترین عضو» دارد. این اصل را، که به اصل خوش‌ترتیبی موسوم است، می‌توان با استقرای ریاضی ثابت کرد. فرض شود A «کوچکترین عضو» نداشته باشد و B مجموعهٔ همهٔ اعداد طبیعی‌ای باشد که عضو A نیستند. مشخص است که عدد ۱ عضو A نیست (چرا که اگر ۱ عضو A بود A «کوچکترین عضو» داشت)، و علاوه‌براین اگر ۱ تا k عضو A نباشند، k+1 هم عضو A نیست (درغیراین‌صورت k+1 کوچکترین عضو A می‌بود)، پس ۱ تا k+1 در A نیستند. ازین امر نتیجه می‌شود که ۱ تا n برای هر عدد طبیعی n عضو A نیستند و ثابت می‌شود که formula_24.
همچنین می‌توان اصل استقرای ریاضی را با استفاده از اصل خوش‌ترتیبی ثابت کرد. «اصل استقرای ریاضی کامل» را هم می‌توان به عنوان نتیجهٔ اصل استقرای ریاضی به دست آورد. این اصل زمانی به کار می‌آید که برای اثبات formula_4 علاوه بر formula_3 باید formula_27 نیز برای همهٔ اعداد طبیعی formula_28 مفروض باشد. در این حالت بر اساس «اصل استقرای ریاضی کامل»، اگر A مجموعه‌ای از اعداد طبیعی باشد، آنگاه A مجموعهٔ همهٔ اعداد طبیعی است.
تعریف بازگشتی مفهومی نزدیک به اصل استقرای ریاضی است. برای مثال، عدد formula_31 (که «اِن فاکتوریل» خوانده می‌شود) به عنوان حاصل‌ضرب همهٔ اعداد طبیعی کوچکتر از یا برابر با n تعریف می‌شود:
formula_32
مفهوم فاکتوریل را می‌توان به شکل دقیق‌تر زیر بیان کرد: حاصل‌جمع همهٔ اعداد طبیعی کوچکتر از یا برابر با n نیز (که با نماد formula_35 نشان داده می‌شود) نیز تعریفی بازگشتی است و می‌توان آن را به شکل زیر بیان کرد:
نوعی از استقرای ریاضی، که استقرای کامل (یا استقرای قوی یا روش استقرای ارزش‌ها) نامیده می‌شود، می‌گوید که در مرحله دوم ممکن است ما فرض کنیم که نه تنها این حالت برای n = k صحیح است بلکه برای همه nهای کمتر یا مساوی با k نیز درست می‌باشد.
استقرای کامل زمانی که موارد متعددی از فرض استقرائی برای هر مرحله استقرا مورد نیاز است، بسیار مفید است. به عنوان مثال، استقرای کامل می‌تواند برای اثبات فرمول فیبوناچی استفاده شود. فرمول فیبوناچی برای formula_38 امین عدد با عبارت پایین برابر است (در اینجا formula_39 (فی) همان عدد طلایی است که با formula_40 برابر است):
formula_41
درستی جمله عمومی را می‌توان از طریق استقرای کامل ریاضی اثبات کرد.
برای formula_42 داریم: formula_43 برای formula_44 داریم: formula_45 در نتیجه برای formula_42 و formula_44 فرمول درست است.
حال با فرض درسی رابطه برای formula_48 می‌خواهیم فرمول را برای formula_49 ثابت کنیم.
برای formula_50 داریم: formula_51 برای formula_52 داریم: formula_53 حال فرمول را برای formula_54 که حاصل‌جمع formula_55 و formula_56 است ثابت می‌کنیم" formula_57 یکی دیگر از اثبات‌ها با استقرای کامل از این فرضیه که این حالت برای همه nهای کوچکتر به‌طور کامل صحیح است، استفاده می‌کند. حالتی که هر عدد طبیعی بزرگتر از ۱ حاصل از (یک یا چند) عدد اول است را در نظر بگیرید و فرض کنید که برای یک m داده شده که m> 1، برای همه n> 1های کوچکتر صحیح است. اگر m اول باشد پس قطعاً یک محصول از اعداد اول است، و اگر نه، پس بنابه تعریف آن محصول m = nn است، که در آن هیچ‌یک از عوامل برابر با ۱ نیست. از این رو با m برابر نیست، و به همین ترتیب هر دو کوچکتر از m می‌باشند. حال فرض استقرا به n و n اعمال می‌شود، بنابراین هر یک محصولی از اعداد اول‌اند. پس m محصولی از محصولات اعداد اول است. به عنوان مثال یک محصول از اعداد اول.
این تعمیم استقرای کامل، معادل است با استقرای عادی ریاضی. فرض کنید (P(n حالتی است که ما قصد داریم آن را با استقرای کامل اثبات کنیم. اجازه دهید (Q(n به معنای (P(m برای همه mها به‌طوری‌که ۰ ≤ m و m ≤ n باشد. پس (Q(n برای همه nها درست است اگر و تنها اگر (P(n برای تمام nها درست باشد، و یک اثبات (P(n با استقرای کامل با یک اثبات (Q(n توسط استقرا (عادی) کاملاً یکسان است.
اصل استقرا در زبان فرمال ریاضی به‌صورت زیر نوشته می‌شود.