جلسهی 30: نوشتنِ اثباتِ استقرایی Writing an Induction Proof
استقرا مثل یک ردیفِ دومینوست: پایه و قدم. نوشتنِ کاملِ هر دو بخش، جمعِ عددهای فرد، کاشیکاریِ صفحهی بیخانه با کاشیهای L شکل، و استقرای قوی برای پول خرد کردن.
در این جلسه یاد میگیری
- یک اثباتِ استقرایی را با پایه، فرضِ استقرا و قدم کامل مینویسی.
- در قدم، دقیقاً از فرضِ استقرا استفاده میکنی.
- میدانی کِی استقرای قوی (چند حالتِ قبلی) لازم است.
درس
اثباتِ استقرایی سه تکه دارد که باید هر سه را بنویسی:
۱) پایه: حکم را برای کوچکترین حالت (مثلاً n = ۱) واقعاً بررسی کن. حتی اگر بدیهی است، بنویسش؛ طبقِ قوانینِ دورهی تابستانِ المپیاد، جا انداختنِ پایه میتواند بخشِ مهمی از نمره را ببرد.
۲) فرضِ استقرا: «فرض کنید حکم برای n = k درست باشد.»
۳) قدم: با استفاده از همین فرض، حکم را برای n = k + ۱ ثابت کن.
آنوقت مثل دومینو: ۱ درست است، پس ۲، پس ۳، …
مثال: ۱ + ۳ + ۵ + … + (۲n − ۱) = n².
پایه: n = ۱: ۱ = ۱² ✓.
فرض: ۱ + ۳ + … + (۲k − ۱) = k².
قدم: ۱ + ۳ + … + (۲k − ۱) + (۲k + ۱) = k² + ۲k + ۱ = (k + ۱)² ✓.
یک استقرای قشنگ: صفحهی ۲ⁿ × ۲ⁿ که یک خانهاش برداشته شده را میشود با کاشیهای L شکلِ سهخانهای پوشاند. قدم: صفحه را به چهار ربع تقسیم کن. خانهی برداشته در یکی از ربعهاست. یک کاشیِ L را درست وسطِ صفحه بگذار طوری که از هر یک از سه ربعِ دیگر یک خانه بپوشاند. حالا هر چهار ربع، صفحهی ۲ⁿ⁻¹ × ۲ⁿ⁻¹ با یک خانهی پوشیدهاند و طبقِ فرضِ استقرا پوشانده میشوند.
استقرای قوی: گاهی برای k + ۱ به چند حالتِ قبلی نیاز داری، نه فقط k. مثال: «هر مبلغِ ۸ تومان یا بیشتر را میشود با سکههای ۳ و ۵ تومانی پرداخت.» پایه: ۸ = ۳ + ۵، ۹ = ۳ + ۳ + ۳، ۱۰ = ۵ + ۵. قدم: برای هر n ≥ ۱۱، مبلغِ n − ۳ (که دستکم ۸ است) قابلِ پرداخت است؛ یک سکهی ۳ اضافه کن. چون قدم ۳ تا عقب میرود، سه پایه لازم بود.
اشتباه رایج: پایهی کافی نداشتن، یا در قدم از چیزی استفاده کردن که هنوز ثابت نشده.
چالشها
- Which Part Is the Base? (آسان)
- Check the Formula (آسان)
- Sum of the Odd Numbers (متوسط)
- Tiling with L Shapes (متوسط)
- Coins of Three and Five (سخت)
- Write the Strong Induction (سخت)
- Try It in Python: Amounts You Cannot Pay (سخت)