منو
 کاربر Online
788 کاربر online

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

چاپ
علوم ریاضی > علو م رایانه




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

یک ردیف ازآجرهایی را درنظربگرید که روی انتهایشان به صورت عمودی ایستاده اند وفاصله ی بین آجرها به قدری کم است که اگریکی ازآن ها بیفتد، آجربعدی هم خواهد افتادو...
img/daneshnameh_up/1/10/comm0002a.JPG

این مثال ازآجرها، استقرای ریاضی را - که یکی ازمهم ترین ابزارهای ریاضیات گسسته است - توصیف میکند. استقرای ریاضی موقعی استفاده میشود که ما یک دنباله ازجملات نامتناهی داریم،

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

پیوندهای خارجی

http://olympiad.roshd.ir/computer/content/pdf/0005.pdf


همچنین ببینید






تعداد بازدید ها: 24780


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..