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

اصل استقراء ریاضی شیوه ای برای اثبات قضایای ریاضی بر روی اعداد طبیعی است. این شیوه (استقراء ساده) از دو مرحله تشکیل شده است. در مرحله اول درستی قضیه ‎ P ( n ) {\displaystyle P(n)} ‎ برای عددی پایه به اثبات می رسد. حال می دانیم که لااقل برای تعدادی از ابتدای اعداد طبیعی ‎ P ( n ) {\displaystyle P(n)} ‎ درست است. اکنون با فرض آنکه ‎ P ( k ) {\displaystyle P(k)} ‎ برای حکم درست باشد، درستی ‎ P ( k + 1 ) {\displaystyle P(k+1)} ‎ را نتیجه می گیریم. این روش اثبات برای اولین بار توسط ریاضی دان ایرانی ابوبکر کرجی معرفی شده بود.
Introductory Mathematics: Algebra and Analysis by Geoff Smith
استقرار ریاضی بیان می کند که اگر P ( x ) {\displaystyle P(x)}   به معنای صدق ویژگی P برای عدد x باشد، برای اینکه P ( x ) {\displaystyle P(x)}   برای همهٔ اعداد طبیعی صدق کند باید:
به این ترتیب با ترکیب شرط ۱ و ۲ (در حالت خاص k = 1 {\displaystyle k=1}  ) می توان گفت که P ( 2 ) {\displaystyle P(2)}   هم صادق است، در نتیجه بنابر شرط ۲ (در حالت خاص k = 2 {\displaystyle k=2}  )، P ( 3 ) {\displaystyle P(3)}   هم صادق است. واضح است که با تکرار چندبارهٔ این عملیات می توان ویژگی P را برای هر عددی ثابت کرد، ازین رو P ( k ) {\displaystyle P(k)}   برای همهٔ اعداد k صادق است.
فرمول ساده و کاربردی ای که برای محاسبهٔ n عدد اول وجود دارد را می توان با استقرای ریاضی ثابت کرد. بنابر این فرمول: 1 + 2 + 3 + . . . + n = n ( n + 1 ) 2 . {\displaystyle 1+2+3+...+n={\frac {n(n+1)}{2}}.}  برای اثبات این فرمول، نخست باید توجه کرد که فرمول برای ۱ صادق است ( 1 ( 1 + 1 ) 2 = 1 {\displaystyle {\frac {1(1+1)}{2}}=1}  ). سپس فرض می شود که فرمول برای k عدد طبیعی اول صادق باشد: 1 + 2 + 3 + . . . + k = k ( k + 1 ) 2 . {\displaystyle 1+2+3+...+k={\frac {k(k+1)}{2}}.}  آن گاه: 1 + 2 + 3 + . . . + k + ( k + 1 ) = k ( k + 1 ) 2 + ( k + 1 ) , {\displaystyle 1+2+3+...+k+(k+1)={\frac {k(k+1)}{2}}+(k+1),}   = k ( k + 1 ) + 2 ( k + 1 ) 2 , {\displaystyle ={\frac {k(k+1)+2(k+1)}{2}},}   = k 2 + 3 k + 2 2 , {\displaystyle ={\frac {k^{2}+3k+2}{2}},}   = ( k + 1 ) ( k + 2 ) 2 , {\displaystyle ={\frac {(k+1)(k+2)}{2}},}  (تجزیهٔ دوجمله ای صورت)بنابراین فرمول برای k + 1 {\displaystyle k+1}   صدق می کند. بنابر استقرای ریاضی این امر نشان دهندهٔ این است که فرمول فوق برای هر کدام از اعداد طبیعی صادق است.

اِستِقرایِ ریاضی (mathematical induction)
یکی از روش های رسمی اثبات در ریاضیات، برای اثبات حکم هایی دربارۀ متغیر صحیح مثبت. اگر این متغیر را با n و حکم را با ( p(n نمایش دهیم، مراحل استقرای ریاضی از این قرار است: (۱) ثابت می کنند ( p(n به ازای عددی چون n = k درست است؛ (۲) ثابت می کنند که اگر ( p(n به ازای n، یا n و همۀ اعداد بین k و n، درست باشد، به ازایn + ۱ نیز درست است؛ (۳) آن گاه با استقرا نتیجه می گیرند که (p(n به ازای هر n یعنیn=k, k+۱, k+۲, k+۳, ... درست است. در بسیاری از موارد، k برابر ۱ در نظر گرفته می شود و در این صورت، درستی( p(n به ازای همۀ اعداد صحیح مثبت ثابت می شود.