||V{maketoc}||
^@#16:
!اصل استقرای ریاضی:
یک ردیف ازآجرهایی را درنظربگرید که روی انتهایشان به صورت عمودی ایستاده اند وفاصله ی بین آجرها به قدری کم است که اگریکی ازآن ها بیفتد، آجربعدی هم خواهد افتادو...
::{picture=img/daneshnameh_up/1/10/comm0002a.JPG}::
این مثال ازآجرها، استقرای ریاضی را - که یکی ازمهم ترین ابزارهای ریاضیات گسسته است - توصیف میکند. استقرای ریاضی موقعی استفاده میشود که ما یک دنباله ازجملات نامتناهی داریم،
@@{TEX()} {p(1),p(2),\cdots ,p(n),p(n+1),\cdots} {TEX}@@
وما میخواهیم ثابت کنیم که همه ی آن جملات درست (برقرار) هستند. درواقع جملات همان آجرها ودرستی جملات همان به زمین افتادن آجرهامت . اگرما بتوانیم ثابت کنیم که درستی هرجمله ی {TEX()} {p(n)} {TEX} درستی جمله ی {TEX()} {p(n+1)} {TEX} را نتیجه می دهد(نشان دهیم که فاصله ی بین آجرها به قدری کم است که افتادن یک آجر،باعث افتادن آجر بعدی خواهد شد. هم چنین اگربتوانیم نشان دهیم که جمله ی{TEX()} {p(1)} {TEX}صحیح است،- آجراولی به زمین می افتد ، آن گاه ثابت کرده ایم که همه ی جملات برقرارهستند. (همه ی آجرها خواهند افتاد.)
اصل استقرای ریاضی یکی ازقدرتمندترین ابزارها وتکیک های حل مسئله است . این اصل به شکل زیرکارمی کند.
فرض کنید {TEX()} {T} {TEX} قضیه ای باشد که می خواهیم ثابت کنیم. همچنین فرض کنید {TEX()} {T} {TEX} شامل یک پارامتر {TEX()} {n} {TEX} است که {TEX()} {n} {TEX} یک عدد طبیعی می باشد. به جای این که مستقیما درستی {TEX()} {T} {TEX}را به ازای تمام مقادیر {TEX()} {n} {TEX}، ثابت کنیم؛ ما دو شرط زیر را اثبات می کنیم.
{TEX()} {T} {TEX}به ازای {TEX()} {n=1} {TEX} برقرار است.
به ازای هر {TEX()} {n>1} {TEX}، از برقراری {TEX()} {T} {TEX} به ازای {TEX()} {n-1} {TEX}، برقراری {TEX()} {T} {TEX}را به ازای {TEX()} {n} {TEX}، نتیجه می گیریم.
برقراری شرط 1 و 2، برای برقرای {TEX()} {T} {TEX}به ازای تمام مقادیر {TEX()} {T} {TEX}کافی است. شرط 1 و 2، برقراری {TEX()} {T} {TEX}به ازای {TEX()} {n=2} {TEX} را نتیجه می دهند. برقراری {TEX()} {T} {TEX}به ازای {TEX()} {n=2} {TEX} و شرط 2، برقرای {TEX()} {T} {TEX}به ازای {TEX()} {n=3} {TEX} را نتیجه می دهند و .... درحقیقت برای این که ثابت کنیم، جمله {TEX()} {p(k)} {TEX} درست است ابتدا ثابت می کنیم که جمله {TEX()} {p(1)} {TEX} درست است و از درستی جمله {TEX()} {p(1)} {TEX} درستی جمله {TEX()} {p(2)} {TEX} را نتیجه می گیریم و از درستی جمله {TEX()} {p(2)} {TEX} درستی جمله {TEX()} {p(3)} {TEX} را نتیجه می گیریم و ... و سپس از درستی جمله {TEX()} {p(k-1)} {TEX} درستی جمله {TEX()} {p(k)} {TEX} را نتیجه می گیریم. به این صورت به ازای هر {TEX()} {k\ge 1} {TEX}، می توانیم ثابت کنیم که جمله {TEX()} {p(k)} {TEX} درست است.
تحقیق درستی شرط 1، معمولا ساده است. ولی به هر حال باید درستی آن را چک کرد. و همچنین تحقیق درستی شرط 2، معمولا از اثبات مساله به طور مستقیم ساده تر است. و وقتی که این دو شرط را ثابت کردیم، طبق اصل استقرای ریاضی مساله را برای بینهایت مقدار، اثبات کرده ایم.#@^