این بار هم در جهت بسط و گسترش توانایی‌های شما در حل مسائل تحلیلی، سری به مسابقه‌ای از جنس ترکیبیاتی زده‌ایم! بخوانید و لذت ببرید! ... سؤال همراه با جواب
سؤال
مسابقه‌ي این هفته در رابطه با یک پستچی زحمتکش است!
آقای پستچی زحمتکش، نامه‌ها را به 19 خانه‌ی ضلع شرقی خیابان مدرسه می‌برد. او متوجه شده است که هر روز از هر دو خانه‌ای که همسایه‌ي هم هستند حداکثر یکی نامه دارد و هر روز تعداد خانه‌هایی که پشت سر هم هستند و نامه ندارند بیش‌تر از دو تا نبوده است.
حال سؤال ما از شما این است که چند طریق متمایز برای رساندن نامه‌ها وجود دارد!؟
راهنمايي
این سؤال آن‌قدر ساده است که با همان راهنمایی‌اي که در قسمت خلاصه گفته شده، حل می‌شود!
جواب
رشته‌ي n رقمی از رقم‌های 0 و 1 را در نظر بگیرید که به‌ترتیب: 0 نشانه‌ی نامه نداشتن و 1 نشانه‌ی نامه داشتن باشد.
دنباله‌ای از 0 و 1ها را پذیرفتنی می‌نامیم هرگاه که در آن 11 و 000 وجود نداشته باشد، چون چنین رشته‌هایی برخلاف فرض‌های مسأله‌ي ما ساخته شده‌اند!
| - شرط اول | از دو خانه حداکثر یکی نامه دارد |
| - شرط دوم | هر روز تعداد خانه‌هایی که پشت سر هم هستند و نامه ندارند بیش از دو تا نیست |
حال فرض کنید 
که برابر با تعداد رشته‌های n رقمی قابل‌قبول باشد.
برابر با تعداد رشته‌های n رقمی قابل‌قبولی باشند که در آن‌ها 00 پس از اولین رقم 1 از سمت چپ آمده است و 
برابر با تعداد رشته‌های n رقمی باشد که در آن‌ها 01 پس از اولین رقم 1 در سمت چپ آمده است.
دقت داشته باشید که:
اگر  .
|
اگر اولین 100 از سمت چپ را حذف کنیم معلوم می‌شود که:
و اگر اولین 101 از سمت چپ را حذف کنیم معلوم می‌شود که:
در نتیجه اگر n بزرگ‌تر یا مساوی 5 باشد آن‌گاه:
به‌سادگی می‌توان حساب کرد که:
اکنون می‌توان از رابطه‌ی بازگشتی به‌دست آمده استفاده کرد و نتیجه گرفت که: