بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 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 − ۳⁩ (که دست‌کم ۸ است) قابلِ پرداخت است؛ یک سکه‌ی ۳ اضافه کن. چون قدم ۳ تا عقب می‌رود، سه پایه لازم بود.
اشتباه رایج: پایه‌ی کافی نداشتن، یا در قدم از چیزی استفاده کردن که هنوز ثابت نشده.

چالش‌ها

  1. Which Part Is the Base? (آسان)
  2. Check the Formula (آسان)
  3. Sum of the Odd Numbers (متوسط)
  4. Tiling with L Shapes (متوسط)
  5. Coins of Three and Five (سخت)
  6. Write the Strong Induction (سخت)
  7. Try It in Python: Amounts You Cannot Pay (سخت)

← جلسه‌ی 29: برهانِ خلف جلسه‌ی 31: ساختن و مثالِ نقض →