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

شیوه‌ای برای اثبات قضایای ریاضی بر روی اعداد طبیعی
(تغییرمسیر از استقراء ریاضی)

استقرای ریاضی[۳] (به انگلیسی: mathematical induction) شیوه‌ای برای استواری قضایای ریاضی بر روی اعداد طبیعی است. این شیوه (استقرای ساده) از دو مرحله تشکیل شده‌است. در مرحله اول، درستی قضیۀ‎ برای عددی پایه به استواری می‌رسد. اکنون می‌دانیم که کمینن برای شماری از اولین اعداد طبیعی ‎‎ درست است. اکنون با این انگار که ‎‎ برای حکم درست باشد، درستی ‎‎ را نتیجه می‌گیریم. این روش اثبات، برای اولین بار توسط اقلیدس معرفی شده بود.[نیازمند منبع]

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

تاریخچهویرایش

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

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

استقرای ریاضی بیان می‌کند که اگر   به معنای درستی ویژگی   برای عدد   باشد، برای اینکه   برای همهٔ اعداد طبیعی درست باشد، باید:[۵]

  1.   درست باشد.
  2. با این انگار که   درست است، بتوان ثابت کرد   نیز درست است.

به‌ این‌ ترتیب با ترکیب شرط ۱ و ۲ (در حالت ویژه  ) می‌توان گفت که   هم درست است، در نتیجه بنابر شرط ۲ (در حالت ویژه    هم درست است. روشن است که با تکرار چندبارهٔ این کردارها می‌توان ویژگی   را برای هر عددی ثابت کرد، از این رو   برای همهٔ اعداد   درست است.[۶]

فرمول ساده و کاربردی‌‌ای که برای محاسبهٔ   عدد نخست طبیعی است را می‌توان با استقرای ریاضی ثابت کرد.  

برای اثبات این فرمول، اول باید توجه کرد که فرمول برای ۱ درست است ( ). سپس فرض می‌شود که فرمول برای   عدد طبیعی نخست درست باشد:[۷] 
آنگاه:
 
 
 
  (تجزیهٔ دوجمله‌ای صورت)
بنابراین، فرمول برای   درست می‌باشد. بنابر استقرای ریاضی، این امر نشان‌دهندهٔ این است که فرمول بالا برای هر کدام از اعداد طبیعی درست است.[۸]

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

  1. عدد ۱ وندی از مجموعهٔ   باشد.
  2. با این انگار (فرض) که   وندی از مجموعهٔ   باشد بتوان ثابت کرد که   وندی از مجموعهٔ   است.

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

شرط ناتهی بودن مجموعهٔ   به این دلیل است که مجموعه تهی «کوچکترین عضو» ندارد و هر مجموعهٔ ناتهی «کوچکترین عضو» دارد. این اصل را، که به نام اصل خوش‌ترتیبی آشنا است، می‌توان با استقرای ریاضی ثابت نمود. فرض کنیم که   «کوچکترین عضو» نداشته باشد و   مجموعهٔ همهٔ اعداد طبیعی‌ باشد که عضو   نیستند. مشخص است که عدد ۱ عضو   نیست (چرا که اگر ۱ عضو   میبود   «کوچکترین عضو» داشت)، و افرون براین اگر ۱ تا   عضو   نباشند،   هم عضو   نیست (وگرنه   کوچک‌ترین عضو   می‌بود)، پس ۱ تا   در   نیستند. از این امر نتیجه می‌شود که ۱ تا   برای هر عدد طبیعی   عضو   نیستند و ثابت می‌شود که  .[۱۰]

همچنین می‌توان اصل استقرای ریاضی را با استفاده از اصل خوش‌ترتیبی ثابت کرد.[۱۱] «اصل استقرای ریاضی کامل» را هم می‌توان به عنوان نتیجهٔ اصل استقرای ریاضی به‌دست آورد. این اصل زمانی به کار می‌آید که برای اثبات  ، علاوه بر   باید   نیز برای همهٔ اعداد طبیعی   انگاریده شود. در این حالت بر اساس «اصل استقرای ریاضی کامل»، اگر   گردآورشی از اعداد طبیعی باشد،

  1. عدد ۱ عضوی از گردآورشی A باشد.
  2. با این انگار که   عضوهای گردآورش   باشند بتوان ثابت کرد که   عضوی از گردآورشی   است.

آنگاه   گردآورش همهٔ اعداد طبیعی است.[۱۲]

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

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

 

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

  1.  
  2.  

حاصل‌جمع همهٔ اعداد طبیعی کوچک‌تر یا مساوی با   نیز (که با نماد   نشان داده می‌شود) تعریفی بازگشتی است و می‌توان آن را به شکل زیر بیان کرد:[۱۵]

  1.  
  2.  

استقرای کاملویرایش

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

استقرای کامل زمانی که موارد بیشماری از انگاره استقرایی برای هر مرحله استقرا نیاز است، بسیار مفید است. برای نمونه، استقرای کامل می‌تواند برای اثبات فرمول فیبوناچی استفاده شود. فرمول فیبوناچی برای  -اُمین عدد با عبارت پایین برابر است (در اینجا   (فی) همان عدد طلایی است که با   برابر است):

 

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

برای   داریم:

 

برای   داریم:

 

در نتیجه برای   و   فرمول درست است.

حال با انگازه درستی رابطه برای  ، می‌خواهیم فرمول را برای   ثابت کنیم.


برای   داریم:

 

برای   داریم:

 

حال فرمول را برای   که برآیه   و   است، ثابت می‌کنیم:

 

یکی دیگر از اثبات‌ها با استقرای کامل از این فرضیه، که این حالت برای همۀ   های کوچک‌تر به‌طور کامل درست است، استفاده می‌کند. حالتی که هر عدد طبیعی بزرگ‌تر از ۱ برآمده از (یک یا چند) عدد اول است را در نظر بگیرید و به انگارید که برای یک   داده شده و  ، برای همه   های کوچک‌تر درست است. اگر   عدد اول باشد، پس قطعاً یک برآمده از اعداد اول است، و اگر نه، پس بنابر تعریف آن برآمده   است، که در آن هیچ‌یک از عوامل برابر با ۱ نیست. از این رو با   برابر نیست، و به همین ترتیب هر دو کوچک‌تر از   می‌باشند. حال فرض استقرا به   و   اعمال می‌شود، بنابراین هر یک برآمده ایی از اعداد اول استند. پس   برآمده ایی از اعداد اول است. برای نمونه یک برآمده از اعداد اول.

این تعمیم از استقرای کامل، برابر است با استقرای عادی ریاضی. فرض کنید که   حالتی است که ما قصد داریم آن را با استقرای کامل اثبات کنیم. اجازه دهید   به معنای   برای همه  ها به‌ طوری‌ که   و   باشد. پس   برای همه  -ها درست است اگر و تنها اگر   برای تمام  -ها درست باشد، و یک اثبات   با استقرای کامل با یک اثبات   توسط استقرا (عادی) کاملاً یکسان است.

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

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

 

منابعویرایش

پانویسویرایش

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