نمایش مبدأ برای استقرای ریاضی

[[پرونده:Dominoeffect.png|بندانگشتی|استقرای ریاضی را به‌صورت غیرصوری با ارجاع به تاثیر ترتیبی افتادن [[ویژگی دومینو|دومینوها]] می‌توان نشان داد.<ref>Matt DeVos, [https://www.sfu.ca/~mdevos/notes/graph/induction.pdf ''Mathematical Induction''], [[Simon Fraser University]]</ref><ref>Gerardo con Diaz, ''[http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf Mathematical Induction] {{Webarchive|url=https://web.archive.org/web/20130502163438/http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf|date=2 May 2013}}'', [[Harvard University]]</ref>]]
'''استقرای ریاضی'''<ref>{{یادکرد فرهنگستان|مصوب=استقرای ریاضی|بیگانه=mathematical induction|بیگانه در فارسی=|حوزه=ریاضی|دفتر=پنجم|بخش=فارسی|سرواژه=استقرای ریاضی}}</ref> {{به انگلیسی|Mathematical induction}} شیوه‌ای برای اثبات قضایای [[ریاضی]] راجع به [[اعداد طبیعی]] است. این شیوه (استقرای ساده) از دو مرحله تشکیل شده‌است. در مرحلۀ اول، درستی [[قضیه|قضیۀ]] {{چر}}<math>P(n)</math>{{چر}} برای عددی پایه به اثبات می‌رسد. اکنون می‌دانیم که حداقل برای شماری از اولین اعداد طبیعی {{چر}}<math>P(n)</math>{{چر}} درست است. اکنون با این فرض که {{چر}}<math>P(k)</math>{{چر}} برای حکم درست باشد، درستی {{چر}}<math>P(k+1)</math>{{چر}} را نتیجه می‌گیریم. این [[روش اثبات]]، برای اولین بار توسط [[اقلیدس]] معرفی شده بود.<ref>{{cite web|url=http://www.earlham.edu/~peters/courses/logsys/math-ind.htm|title=Mathematical Induction|last=Suber|first=Peter|publisher=Earlham College|access-date=26 March 2011|archive-date=24 May 2011|archive-url=https://web.archive.org/web/20110524104121/http://www.earlham.edu/~peters/courses/logsys/math-ind.htm|url-status=dead}}</ref>

== تاریخچه ==
در یونان باستان مثال‌های منطقی‌ای از استقرا را می‌توان دید، ولی اولین کاربرد ریاضی استقرا در حدود ۱۰۰۰ میلادی توسط [[ابوبکر کرجی]] هنگام کار بر روی [[بسط دوجمله‌ای|بسط دو جمله‌ای]] یافته می‌شود.<ref>Rashed, R. (1994), "Mathematical induction: al-Karajī and al-Samawʾal", The Development of Arabic Mathematics: Between Arithmetic and Algebra, Boston Studies in the Philosophy of Science, 156, Springer Science & Business Media, ISBN 9780792325659</ref>

== اصل استقرای ریاضی ==
استقرای ریاضی بیان می‌کند که اگر <math>P(x)</math> به معنای درستی ویژگی <math>P</math> برای عدد <math>x</math> باشد، برای اینکه <math>P(x)</math> برای همهٔ اعداد طبیعی درست باشد، باید:<ref dir=ltr>{{harvcolnb| Spivak | 2006 | p=21}}</ref>

:# <math>P(1)</math> درست باشد.
:# با این فرض که <math>P(k)</math> درست است، بتوان ثابت کرد که <math>P(k + 1)</math> نیز درست است.
به‌ این‌ ترتیب با ترکیب شرط ۱ و ۲ (در حالت ویژه <math>k=1</math>) می‌توان گفت که <math>P(2)</math> هم درست است، در نتیجه بنابر شرط ۲ (در حالت ویژه <math>k=2</math>)، <math>P(3)</math> هم درست است. روشن است که با تکرار چندبارهٔ این کردارها می‌توان ویژگی <math>P</math> را برای هر عددی ثابت کرد، از این رو <math>P(k)</math> برای همهٔ اعداد <math>k</math> درست است.<ref dir=ltr>{{harvcolnb| Spivak | 2006 | p=21}}</ref>

فرمول ساده و کاربردی‌‌ای که برای محاسبهٔ <math>n</math> عدد اول طبیعی است را می‌توان با استقرای ریاضی ثابت کرد.
<math>1+2+3+\cdots+n = \frac{n(n+1)}{2}</math>

برای اثبات این فرمول، اول باید توجه کرد که فرمول برای <math>n = 1</math> درست است (<math>\frac{1(1+1)}{2}=1</math>). سپس فرض می‌شود که فرمول برای <math>n = k</math> درست باشد:<ref dir="ltr">{{harvcolnb| Spivak | 2006 | p=22}}</ref>
<math>1+2+3+\cdots+k = \frac{k(k+1)}{2}</math>{{سخ}}
آنگاه:{{سخ}}
<math>1+2+3+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1),</math>{{سخ}}
<math> = \frac{k(k+1)+2(k+1)}{2},</math>{{سخ}}
<math> = \frac{k^2+3k+2}{2},</math>{{سخ}}
<math> = \frac{(k+1)(k+2)}{2},</math> ([[اتحاد و تجزیه|تجزیهٔ دوجمله‌ای]] صورت){{سخ}}
بنابراین، فرمول برای <math>n = k+1</math> درست می‌باشد. بنابر استقرای ریاضی، این امر نشان‌دهندهٔ این است که فرمول بالا برای هر کدام از اعداد طبیعی درست است.<ref dir="ltr">{{harvcolnb| Spivak | 2006 | p=22}}</ref>

روش پدیداری‌تر ([[علوم صوری|صوری‌]]<nowiki/>‌تر) برای بیان استقرای ریاضی (بدون استفاده از «ویژگی»های عدد) این است که <math>A</math> یک [[مجموعه (ریاضی)|مجموعه]]ٔ [[مجموعه تهی|ناتُهی]] در نظر گرفته شود و شرط گذاشته شود که
:# عدد ۱ وندی از مجموعهٔ <math>A</math> باشد.
:# با این فرض که <math>k</math> وندی از مجموعهٔ <math>A</math> باشد، بتوان ثابت کرد که <math>k + 1</math> وندی از مجموعهٔ <math>A</math> است.
به‌این‌ترتیب ثابت می‌شود که <math>A</math> مجموعهٔ همهٔ اعداد طبیعی است.<ref dir="ltr">{{harvcolnb| Spivak | 2006 | p=22}}</ref>

شرط ناتهی بودن مجموعهٔ <math>A</math> به این دلیل است که [[مجموعه تهی]] «کوچک‌ترین عضو» ندارد و هر مجموعهٔ ناتهی «کوچک‌ترین عضو» دارد. این اصل را، که به نام [[اصل خوش‌ترتیبی]] آشنا است، می‌توان با استقرای ریاضی ثابت نمود. فرض کنیم که <math>A</math> «کوچک‌ترین عضو» نداشته باشد و <math>B</math> مجموعهٔ همهٔ اعداد طبیعی‌ باشد که عضو <math>A</math> نیستند. مشخص است که عدد ۱ عضو <math>A</math> نیست (چرا که اگر ۱ عضو <math>A</math> می‌بود، <math>A</math> «کوچک‌ترین عضو» داشت)، و افرون براین اگر ۱ تا <math>k</math> عضو <math>A</math> نباشند، <math>k+1</math> هم عضو <math>A</math> نیست (وگرنه <math>k+1</math> کوچک‌ترین عضو <math>A</math> می‌بود)، پس ۱ تا <math>k+1</math> در <math>A</math> نیستند. از این امر نتیجه می‌شود که ۱ تا <math>n</math> برای هر عدد طبیعی <math>n</math> عضو <math>A</math> نیستند و ثابت می‌شود که <math>A=\emptyset</math>.<ref dir="ltr">{{harvcolnb| Spivak | 2006 | p=23}}</ref>

همچنین می‌توان اصل استقرای ریاضی را با استفاده از [[اصل خوش‌ترتیبی]] ثابت کرد.<ref dir="ltr">{{harvcolnb| Spivak | 2006 | p=23}}</ref>
«اصل استقرای ریاضی کامل» را هم می‌توان به عنوان نتیجهٔ اصل استقرای ریاضی به‌دست آورد. این اصل زمانی به کار می‌آید که برای اثبات <math>P(k+1)</math>، علاوه بر <math>P(k)</math>، باید <math>P(l)</math> نیز برای همهٔ اعداد طبیعی <math>l \leq k</math> فرض شود. در این حالت بر اساس «اصل استقرای ریاضی کامل»، اگر <math>A</math> گردآورشی از اعداد طبیعی باشد،
:# عدد ۱ عضوی از گردآورشی A باشد.
:# با این فرض که <math>1,\ldots,k</math> عضوهای گردآورش <math>A</math> باشند بتوان ثابت کرد که <math>k + 1</math> عضوی از گردآورشی <math>A</math> است.
آنگاه <math>A</math> گردآورش همهٔ اعداد طبیعی است.<ref dir="ltr">{{harvcolnb| Spivak | 2006 | p=23}}</ref>

=== تعریف بازگشتی ===
[[تعریف بازگشتی]]، بگرتی (concept) نزدیک به اصل استقرای ریاضی است. برای مثال، عدد <math>n!</math> که <math>n</math> [[فاکتوریل]] خوانده می‌شود، به عنوان حاصل‌ضرب همهٔ اعداد طبیعی کوچک‌تر یا مساوی با <math>n</math> تعریف می‌شود:<ref dir=ltr>{{harvcolnb| Spivak | 2006 | p=23}}</ref>

<math>n!=1\cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n</math>

مفهوم فاکتوریل را می‌توان به شکل دقیق‌تر زیر بیان کرد:<ref dir=ltr>{{harvcolnb| Spivak | 2006 | p=23}}</ref>
:# <math>1!=1</math>
:# <math>n!=(n-1)! \cdot n</math>
حاصل‌جمع همهٔ اعداد طبیعی کوچک‌تر یا مساوی با <math>n</math> نیز (که با نماد <math>\sum_{i=1}^n k</math> نشان داده می‌شود) تعریفی بازگشتی است و می‌توان آن را به شکل زیر بیان کرد:<ref dir=ltr>{{harvcolnb| Spivak | 2006 | p=24}}</ref>
:# <math>\sum_{i=1}^1 a_i=1</math>
:# <math>\sum_{i=1}^n a_i=a_n + \sum_{i=1}^{n-1}a_i</math>

== استقرای کامل ==
نوعی از استقرای ریاضی، که استقرای کامل (یا استقرای قوی یا روش استقرای ارزش‌ها) نامیده می‌شود، می‌گوید که در مرحلۀ دوم ممکن است ما فرض کنیم که نه تنها این حالت برای <math>n = k</math> درست است، بلکه برای همۀ <math>n</math>-های کمتر یا مساوی با <math>k</math> نیز درست می‌باشد.<ref name=":0">{{یادکرد وب|عنوان=Strong Induction {{!}} Brilliant Math & Science Wiki|نشانی=https://brilliant.org/wiki/strong-induction/|وبگاه=brilliant.org|بازبینی=2023-01-21|کد زبان=en-us}}</ref> در واقع تفاوت این نوع از استقرا با استقرای ساده، تنها در فرض استقرا است.<ref name=":0" /><ref>موحد، درآمدی به منطق جدید (چاپ سیزدهم)، صفحۀ 127، علمی و فرهنگی.</ref>

استقرای کامل زمانی که موارد بیشماری از فرض استقرایی برای هر مرحلۀ استقرا نیاز است، بسیار مفید می‌باشد. برای نمونه، استقرای کامل می‌تواند برای اثبات فرمول [[اعداد فیبوناچی|فیبوناچی]] استفاده شود. فرمول فیبوناچی برای <math>n</math>-اُمین عدد با عبارت پایین برابر است (در اینجا <math>\varphi</math> (فی) همان [[عدد طلایی]] است که با  <math>\frac{\left(1+\sqrt 5\right)}{2}</math>  برابر است):
{{وسط‌چین}}
<math>F\left(n\right) = \frac{\varphi^n-(1-\varphi)^n}{\sqrt 5}=\frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}</math>
{{پایان وسط‌چین}}
درستی جملۀ عمومی را می‌توان از روش استقرای کامل ریاضی اثبات کرد.

برای <math>n=0</math> داریم:{{وسط‌چین}}
<math>F(0)=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{0}-\left(\frac{1-\sqrt{5}}{2}\right)^{0}}{\sqrt{5}}
=\frac{1-1}{\sqrt{5}}
= 0
</math>
{{پایان وسط‌چین}}برای <math>n=1</math> داریم:{{وسط‌چین}}
<math>F(1)=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{1}-\left(\frac{1-\sqrt{5}}{2}\right)^{1}}{\sqrt{5}}
=\frac{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}{\sqrt{5}}
=\frac{\frac{1+\sqrt{5}-1+\sqrt{5}}{2}}{\sqrt{5}}
=\frac{\frac{\sqrt{5}+\sqrt{5}}{2}}{\sqrt{5}}
=\frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}}
=\frac{{\sqrt{5}}}{\sqrt{5}}
=1
</math>
{{پایان وسط‌چین}}در نتیجه برای <math>n=0</math> و <math>n=1</math> فرمول درست است.

حال با فرض درستی رابطه برای <math>n \leq k</math>، می‌خواهیم فرمول را برای <math>n=k+1</math> ثابت کنیم.



برای <math>n=k</math> داریم:{{وسط‌چین}}
<math>F(k)=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{k}-\left(\frac{1-\sqrt{5}}{2}\right)^{k}}{\sqrt{5}}
</math>
{{پایان وسط‌چین}}

