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

[nafise sadeghi]

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


این اصل بیان میکند اگر S زیرمجموعه ای ناتهی از اعداد طبیعی باشد به طوری که:
1) عدد یک عضو این مجموعه باشد. http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/11054568e26366f65a7378f3dd286d47.png
2) هرگاه عدد طبیعی n در مجموعه S باشد آنگاه n+1 نیز عضو این مجموعه باشد.http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/04cb7c42885319a02bd5b7125a8fcac3.png
میتوان تنیجه گرفت هر عدد طبیعی عضو S است و به عبارت دیگر S همان مجموعه اعداد طبیعی است.



لازم به توضیح است این اصل با پذیرش اصل خوش ترتیبی (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D8%A7%D8%B5%D9%84+%D8%AE%D9%88%D8% B4+%D8%AA%D8%B1%D8%AA%DB%8C%D8%A8%DB%8C) قابل اثبات است.
برهان:

برای اثبات از برهان خلف کمک می گیریم. به برهان خلف فرض می کنیم با مفروضات فوق مجموعه S برابر مجموعه اعداد طبیعی نباشد. پس مجموعه ای چون T وجود دارد که S=N-T. حال داریم: مجموعه T زیر مجموعه اعداد طبیعی است و ناتهی است(چرا؟) پس بنا بر اصل خوشترتیبی T دارا عضو مینیمم است چونhttp://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/38abb0a33e68edc5aabd65039f0bc02d.png واضح است که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/01ae3508b34257bac7b44cab3dc1d6ab.png و چون http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/11054568e26366f65a7378f3dd286d47.png پس داریم:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/f438cb4ec7ca7311aeed5cdbf27097ce.png و چون http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/38abb0a33e68edc5aabd65039f0bc02d.png برابر مینیمم مجموعه T است پس http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/60562fbe1ef773009ccd02113825dd2d.png و لذا از شرط دوم مجموعه S داریم:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d8a23832cdb9b7bd1d7f12bb5143ef86.png
که این تناقض است چون http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/85de52bd04899338cfad784483cc1794.png پس فرض خلف باطل و حکم(اصل اسقرا) برقرار است.



به این ترتیب برای اثبات برخی از مسائل و احکام ریاضی که درباره اعداد طبیعی می باشند می توان از اصل استقرای ریاضی استفاده کرد که اثبات به این روش، یک روش مستقیم در استدلال ریاضی است.
صورتی دیگر از اصل استقرای ریاضی:(اثبات به کمک اصل استقرای ریاضی)

همان گونه که گفته شد از اصل استقرا برای اثبات احکامی در مورد اعداد طبیعی استفاده می شود. حال روش اثبات را بوسیله این اصل بیان می کنیم:

