مسابقه‌ی شماره ۱۹۱
فرض کنید a(n) تعداد راه‌هایی باشد که عدد طبیعی n را می‌توان به‌شکل مجموع مرتبی از عددهای ۱ و ۲ نوشت. مثلا a(5)=8، زیرا:
| 1 + 1 + 1 + 1 + 1 |
= 5 |
| 1 + 1 + 1 + 2 |
= |
| 1 + 1 + ۲ + ۱ |
= |
| 1 + ۲ + 1 + ۱ |
= |
| ۲ + 1 + 1 + ۱ |
= |
| 1 + 2 + 2 |
= |
| ۲ + ۱ + 2 |
= |
| ۲ + 2 + ۱ |
= |
حال فرض کنید که b(n) تعداد راه‌هایی باشد که می‌توان n را به‌شکل مجموع مرتبی از عددهای صحیح بزرگ‌تر از ۱ نوشت. مثلا b(7)=8، زیرا:
| ۲ + ۲ + ۳ |
= 7 |
| ۲ + ۳ + ۲ |
= |
| ۳ + ۲ + ۲ |
= |
| 4 + ۳ |
= |
| 3 + 4 |
= |
| 5 + 2 |
= |
| 2 + 5 |
= |
| 7 |
= |
حال فرض کنید و اما سوال مسابقه، ثابت کنید:
| a(n) = b(n+2), n=1, 2, ... |