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

استقرای ریاضی را به‌صورت غیرصوری با ارجاع به تاثیر ترتیبی افتادن دومینوها می‌توان نشان داد.

استقرای ریاضی الگو:به انگلیسی شیوه‌ای برای اثبات قضایای ریاضی راجع به اعداد طبیعی است. این شیوه (استقرای ساده) از دو مرحله تشکیل شده‌است. در مرحلۀ اول، درستی قضیۀ الگو:چر$P(n)$الگو:چر برای عددی پایه به اثبات می‌رسد. اکنون می‌دانیم که حداقل برای شماری از اولین اعداد طبیعی الگو:چر$P(n)$الگو:چر درست است. اکنون با این فرض که الگو:چر$P(k)$الگو:چر برای حکم درست باشد، درستی الگو:چر$P(k+1)$الگو:چر را نتیجه می‌گیریم. این روش اثبات، برای اولین بار توسط اقلیدس معرفی شده بود.

تاریخچه

در یونان باستان مثال‌های منطقی‌ای از استقرا را می‌توان دید، ولی اولین کاربرد ریاضی استقرا در حدود ۱۰۰۰ میلادی توسط ابوبکر کرجی هنگام کار بر روی بسط دو جمله‌ای یافته می‌شود.

اصل استقرای ریاضی

استقرای ریاضی بیان می‌کند که اگر $P(x)$ به معنای درستی ویژگی $P$ برای عدد $x$ باشد، برای اینکه $P(x)$ برای همهٔ اعداد طبیعی درست باشد، باید:

1. $P(1)$ درست باشد.
2. با این فرض که $P(k)$ درست است، بتوان ثابت کرد که $P(k+1)$ نیز درست است.

به‌ این‌ ترتیب با ترکیب شرط ۱ و ۲ (در حالت ویژه $k=1$) می‌توان گفت که $P(2)$ هم درست است، در نتیجه بنابر شرط ۲ (در حالت ویژه $k=2$)، $P(3)$ هم درست است. روشن است که با تکرار چندبارهٔ این کردارها می‌توان ویژگی $P$ را برای هر عددی ثابت کرد، از این رو $P(k)$ برای همهٔ اعداد $k$ درست است.

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

برای اثبات این فرمول، اول باید توجه کرد که فرمول برای $n=1$ درست است ($\frac{1(1+1)}{2}=1$). سپس فرض می‌شود که فرمول برای $n=k$ درست باشد: $1+2+3+\cdots +k=\frac{k(k+1)}{2}$الگو:سخ آنگاه:الگو:سخ $1+2+3+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1),$الگو:سخ $=\frac{k(k+1)+2(k+1)}{2},$الگو:سخ $=\frac{k^2+3k+2}{2},$الگو:سخ $=\frac{(k+1)(k+2)}{2},$ (تجزیهٔ دوجمله‌ای صورت)الگو:سخ بنابراین، فرمول برای $n=k+1$ درست می‌باشد. بنابر استقرای ریاضی، این امر نشان‌دهندهٔ این است که فرمول بالا برای هر کدام از اعداد طبیعی درست است.

روش پدیداری‌تر (صوری‌‌تر) برای بیان استقرای ریاضی (بدون استفاده از «ویژگی»های عدد) این است که $A$ یک مجموعهٔ ناتُهی در نظر گرفته شود و شرط گذاشته شود که

1. عدد ۱ وندی از مجموعهٔ $A$ باشد.
2. با این فرض که $k$ وندی از مجموعهٔ $A$ باشد، بتوان ثابت کرد که $k+1$ وندی از مجموعهٔ $A$ است.

به‌این‌ترتیب ثابت می‌شود که $A$ مجموعهٔ همهٔ اعداد طبیعی است.

