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

استقرای ریاضی[3] (به انگلیسی: mathematical induction) شیوه‌ای برای اثبات قضایای ریاضی بر روی اعداد طبیعی است. این شیوه (استقراء ساده) از دو مرحله تشکیل شده‌است. در مرحله اول درستی قضیه ‎${\displaystyle P(n)}$‎ برای عددی پایه به اثبات می‌رسد. حال می‌دانیم که لااقل برای تعدادی از ابتدای اعداد طبیعی ‎${\displaystyle P(n)}$‎ درست است. اکنون با فرض آنکه ‎${\displaystyle P(k)}$‎ برای حکم درست باشد، درستی ‎${\displaystyle P(k+1)}$‎ را نتیجه می‌گیریم. این روش اثبات برای اولین بار توسط اقلیدس معرفی شده بود.

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

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

استقرای ریاضی بیان می‌کند که اگر ${\displaystyle P(x)}$ به معنای صدق ویژگی P برای عدد x باشد، برای اینکه ${\displaystyle P(x)}$ برای همهٔ اعداد طبیعی صدق کند باید:[4]

1. ${\displaystyle P(1)}$ صدق کند، و
2. با فرض اینکه ${\displaystyle P(k)}$ صدق می‌کند بتوان ثابت کرد ${\displaystyle P(k+1)}$ نیز صادق است.

به‌این‌ترتیب با ترکیب شرط ۱ و ۲ (در حالت خاص ${\displaystyle k=1}$) می‌توان گفت که ${\displaystyle P(2)}$ هم صادق است، در نتیجه بنابر شرط ۲ (در حالت خاص ${\displaystyle k=2}$)، ${\displaystyle P(3)}$ هم صادق است. واضح است که با تکرار چندبارهٔ این عملیات می‌توان ویژگی P را برای هر عددی ثابت کرد، ازین‌رو ${\displaystyle P(k)}$ برای همهٔ اعداد k صادق است.[5]

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

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

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

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

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

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

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

آنگاه A مجموعهٔ همهٔ اعداد طبیعی است.[11]

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

تعریف بازگشتی مفهومی نزدیک به اصل استقرای ریاضی است. برای مثال، عدد ${\displaystyle n!}$ (که «اِن فاکتوریل» خوانده می‌شود) به عنوان حاصل‌ضرب همهٔ اعداد طبیعی کوچکتر از یا برابر با n تعریف می‌شود:[12]

${\displaystyle n!=1\cdot 2\cdot 3\cdot \ldots \cdot (n-1)\cdot n}$

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

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

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

1. ${\displaystyle \sum _{i=1}^{1}a_{i}=1}$
2. ${\displaystyle \sum _{i=1}^{n}a_{i}=a_{n}+\sum _{i=1}^{n-1}a_{i}}$

استقرای کامل

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

استقرای کامل زمانی که موارد متعددی از فرض استقرائی برای هر مرحله استقرا مورد نیاز است، بسیار مفید است. به عنوان مثال، استقرای کامل می‌تواند برای اثبات فرمول فیبوناچی استفاده شود. فرمول فیبوناچی برای ${\displaystyle n}$ امین عدد با عبارت پایین برابر است (در اینجا ${\displaystyle \varphi }$ (فی) همان عدد طلایی است که با ${\displaystyle \left(1+{\sqrt {5}}\right)/2}$ برابر است):

${\displaystyle F\left(n\right)={\frac {\varphi ^{n}-(1-\varphi )^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}}$

درستی جمله عمومی را می‌توان از طریق استقرای کامل ریاضی اثبات کرد.

برای ${\displaystyle n=0}$ داریم:

${\displaystyle 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}$

برای ${\displaystyle n=1}$ داریم:

${\displaystyle 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}$

در نتیجه برای ${\displaystyle n=0}$ و ${\displaystyle n=1}$ فرمول درست است.

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

برای ${\displaystyle n=k}$ داریم:

${\displaystyle F(k)={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{k}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{k}}{\sqrt {5}}}}$

برای ${\displaystyle n=k-1}$ داریم:

${\displaystyle F(k-1)={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{k-1}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{k-1}}{\sqrt {5}}}}$

حال فرمول را برای ${\displaystyle F(k+1)}$ که حاصل‌جمع ${\displaystyle F(k)}$ و ${\displaystyle F(k-1)}$ است ثابت می‌کنیم"

${\displaystyle {\begin{aligned}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{aligned}}}$

یکی دیگر از اثبات‌ها با استقرای کامل از این فرضیه که این حالت برای همه nهای کوچکتر به‌طور کامل صحیح است، استفاده می‌کند. حالتی که هر عدد طبیعی بزرگتر از ۱ حاصل از (یک یا چند) عدد اول است را در نظر بگیرید و فرض کنید که برای یک m داده شده که m> 1، برای همه n> 1های کوچکتر صحیح است. اگر m اول باشد پس قطعاً یک محصول از اعداد اول است، و اگر نه، پس بنابه تعریف آن محصول m = n₁n₂ است، که در آن هیچ‌یک از عوامل برابر با ۱ نیست. از این رو با 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 توسط استقرا (عادی) کاملاً یکسان است.

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

اصل استقرا در زبان فرمال ریاضی به‌صورت زیر نوشته می‌شود.

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

منابع

پانویس

1. Matt DeVos, Mathematical Induction, Simon Fraser University
2. Gerardo con Diaz, Mathematical Induction بایگانی‌شده در ۲ مه ۲۰۱۳ توسط Wayback Machine, Harvard University
3. «استقرای ریاضی» [ریاضی] هم‌ارزِ «mathematical induction»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر پنجم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۷۸-۹۶۴-۷۵۳۱-۷۶-۴ (ذیل سرواژهٔ استقرای ریاضی)
4. Spivak 2006‏:‎21
5. Spivak 2006‏:‎21
6. Spivak 2006‏:‎22
7. Spivak 2006‏:‎22
8. Spivak 2006‏:‎22
9. Spivak 2006‏:‎23
10. Spivak 2006‏:‎23
11. Spivak 2006‏:‎23
12. Spivak 2006‏:‎23
13. Spivak 2006‏:‎23
14. Spivak 2006‏:‎24

• ریچارد جانسون با (۱۳۸۰)، ساختمان‌های گسسته، ترجمهٔ حسین ابراهیم‌زاده قلزم (ویراست پنجم)، سیمای دانش
• Introductory Mathematics: Algebra and Analysis by Geoff Smith

فهرست منابع

• Spivak, M. (2006). Calculus. Calculus (3rd ed.). Cambridge University Press. ISBN 978-0-521-86744-3. Retrieved 2018-12-01.