برای <math>n=k-1</math> داریم:{{وسط‌چین}}
<math>F(k-1)=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}}{\sqrt{5}}
</math>
{{پایان وسط‌چین}}حال فرمول را برای <math>F(k+1)
</math> که برآیه <math>F(k)</math> و <math>F(k-1)</math> است، ثابت می‌کنیم:{{وسط‌چین}}
<math>
\begin{align}
F\left(k+1\right) &= F\left(k\right)+F\left(k-1\right)\\
 &= \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{k}-\left(\frac{1-\sqrt{5}}{2}\right)^{k}}{\sqrt{5}}+\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}}{\sqrt{5}}\\
 &= \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{k}+\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k}-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}}{\sqrt{5}}\\
 &= \frac{\left(\left(\frac{1+\sqrt{5}}{2}\right)+1\right)\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\left(\frac{1-\sqrt{5}}{2}\right)+1\right)\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}}{\sqrt{5}}\\
 &= \frac{\left(\left(\frac{3+\sqrt{5}}{2}\right)\right)\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\left(\frac{3-\sqrt{5}}{2}\right)\right)\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}}{\sqrt{5}}\\
 &= \frac{\left(\left(\frac{1+\sqrt{5}}{2}\right)^{2}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\left(\frac{1-\sqrt{5}}{2}\right)^{2}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}}{\sqrt{5}}\\
 &= \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}}{\sqrt{5}}
