استفاده از استقرا احتیاج به دقت بالایی دارد که با حل کردن مسایل مختلف می توان دقت کافی را به دست آورد. این فصل را با بررسی چند اثبات غلط و ذکر بعضی از علل خطا، به پایان می بریم.
بسیاری از اثبات های غلط از اینجا ناشی می شوند که یک شخص اعتقاد راسخی به درستی حکم مساله دارد و می خواهد به هر ترتیبی که شده، حکم مساله را بدیهی جلوه دهد و به حکم برسد. در استقرا معمولا این امر، به صورت اضافه کردن چند فرض به مساله که ظاهرا بدیهی به نظر می رسند، نتیجه می شود. در اثبات درستی حکم استقرا از فرض استقرا، از این مفروضات اضافی استفاده می کنیم، در حالی که درستی این مفروضات اضافی را ثابت نکرده ایم. به عنوان مثال فرض می کنیم که گراف همبند است در حالی که یادمان می رود، مساله را تنها برای گراف های همبند ثابت کرده ایم. یک چنین اشتباه ماهرانه ای خطرناک است و می تواند ما را به سوی اثبات های غلط بی شماری سوق دهد.
ثابت کنیم همه اسب ها هم رنگند.
اثبات. پایه استقرا درست است زیرا یک اسب با خودش هم رنگ است. حال فرض کنید حکم برای n درست باشد یعنی هر اسب هم رنگ باشند، اسب را در نظر بگیرید. می خواهیم ثابت کنیم همه این اسب هم رنگند.
اسب ها را از 1 تا شماره گذاری کنید. همه این اسب ها با اسب شماره یک، هم رنگند. حالا اسب های شماره را در نظر بگیرید؛ طبق فرض استقرا، تمام این اسب ها نیز با اسب شماره یک، هم رنگند. بنابراین همه اسب های شماره با اسب شماره یک، هم رنگند؛ درنتیجه تمام اسب با یکدیگر هم رنگند و حکم ثابت شد.
اشکال این اثبات این است که وقتی می خواستیم از ، را نتیجه بگیریم از این فرض که تعداد اسب ها حداقل سه تاست (یعنی ) استفاده کردیم. بنابراین از به نمی توان رسید و اثبات غلط است.
خط در صفحه داریم، ثابت کنیم که همگی آنها از یک نقطه می گذرند.
اثبات. حکم برای پایه استقرا ، درست است. زیرا هر دو خطی همرس هستند. حال فرض کنید حکم برای درست باشد یعنی هر خط دلخواه همرس باشند، ثابت می کنیم که هر خط همرس می باشند.
خط ها را از 1 تا شماره گذاری کنید. حال طبق فرض استقرا، خط های شماره همرسند و از نقطه ای مانند می گذرند. از طرف دیگر طبق فرض استقرا، خط های شماره نیز همرسند و از نقطه ای مانند می گذرند. چون خط های شماره همگی از نقاط و ، باید بگذرند، بنابراین این دو نقطه یکی می باشند و این خط همرسند. درنتیجه حکم ثابت شد.
اشکال اثبات فوق در پایه استقرا است و هم در نتیجه گرفتن حکم استقرا از روی فرض استقرا. اولا هر دو خطی همرس نیستند زیرا ممکن است موازی باشند. ثانیا در نتیجه گرفتن حکم استقرا از فرض استقرا، از این فرض استفاده کردیم که . (زیرا گفتیم چون و ، خطوط می گذرند، درنتیجه نقاط و یکسانند. ولی این به شرطی درست است که باشد.) بنابراین در اثبات فوق از ، نمی توان را نتیجه گرفت. در نتیجه اثبات غلط است.
اثبات. حکم برای پایه از استقرا ، برقرار است زیرا: . فرض کنید حکم به ازای درست باشد یعنی:
1. 2.آنگاه: 3.آنگاه: و حکم اثبات شد.
اشکال این اثبات جایی است که می خواهیم از عبارت (2)، عبارت (3) را نتیجه بگیریم. زیرا وقتی می توانیم طرفین را تقسیم بر کنیم که باشد. بنابراین نمی توان از ، را نتیجه گرفت.
یک اشتباه رایج دیگر در استفاده از روش قهقرایی می باشد. ما در عمل قهقرایی، را درست فرض می کنیم و با ساده کردن آن به می رسیم. در حالی که گاهی یادمان می رود این کار برگشت پذیر باشد. به عنوان مثال ما در حالت عادی از اینکه و می باشد. ولی همان طور که در مثال 20، در عمل قهقرایی دیدید بر عکس این عمل اشکالی ندارد یعنی ما از به و برسیم و هر یک از جملات و را ثابت کنیم، می توانیم در عمل برگشت درستی را ثابت کنیم.
بعضی از اشتباهات دیگر استقرا به این خاطر است که ما از روی یک مثال از ، یک مثال از را می سازیم و درستی حکم را برای مثال ساخته شده اثبات می کنیم و فراموش می کنیم که مثال ما یک مثال دلخواه نیست و ما حکم را به ازای تمام مقادیر ثابت نکرده ایم.
برخی دیگر از اشتباهات از اینجا ناشی می شود که ما اثبات پایه استقرا را نادیده می گیریم. برخی دیگر از اشتباهات این است که ما یادمان می رود که مثلاً که ما از درستی درستی را نتیجه می گیریم و بنابراین از درستی ، درستی و الی آخر را نتیجه می گیریم و اگر یکی از این موارد اشتباه باشد، اثبات ما نادرست می باشد. در زیر چند مثال در این زمینه می بینیم.
ثابت کنید در هر گراف مسطح همبند، . ( تعداد یال ها؛ تعداد رئوس و تعداد نواحی)
در اینجا یک اثبات اشتباه برای قضیه فوق می آوریم. دقت کنید که این قضیه درست است. (این قضیه را در فصل گراف های مسطح و فرمول اویلر، اثبات کرده ایم.)
اثبات. بر روی تعداد نواحی استقرا می زنیم. پایه استقرا که برقرار است. (در هر درخت ، درنتیجه .) حال فرض کنید حکم به ازای هر گراف مسطحی با ناحیه برقرار باشد، حکم را برای گراف های مسطح با ناحیه، ثابت می کنیم.
فرض کنید یک گراف مسطح با ناحیه باشد. دو راس دلخواه از رئوس یک وجه را در نظر بگیرید. یک وجه دلخواه را در نظر بگیرید، از وسط یک یال آن به وسط یک یال دیگر، یک یال رسم کنید. به این شکل یک گراف مسطح با ، و به دست می آید. با توجه به فرض استقرا ، درنتیجه و حکم ثابت شد.
اشکال اثبات بالا چیست؟ باز اشکال سر نتیجه گرفتن حکم از روی فرض استقرا است. اشکال این است که ما حکم را برای تمام گراف های مسطح با ناحیه ثابت نکردیم، بلکه تنها برای عده ای از آنها ثابت کردیم. اگر باور نمی کنید می توانید تحقیق کنید مثلاً تمام رئوسی که اضافه می شوند از درجه ی فرد می باشند و همواره درجه شان فرد باقی می ماند.
در هر گراف مسطح ساده با رأس ، که درجه ی تمام رئوس از یک بیش تر باشد، تعداد یال ها برابر است با .
اثبات. پایه ی استقرا ، درست است زیرا تنها گرافی که در شرایط مسئله صدق می کند، یک مثلث می باشد. (مثلث، دور به طول سه ساخته است. )
حال فرض کنید حکم مسئله به ازای درست باشد. گراف مسطح دلخواه ، با رأس را در نظر بگیرید که دارای شرایط مسئله باشد. چون ، ساده و مسطح است، پس حداقل دو رأس مانند ، روی مرز ناحیه خارجی گراف ، وجود دارند. حال از روی گراف ، گراف با راس را به این شکل می سازیم که یک راس مانند را به ناحیه خارجی ، اضافه می کنیم و آن را به رئوس و ، متصل می کنیم. درنتیجه گراف ، یک گراف ساده و مسطح راسی می باشد. تعداد یال های گراف ، دو عدد بیشتر از تعداد یال های گراف می باشد. ولی طبق فرض استقرا، گراف ، یال دارد؛ بنابراین گراف ، یال دارد. چون گراف یک گراف دلخواه بود، بنابراین گرافیک گراف خاص نیست و حکم ثابت شد.
مثال نقض حکم فوق، یک دور به طول چهار است یعنی . () ولی اشکال اثبات فوق چیست؟ پایه استقرا که به وضوح درست است. حکم هم تعریف شده است و هیچ ابهامی در آن نیست. پس باید اشکال در نتیجه گرفتن از باشد. نکته در اینجاست که ما از روی گراف راسی ، با روشی که گفته شد، تنها تعدادی از گراف های راسی را می سازیم. (مثلا نمی توان به این طریق گراف را، ساخت.) بنابراین ما تنها حکم را برای عده ای از گراف های راسی اثبات کردیم نه برای همه آنها.
برخی دیگر از اثبات های غلط از به کار بستن استقرا در اثبات یک چیز تعریف نشده، به وجود می آید. در زیر مثالی را از این حالت می آوریم.
می خواهیم ثابت کنیم هیچ آدم موداری در جهان وجود ندارد.
اثبات. با استقرا روی ثابت می کنیم «کسی که تار مو داشته باشد، مودار نیست.»
حکم به ازای پایه استقرا درست است زیرا کسی که با یک تار مو، مودار نمی شود. حال فرض کنید هیچ آدمی با تار مو، مودار نباشد. حال یک نفر مودار با تار مو را در نظر بگیرید. اگر یک موی این فرد را بکنیم که کچل نمی شود. بنابراین یک نفر آدم مودار با تار مو به دست آمد و این بر خلاف فرض استقرا می باشد. پس هیچ انسانی با تار مو، مودار نیست. درنتیجه هیچ آدم موداری در جهان یافت نمی شود.
اشکال اثبات فوق این است که مودار بودن، تعریف دقیقی ندارد و ما به صورت کیفی می گوییم که یک نفر مودار است یا نه، نه به صورت کمی.
یک ماتریس از اعداد صحیح نامنفی دارای این ویژگی است که به ازای هر درایه صفر آن، مجموع درایه های سطر و ستونی که شامل آن درایه هستند، حداقل است. نشان دهید که مجموع همه درایه های ماتریس مزبور حداقل است.
اثبات. به ازای حکم برقرار است. فرض کنید که حکم به ازای برقرار باشد. ماتریس را در نظر بگیرید. روشن است که اگر درایه صفری موجود نباشد، حکم درست است. هرگاه باشد، آنگاه طبق فرض، مجموع سطر و ستون دست کم و مجموع درایه های ماتریس که از حذف سطر و ستون به دست می آید،- طبق فرض استقرا- حداقل است. لذا نتیجه می شود که مجموع درایه های ماتریس اولیه حداقل
است و حکم با استقرا، ثابت شد.
اشکال اثبات فوق چیست؟ اشکال اثبات فوق این است که لزومی ندارد در ماتریس که از حذف سطر ام و ستون ام به وجود آمده است، به ازای هر درایه صفری، مجموع درایه های سطر و ستونی که شامل آن درایه هستند، حداقل باشد. بنابراین نمی توانیم از فرض استقرا استفاده کنیم.
در به کار بردن استقرا به موارد زیر توجه کنید:
استقرا را باید روی مسایلی که تعریف دقیقی دارند به کار برد. مثلا نمی توان در اثبات اینکه تمام مردم دنیا کچلند از استقرا استفاده کرد. زیرا کچل بودن تعریف دقیقی ندارد.
حتما برقراری پایه استقرا را چک کنید. مثلا اگر بخواهیم مثال 3 را به ازای هر اثبات کنیم، می توانیم به راحتی از فرض استقرا، حکم استقرا را نتیجه بگیریم ولی چون برقرار نیست نمی توان گفت که حکم برقرار است.
در گام استقرا، فرض های اضافی در مورد مقدار پارامتر نکنید. به عنوان مثال، مثال های 1، 2 و 3 از این دسته اند.
فرض های اضافی را بدون اثبات آنها، به مساله اضافه نکنید مثل همبند بودن در گراف ها که معمولا به فرض های مساله می توان اضافه کرد. ولی گاهی هم نمی توان این فرض را اضافه کرد. مثلا قضیه اویلر در گراف های مسطح، برای گراف های ناهمبند برقرار نیست.
دقت کنید که باید درستی حکم استقرا را به ازای تمام مقادیر از فرض استقرا، نتیجه بگیریم. با ساختن چند مثال و تحقیق درستی حکم در مورد آنها، نمی توان نتیجه گرفت که حکم به ازای همه مقادیر درست است. مثال های 4 و 5 از این دسته می باشند.
از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..
وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران رشد
اسب هم رنگ باشند، 
اسب را در نظر بگیرید. می خواهیم ثابت کنیم همه این 
را در نظر بگیرید؛ طبق فرض 
با اسب شماره یک، هم رنگند؛ درنتیجه تمام 
، 
را نتیجه بگیریم از این فرض که تعداد اسب ها حداقل سه تاست (یعنی 
) استفاده کردیم. بنابراین از 
به 
نمی توان رسید و اثبات غلط است.
، درست است. زیرا هر دو خطی همرس هستند. حال فرض کنید حکم برای 
همرسند و از نقطه ای مانند 
می گذرند. از طرف دیگر طبق فرض استقرا، خط های شماره 
نیز همرسند و از نقطه ای مانند 
می گذرند. چون خط های شماره 
. (زیرا گفتیم چون 
باشد.) بنابراین در اثبات فوق از 
را نتیجه گرفت. در نتیجه اثبات غلط است.
، برقرار است زیرا: 
. فرض کنید حکم به ازای 
کنیم که 
باشد. بنابراین نمی توان از 
و 
می باشد. ولی همان طور که در مثال 20، در 
به 
. (
تعداد یال ها؛ 
تعداد رئوس و 
تعداد نواحی)
، درنتیجه 
.) حال فرض کنید حکم به ازای هر گراف مسطحی با 
ناحیه برقرار باشد، حکم را برای گراف های مسطح با 
یک گراف مسطح با 
، 
و 
به دست می آید. با توجه به فرض استقرا 
و حکم ثابت شد.
ناحیه ثابت نکردیم، بلکه تنها برای عده ای از آنها ثابت کردیم. اگر باور نمی کنید می توانید تحقیق کنید مثلاً تمام رئوسی که اضافه می شوند از درجه ی فرد می باشند و همواره درجه شان فرد باقی می ماند.
.
، درست است زیرا تنها گرافی که در شرایط مسئله صدق می کند، یک مثلث می باشد. (مثلث، دور به طول سه ساخته است. 
)
، روی مرز ناحیه خارجی گراف 
با 
را به ناحیه خارجی 
و 
، متصل می کنیم. درنتیجه گراف 
یال دارد. چون گراف 
. (
) ولی اشکال اثبات فوق چیست؟ پایه استقرا که به وضوح درست است. حکم هم تعریف شده است و هیچ ابهامی در آن نیست. پس باید اشکال در نتیجه گرفتن 
راسی اثبات کردیم نه برای همه آنها.
از اعداد صحیح نامنفی دارای این ویژگی است که به ازای هر درایه صفر آن، مجموع درایه های سطر و ستونی که شامل آن درایه هستند، حداقل 
است.
برقرار باشد. ماتریس 
را در نظر بگیرید. روشن است که اگر درایه صفری موجود نباشد، حکم درست است. هرگاه 
باشد، آنگاه طبق فرض، مجموع سطر 
و ستون 
دست کم 
و مجموع درایه های ماتریس 
که از حذف سطر 
است. لذا نتیجه می شود که مجموع درایه های ماتریس 
ام به وجود آمده است، به ازای هر درایه صفری، مجموع درایه های سطر و ستونی که شامل آن درایه هستند، حداقل 
باشد. بنابراین نمی توانیم از فرض استقرا استفاده کنیم.
از فرض استقرا، نتیجه بگیریم. با ساختن چند مثال و تحقیق درستی حکم در مورد آنها، نمی توان نتیجه گرفت که حکم به ازای همه مقادیر درست است. مثال های 4 و 5 از این دسته می باشند.