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