اگر (P(n حکمی در مورداعداد طبیعی باشد (P(n برای هر عدد طبیعی n درست است اگر و فقط اگر:
1- حکم (P(1 درست باشد. به عبارت دیگر حکم برای n=1 برقرار باشد. (این مرحله را مرحله مبنای استقرا می گوییم.)
2- به ازای هر عدد طبیعی k از فرض درستی (P(k (فرض استقرا) بتوان درستی (P(k+1 (حکم استقرا) را نتیجه گرفت.

به عبارت دیگر نشان می دهیم عدد 1 در دامنه حکم است و چون هر k طبیعی که در دامنه حکم باشد k+1 هم در دامنه است می توان گفت دامنه حکم هر عدد طبیعی است و هر عدد طبیعی در حکم صدق می کند.


لازم به توضیح است که در اثبات به کمک اصل استقرا هر یک دو شرط فوق باید برقرار باشد تا بتوان درستی حکم را نتیجه گرفت

[nafise sadeghi]

مثال: نشان دهید برای هر عدد طبیعی n: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/464728a0ef366dd0ddef3f92a619d38b.png

پاسخ: اثبات را با استفاده از اصل استقرای ریاضی انجام می دهیم:
1- درستی حکم داده شده را برای n=1 بررسی می کنیم: (مرحله مبنایی استقرا)
سمت راست تساوی: 4
سمت چپ تساوی: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e59bb22601a0af2913eeb52a4c9ffcf1.png
پس برای n=1 طرفین تساوی دادهشده با هم برابر می شوند که نشان می دهد حکم برای n=1 درست است.
2- فرض می کنیم تساوی داده شده به ازای عدد طبیعی n=k برقرار باشد(فرض استقرا) یعنی:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1c93f1ebfbf3a040f03f36dff2b5663a.png
حال نشان میدهیم حکم برای n=k+1 هم برقرار است(حکم استقرا) یعنی:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ebe5384af4b1a5c9de6f1a8e43d06172.png
برای اثبات حکم استقرا از فرض استقرا کمک می گیریم. برای این کار به طرفین فرض استقرا عبارت http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/a0b2549e5b41202b241b643d5b6a443a.png را اضافه میکنیم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ceac6b2ddd7200c562723360d8d119f4.png
حال در سمت راست تساوی فوق داریم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6ff945e0826b542f13bb4735ae5e97f4.png
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/71f7cdaf23456474035f04122af0893f.png
پس نشان داده شد:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/58205b88f8eba1c1a5da9d461557ee8e.png
به این ترتیب بر طبق اصل استقرا حکم فوق برای هر n عضو اعداد طبیعی برقرار است.

[nafise sadeghi]

اصل استقراء تعمیم یافــته:
گاهی ممکن است با احکامی روبه رو شویم که برای n=1 برقرار نمی باشند و باید در بررسی شرط اول (مرحله مبنا) از عددی طبیعی بزرگتر استفاده کنیم به این ترتیب از اصل استقراء تعمیم یافــته استفاده می کنیم.


اصل استقرای تعمیم یافته:
اگر (P(nحکمی در باره اعداد طبیعی n (یا صحیح) باشد در صورتی که:
1- برای هر عدد طبیعی P(m) ، m>1 درست باشد
2- به ازای هر عدد طبیعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/016d1ed1bb5f5595eea90a75b37d95f4.png، از درستی (P(k درستی (P(k+1 نتیجه شود
آنگاه میتوان گفت حکم (P(n برای هر عدد طبیعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7552cf40bda9011bb4cecc558a0c8112.png برقرار است.



به این ترتیب در اثبات مسائل به کمک اصل استقرای تعمیم یافته باید m مناسب را برای بررسی شرط اول بیابیم.
مثال: نشان دهید عدد طبیعی مناسبی مانند m وجود دارد که برای هر عدد طبیعی n بزرگتر یا مساوی m داریـم: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/81c147312d78f9b1a234ad181d31019d.png

پاسخ: با قرار دادن مقادیر طبیعی برای m متوجه می شویم که m مناسب 3 است چرا که برای اولین بار حکم برای m=3 درست است. حال نشان میدهیم حکم برای هر عدد طبیعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2a85be57c9a7af00e4e5f4bb55509ffe.png برقرار است.
1- http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b57674248eaf66599a2d8137319c46ba.png
2- اکنون در این مرحله فرض (فرض استقرا) می کنیم نامساوی فوق برای هر عدد طبیعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/af7f1f03c9bdf15de0e65903d521e3f7.png درست باشد یعنی: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/9f1643965068705a774d509d5c9dc502.png
نشان میدهیم حکم داده شده برای (n=k+1 ،(k>2 درست است، یعنی:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/4aed5d50f91879a17196d072106e3049.png (حکم استقرا)
برای این منظور از فرض استقرا استفاده کرده و به طرفین فرض عدد 2 را اضافه می کنیم، داریم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2931c930e4e35d6f9bfe538f717ea284.png
حال با مقایسه نامساوی اخیر و حکم استقرا کافی است نشان دهیم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1ed8db7fb6069a72e7b35bd543f27fc0.png
برای این کار از اثبات بازگشتی کمک میگیریم:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b33cab51e632cb22460e8a1efe28e50e.png
مشاهده می شود نامساوی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c78494e57e91e5650761597b5631697a.png برای K>2 همواره درست است و چون تمامی روابط برگشت پذیرند، لذا http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1ed8db7fb6069a72e7b35bd543f27fc0.png برقرار بوده و به این ترتیب حکم برای هر عدد طبیعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/92cb72b594751044ac0b5bb4c982216a.png برقرار است.


لازم به توضیح است که از اصل استقرای ریاضی میتوان در اثبات برخی قضایای هندسه نیز استفاده

[nafise sadeghi]

مثال: نشان دهید در هر n ضلعی محدب تعداد قطرها برابر است با: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6f69af1d3a04c8b8f557d14d4d48fba4.png

پاسخ: می دانیم یک 3 ضلعی محدب، مثلث (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D9%85%D8%AB%D9%84%D8%AB) دارای هیچ قطری نمی باشد و چهار ضلعی محدب دارای
دو قطر است. به این ترتیب حکم را برای n>3 اثبات می کنیم. مرحله اول (مبنا) را با n=4 آغاز می کنیم:
1- http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/9623c893498a44b436f86ab0fc480552.png
حال فرض می کنیم که حکم برای n=k درست باشد، یعنی تعداد قطرهای هر k ضلعی محدب برابر باشد با:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/51a447c34c340948e8c2c14ba1dc7fbf.png
نشان می دهیم که حکم برای n=k+1 هم درست است، یعنی تعداد قطرهای هر k+1 ضلعی محدب برابر است با:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/525ffaced073ed216418fd35be944c3c.png
برای اثبات سعی می کنی به گونه ای از فرض استقرا استفاده کنیم. به این صورت که می دانیم که اگر به تعداد ضلعهای یک n ضلعی، یک ضلع اضافه کنیم یا به تعداد رئوس آن یک راس اضافه کنیم به تعداد قطرهای آن n-1 واحد اضافه می شود. لذا:



(k-1)+تعداد قطرهای k ضلعی محدب=تعداد قطرهای k+1 ضلعی محدب

بنابراین رابطه زیر برقرار است:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d460563fe61b28e161f434396f2c3eb6.png تعداد قطرهای k+1 ضلعی محدب


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5fc9c24af5ed9419fdc45589c6399240.png

[nafise sadeghi]

اصل استقرای قوی ریاضی:
صورتی دیگر از اصل استقرای ریاضی به شکل زیر مطرح می شود، که به اصل استقرای قوی ریاضی موسوم است. این اصل با اصل استقرای ریاضی و در نتیجه با اصل خوش ترتیبی (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D8%A7%D8%B5%D9%84+%D8%AE%D9%88%D8% B4+%D8%AA%D8%B1%D8%AA%DB%8C%D8%A8%DB%8C) معادل است.

اصل استقرای قوی ریاضی:
اگر S زیرمجموعه ای از اعداد طبیعی باشد، به طوری که:
1- عدد یک عضوی از مجموعه S باشد. http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/11054568e26366f65a7378f3dd286d47.png
2- اگر اعداد طبیعی کوچکتر از n در مجموعه S باشند، آنگاه n نیز عضو S باشد
در این صورت هر عدد طبیعی عضوی از S است و به عبارت دیگر S همان مجموعه اعداد طبیعی است.



لازم به تذکر است در ریاضیات برای اثبات احکام طبیعی بیشتر از اصل استقرای قوی ریاضی استفاده میشود.
روش اثبات احکام بوسیله اصل استقرای قوی ریاضی:

مراحل اثبات به کمک اصل استقرای قوی ریاضی به این صورت است:
1- درستی حکم را برای n=1 بررسی می کنیم.
2- نشان می دهیم که اگر حکم داده شده به ازا هر عدد طبیعی k که (k<n) برقرار باشد، نگاه برای n نیز درست است.

با یک مثال روش اثبات را بررسی می کنیم:

دنباله http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/27a0d63025743ce40dd439501af3f008.png به دنباله لوکا معروف است که در بین جملات آن رابطه بازگشتی زیر برقرار است:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/73c05616c8361c8cc473762976de610f.png

با استفاده از اصل استقرای قوی ریاضی نشان می دهیم که برای هر عدد طبیعی n را بطه زیر برقرار است:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/8ff2608cfef927ed2429cda73855b40a.png

پاسخ: اگر


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e8972cbe603f92867cc5700eff0b4572.png

آنگاه 1و2 عضوی از S می باشند زیرا نامساویهای:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b193619382d9b4eac4521b82fcdaf905.png

درست می باشند.(مرحله مبنا)
حال فرض میکنیم (فرض استقرا) http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/92cb72b594751044ac0b5bb4c982216a.png و به ازای هر عدد طبیعی k که k، k<n در مجموعه S قرار دارد. بنابراین:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2fc455b2157f85b00f9419b9f467dcdc.png

لذا چون http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/4e866f998e5feab520b18ed2761950b5.png پس:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/f04ef32f5df70ad48f400e66054dbc53.png


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/00dcc7b141b00219401d0850b04b74f0.png

و از طرفی دیگر:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/03ad0db637722d990e7d6d0373b2d08e.png

و لــذا:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/db2ef7df649cc3e1ced3b8d3106ee049.png

یعنی n نیز در مجموعه S قرار دارد، پس مجموعه S همان مجموعه اعداد طبیعی است. و لذا برای هر عدد طبیعی n حکم برقرار است.


لازم به توضیح است که از این اصل هم می توان برای اثبات برخی قضایای هندسه استفاده کرد و در ضمن می توان احکامی طبیعی که از یک هم آغاز نمی شوند را به این وسیله اثبات نمود.

[nafise sadeghi]

مثال: نشان دهید مجموع زوایای هر n ضلعی محدب برابر است با: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/119f6e37b29dd5dd25c4930a8b6c7d6e.png
پاسخ: می دانیم در این سوال n>2 زیرا n ضلعی حداقل از سه ضلع بوجود می آید.
به این ترتیب در مرحله مبنا حکم را برای n=3 بررسی می کنیم:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/f42f5896791d2c728e885164b27fd8b1.png

که همان گونه که می دانیم در هندسه نشان داده شده است که مجموع زوایای داخلی هر سه ضلعی محدب(مثلث) برابر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/3b29e4a83a6325350a0bc3cc212034f8.png می باشد.
اکنون فرض می کنیم (فرض استقرا) که مجموع زاویه های داخلی هر k ضلعی محدب که k<n برابر:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7836347b4bcea858f79f2fd4c6faaca2.png باشد.
اکنون نشان می دهیم (حکم استقرا) که مجموع زاویه های داخلی هر n ضلعی محدب نیز برابر:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/a2aa9788f32bd9c65984130e91faaeb5.png است.
برای این منظور n ضلعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7eb85faea91f3dcad674d2cf1d285ea6.png را در نظر می گیریم. قطر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ed379744acee47ea0fe647a3c5b80f84.png را رسم می کنیم تا n ضلعی به یک k ضلعی: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/93d2205a14aaf868fbdf78b7270d54ec.png و یک (n-k+2) ضلعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1865e505f3cf33a77a444062be145373.png تقسیم شود. مطابق فرض استقرا، مجموع زاویه های داخلی k ضلعی و (n-k+2) ضلعی به ترتیب برابر است با:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7836347b4bcea858f79f2fd4c6faaca2.png و http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b1ac1e45bd7f263cefd31467e6213543.png

بنابراین مجموع زاویه های داخلی n ضلعی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7eb85faea91f3dcad674d2cf1d285ea6.png برابر است با:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6dc6b950c985a5363c7a05fa087299cd.png

و لذا حکم برقرار است.







مزیت و محدودیت استدلال به کمک استقرای ریاضی:

استدلال به کمک استقرای ریاضی یک روش مستقیم برای اثبات و حل مسایل ریاضی محسوب می شود. این روش هم امتیازاتی دارد و هم محدودیت هایی. از مزایای استقرای ریاضی، مرحله ای بودن این روش است. یعنی عموما بدون نیاز به ابتکارهای زاید، مفید است و لذا شخص نتها لازوم دارد که برای استدلال خود، از مراحل مشخصی پیروی کند و برای این کار به بینش خاص نیاز نیست. مزیت دیگر این روش این است که استقرای ریاضی در حل مسایل خاصی که در آنها سایر روشهای عملی نیستند و یا بسیار مشکل اند، مفید است.
اما محدودیت استقرای ریاضی در این است که فقط برای مسائلی به کار می رود که با اعداد طبیعی سروکار دارند. لذا این روش اساسا یک روش تحقیق است، و تنها در اثبات نتایجی که درستی آنها را معلوم کرده یا حدس زده ایم، به کار می رود.