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

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از اصل استقرا)
پرش به ناوبری پرش به جستجو

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

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

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

  1. صدق کند، و
  2. با فرض اینکه صدق می‌کند بتوان ثابت کرد نیز صادق است.

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

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



(تجزیهٔ دوجمله‌ای صورت)
بنابراین فرمول برای صدق می‌کند. بنابر استقرای ریاضی این امر نشان‌دهندهٔ این است که فرمول فوق برای هر کدام از اعداد طبیعی صادق است.[۴]

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

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

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

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

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

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

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

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

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

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

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

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

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

استقرای کامل زمانی که موارد متعددی از فرض استقرائی برای هر مرحله استقرا مورد نیاز است، بسیار مفید است. به عنوان مثال، استقرای کامل می‌تواند برای نشان دادن (Fn = (φn – ψn) / (φ – ψ استفاده شود که در آن Fn عدد فیبوناچی n ام، φ = (۱ + √۵) / ۲ (نسبت طلایی) و ψ = (۱ - √۵) / ۲ ریشه‌های چندجمله‌ای x2 - x - 1 می‌باشند. با استفاده از این واقعیت که Fn + 2 = Fn+1 + Fn برای هر n ∈ N، تأیید فوق را می‌توان با محاسبه مستقیم Fn+2 اگر فرض کنیم که در حال حاضر برای هر دوی Fn + 1 Fn صحیح است، تعریف کرد. برای تکمیل اثبات، تعریف باید در دو حالت پایه n = ۰ و n = ۱ تأیید شود.

یکی دیگر از اثبات‌ها با استقرای کامل از این فرضیه که این حالت برای همه nهای کوچکتر به‌طور کامل صحیح است، استفاده می‌کند. حالتی که هر عدد طبیعی بزرگتر از ۱ حاصل از (یک یا چند) عدد اول است را در نظر بگیرید و فرض کنید که برای یک m داده شده که m > 1، برای همه n > 1های کوچکتر صحیح است. اگر m اول باشد پس قطعاً یک محصول از اعداد اول است، و اگر نه، پس بنابه تعریف آن محصول m = n1n2 است، که در آن هیچ‌یک از عوامل برابر با ۱ نیست. از این رو با m برابر نیست، و به همین ترتیب هر دو کوچکتر از m می‌باشند. حال فرض استقرا به n1 و n2 اعمال می‌شود، بنابراین هر یک محصولی از اعداد اول‌اند. پس m محصولی از محصولات اعداد اول است. به عنوان مثال یک محصول از اعداد اول.

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

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

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

منابع[ویرایش]

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

  1. Spivak 2006‏:‎21
  2. Spivak 2006‏:‎21
  3. Spivak 2006‏:‎22
  4. Spivak 2006‏:‎22
  5. Spivak 2006‏:‎22
  6. Spivak 2006‏:‎23
  7. Spivak 2006‏:‎23
  8. Spivak 2006‏:‎23
  9. Spivak 2006‏:‎23
  10. Spivak 2006‏:‎23
  11. Spivak 2006‏:‎24
  • ریچارد جانسون با. ساختمان‌های گسسته. ترجمهٔ حسین ابراهیم‌زاده قلزم. ویرایش پنجم. چاپ اول. سیمای دانش، ۱۳۸۰. 
  • Introductory Mathematics: Algebra and Analysis by Geoff Smith

فهرست منابع[ویرایش]