\end{align}
</math>
{{پایان وسط‌چین}}یکی دیگر از اثبات‌ها با استقرای کامل از این فرضیه، که این حالت برای همۀ <math>n</math>-های کوچک‌تر به‌طور کامل درست است، استفاده می‌کند. حالتی که هر عدد طبیعی بزرگ‌تر از ۱ برآمده از (یک یا چند) عدد اول است را در نظر بگیرید و فرض کنید که برای یک <math>m</math> داده شده و <math>m>1</math>، برای همۀ <math>n>1</math>-های کوچک‌تر درست است. اگر <math>m</math> عدد اول باشد، پس قطعاً یک برآمده از اعداد اول است، و اگر نه، پس بنابر تعریف آن برآمدۀ <math>m = n_1\cdot n_2</math> است، که در آن هیچ‌یک از عوامل برابر با ۱ نیست. از این رو با <math>m</math> برابر نیست، و به همین ترتیب هر دو کوچک‌تر از <math>m</math> می‌باشند. حال فرض استقرا به <math>n_1</math> و <math>n_2</math> اعمال می‌شود، بنابراین هر یک برآمده‌ای از اعداد اول استند. پس <math>m</math> برآمده‌ای از اعداد اول است. برای نمونه یک برآمده از اعداد اول.

این تعمیم از استقرای کامل، برابر است با استقرای عادی ریاضی. فرض کنید که <math>P(n)</math> حالتی است که ما قصد داریم آن را با استقرای کامل اثبات کنیم. اجازه دهید <math>Q(n)</math> به معنای <math>P(m)</math> برای همۀ <math>m</math>-ها به‌طوری‌ که <math>0 \leq m</math> و <math>m \leq n</math> باشد. پس <math>Q(n)</math> برای همه <math>n</math>-ها درست است اگر و تنها اگر <math>P(n)</math> برای تمام <math>n</math>-ها درست باشد، و یک اثبات <math>P(n)</math> با استقرای کامل با یک اثبات <math>Q(n)</math> توسط استقرا (عادی) کاملاً یکسان است.