شرط ناتهی بودن مجموعهٔ $A$ به این دلیل است که مجموعه تهی «کوچک‌ترین عضو» ندارد و هر مجموعهٔ ناتهی «کوچک‌ترین عضو» دارد. این اصل را، که به نام اصل خوش‌ترتیبی آشنا است، می‌توان با استقرای ریاضی ثابت نمود. فرض کنیم که $A$ «کوچک‌ترین عضو» نداشته باشد و $B$ مجموعهٔ همهٔ اعداد طبیعی‌ باشد که عضو $A$ نیستند. مشخص است که عدد ۱ عضو $A$ نیست (چرا که اگر ۱ عضو $A$ می‌بود، $A$ «کوچک‌ترین عضو» داشت)، و افرون براین اگر ۱ تا $k$ عضو $A$ نباشند، $k+1$ هم عضو $A$ نیست (وگرنه $k+1$ کوچک‌ترین عضو $A$ می‌بود)، پس ۱ تا $k+1$ در $A$ نیستند. از این امر نتیجه می‌شود که ۱ تا $n$ برای هر عدد طبیعی $n$ عضو $A$ نیستند و ثابت می‌شود که $A=\mathrm{\varnothing }$.

همچنین می‌توان اصل استقرای ریاضی را با استفاده از اصل خوش‌ترتیبی ثابت کرد. «اصل استقرای ریاضی کامل» را هم می‌توان به عنوان نتیجهٔ اصل استقرای ریاضی به‌دست آورد. این اصل زمانی به کار می‌آید که برای اثبات $P(k+1)$، علاوه بر $P(k)$، باید $P(l)$ نیز برای همهٔ اعداد طبیعی $l\le k$ فرض شود. در این حالت بر اساس «اصل استقرای ریاضی کامل»، اگر $A$ گردآورشی از اعداد طبیعی باشد،

1. عدد ۱ عضوی از گردآورشی A باشد.
2. با این فرض که $1,\dots ,k$ عضوهای گردآورش $A$ باشند بتوان ثابت کرد که $k+1$ عضوی از گردآورشی $A$ است.

آنگاه $A$ گردآورش همهٔ اعداد طبیعی است.

تعریف بازگشتی

تعریف بازگشتی، بگرتی (concept) نزدیک به اصل استقرای ریاضی است. برای مثال، عدد $n!$ که $n$ فاکتوریل خوانده می‌شود، به عنوان حاصل‌ضرب همهٔ اعداد طبیعی کوچک‌تر یا مساوی با $n$ تعریف می‌شود:

$n!=1\cdot 2\cdot 3\cdot \dots \cdot (n-1)\cdot n$

مفهوم فاکتوریل را می‌توان به شکل دقیق‌تر زیر بیان کرد:

1. $1!=1$
2. $n!=(n-1)!\cdot n$

حاصل‌جمع همهٔ اعداد طبیعی کوچک‌تر یا مساوی با $n$ نیز (که با نماد $\sum _{i=1}^{n}k$ نشان داده می‌شود) تعریفی بازگشتی است و می‌توان آن را به شکل زیر بیان کرد:

1. $\sum _{i=1}^1{a}_i=1$
2. $\sum _{i=1}^n{a}_i=a_n+\sum _{i=1}^{n-1}{a}_i$

استقرای کامل

نوعی از استقرای ریاضی، که استقرای کامل (یا استقرای قوی یا روش استقرای ارزش‌ها) نامیده می‌شود، می‌گوید که در مرحلۀ دوم ممکن است ما فرض کنیم که نه تنها این حالت برای $n=k$ درست است، بلکه برای همۀ $n$-های کمتر یا مساوی با $k$ نیز درست می‌باشد. در واقع تفاوت این نوع از استقرا با استقرای ساده، تنها در فرض استقرا است.

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

برای $n=0$ داریم:الگو:وسط‌چین $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$ الگو:پایان وسط‌چینبرای $n=1$ داریم:الگو:وسط‌چین $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$ الگو:پایان وسط‌چیندر نتیجه برای $n=0$ و $n=1$ فرمول درست است.

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

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

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

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

تعریف صوری اصل استقرا

اصل استقرا در زبان صوری ریاضی به‌صورت زیر نوشته می‌شود. الگو:چپ‌چین

$(\mathrm{\forall }P)[P(0)\wedge (\mathrm{\forall }k\in \mathbb{N})(P(k)\Rightarrow P(k+1))]\Rightarrow (\mathrm{\forall }n\in \mathbb{N})[P(n)]$

منابع

پانویس

• الگو:یادکرد
• Introductory Mathematics: Algebra and Analysis by Geoff Smith

• الگو:Cite book