اصل استقرای ریاضی:
یک ردیف ازآجرهایی را درنظربگرید که روی انتهایشان به صورت عمودی ایستاده اند وفاصله ی بین آجرها به قدری کم است که اگریکی ازآن ها بیفتد، آجربعدی هم خواهد افتادو...
این مثال ازآجرها، استقرای ریاضی را - که یکی ازمهم ترین ابزارهای ریاضیات گسسته است - توصیف میکند. استقرای ریاضی موقعی استفاده میشود که ما یک دنباله ازجملات نامتناهی داریم،
وما میخواهیم ثابت کنیم که همه ی آن جملات درست (برقرار) هستند. درواقع جملات همان آجرها ودرستی جملات همان به زمین افتادن آجرهامت . اگرما بتوانیم ثابت کنیم که درستی هرجمله ی  درستی جمله ی  را نتیجه می دهد(نشان دهیم که فاصله ی بین آجرها به قدری کم است که افتادن یک آجر،باعث افتادن آجر بعدی خواهد شد. هم چنین اگربتوانیم نشان دهیم که جمله ی صحیح است،- آجراولی به زمین می افتد ، آن گاه ثابت کرده ایم که همه ی جملات برقرارهستند. (همه ی آجرها خواهند افتاد.)
اصل استقرای ریاضی یکی ازقدرتمندترین ابزارها وتکنیک های حل مسئله است . این اصل به شکل زیرکارمی کند.
فرض کنید  قضیه ای باشد که می خواهیم ثابت کنیم. همچنین فرض کنید شامل یک پارامتر  است که یک عدد طبیعی می باشد. به جای این که مستقیما درستی را به ازای تمام مقادیر ، ثابت کنیم؛ ما دو شرط زیر را اثبات می کنیم.
به ازای  برقرار است.
به ازای هر  ، از برقراری به ازای  ، برقراری را به ازای ، نتیجه می گیریم.
برقراری شرط 1 و 2، برای برقرای به ازای تمام مقادیر کافی است. شرط 1 و 2، برقراری به ازای  را نتیجه می دهند. برقراری به ازای و شرط 2، برقرای به ازای  را نتیجه می دهند و .... درحقیقت برای این که ثابت کنیم، جمله  درست است ابتدا ثابت می کنیم که جمله درست است و از درستی جمله درستی جمله  را نتیجه می گیریم و از درستی جمله درستی جمله  را نتیجه می گیریم و ... و سپس از درستی جمله  درستی جمله را نتیجه می گیریم. به این صورت به ازای هر  ، می توانیم ثابت کنیم که جمله درست است.
تحقیق درستی شرط 1، معمولا ساده است. ولی به هر حال باید درستی آن را چک کرد. و همچنین تحقیق درستی شرط 2، معمولا از اثبات مساله به طور مستقیم ساده تر است. و وقتی که این دو شرط را ثابت کردیم، طبق اصل استقرای ریاضی مساله را برای بینهایت مقدار، اثبات کرده ایم.
پیوندهای خارجی
http://olympiad.roshd.ir/computer/content/pdf/0005.pdf
همچنین ببینید
|
اصل استقرای ریاضی:
یک ردیف ازآجرهایی را درنظربگرید که روی انتهایشان به صورت عمودی ایستاده اند وفاصله ی بین آجرها به قدری کم است که اگریکی ازآن ها بیفتد، آجربعدی هم خواهد افتادو...
این مثال ازآجرها، استقرای ریاضی را - که یکی ازمهم ترین ابزارهای ریاضیات گسسته است - توصیف میکند. استقرای ریاضی موقعی استفاده میشود که ما یک دنباله ازجملات نامتناهی داریم،
وما میخواهیم ثابت کنیم که همه ی آن جملات درست (برقرار) هستند. درواقع جملات همان آجرها ودرستی جملات همان به زمین افتادن آجرهامت . اگرما بتوانیم ثابت کنیم که درستی هرجمله ی درستی جمله ی را نتیجه می دهد(نشان دهیم که فاصله ی بین آجرها به قدری کم است که افتادن یک آجر،باعث افتادن آجر بعدی خواهد شد. هم چنین اگربتوانیم نشان دهیم که جمله یصحیح است،- آجراولی به زمین می افتد ، آن گاه ثابت کرده ایم که همه ی جملات برقرارهستند. (همه ی آجرها خواهند افتاد.)
اصل استقرای ریاضی یکی ازقدرتمندترین ابزارها وتکیک های حل مسئله است . این اصل به شکل زیرکارمی کند.
فرض کنید قضیه ای باشد که می خواهیم ثابت کنیم. همچنین فرض کنید شامل یک پارامتر است که یک عدد طبیعی می باشد. به جای این که مستقیما درستی را به ازای تمام مقادیر ، ثابت کنیم؛ ما دو شرط زیر را اثبات می کنیم.
به ازای برقرار است.
به ازای هر ، از برقراری به ازای ، برقراری را به ازای ، نتیجه می گیریم.
برقراری شرط 1 و 2، برای برقرای به ازای تمام مقادیر کافی است. شرط 1 و 2، برقراری به ازای را نتیجه می دهند. برقراری به ازای و شرط 2، برقرای به ازای را نتیجه می دهند و .... درحقیقت برای این که ثابت کنیم، جمله درست است ابتدا ثابت می کنیم که جمله درست است و از درستی جمله درستی جمله را نتیجه می گیریم و از درستی جمله درستی جمله را نتیجه می گیریم و ... و سپس از درستی جمله درستی جمله را نتیجه می گیریم. به این صورت به ازای هر ، می توانیم ثابت کنیم که جمله درست است.
تحقیق درستی شرط 1، معمولا ساده است. ولی به هر حال باید درستی آن را چک کرد. و همچنین تحقیق درستی شرط 2، معمولا از اثبات مساله به طور مستقیم ساده تر است. و وقتی که این دو شرط را ثابت کردیم، طبق اصل استقرای ریاضی مساله را برای بینهایت مقدار، اثبات کرده ایم.
پیوندهای خارجی
http://olympiad.roshd.ir/computer/content/pdf/0005.pdf
همچنین ببینید
|