== تعریف صوری اصل استقرا ==
اصل استقرا در [[نظریه زبان‌ها|زبان صوری]] ریاضی به‌صورت زیر نوشته می‌شود.
{{چپ‌چین}}
: <math>(\forall P)[P(0) \land ( \forall k \in \mathbb{N}) (P(k) \Rightarrow P(k+1))] \Rightarrow ( \forall n \in \mathbb{N} ) [P(n)] </math>

{{پایان}}

== منابع ==
=== پانویس ===
{{پانویس|۲}}
* {{یادکرد
|فصل=
|کتاب=ساختمان‌های گسسته
|نویسنده = ریچارد جانسون با
|ترجمه=حسین ابراهیم‌زاده قلزم
|ناشر =سیمای دانش
|شهر=
|کوشش=
|ویرایش=پنجم
|صفحه=
|سال=۱۳۸۰
|شابک=
}}
* '''Introductory Mathematics: Algebra and Analysis''' by Geoff Smith
{{چپ‌چین}}
* {{cite book | last=Spivak | first=M. | title=Calculus | publisher=Cambridge University Press | series=Calculus | year=2006 | isbn=978-0-521-86744-3 | url=https://books.google.com/books?id=7JKVu_9InRUC&pg=PP1 | ref=harv |edition=3rd| access-date=2018-12-01}}
{{پایان چپ‌چین}}
{{بنیان‌ها-پاورقی}}
[[رده:استقرای ریاضی]]
[[رده:استدلال استقرایی]]
[[رده:برهان‌های ریاضیات]]
[[رده:منطق ریاضی]]
[[رده:نظریه برهان]]