چند رشتهی دودویی (از ۰ و ۱) به طول $6$ وجود دارد که در آن دو رقم $1$ پشت سر هم نیامده باشند؟
راهنمایی
$a_n$ را تعداد رشتههای خوب به طول $n$ بگیر و به رقم آخر نگاه کن.
پاسخ و راهحل
پاسخ: $21$
اگر رشته به $0$ ختم شود، بقیهاش هر رشتهی خوب به طول $n-1$ است؛ اگر به $1$ ختم شود، رقم قبلی حتماً $0$ است. پس $a_n = a_{n-1} + a_{n-2}$ با $a_1=2$ و $a_2=3$.
دنباله: $2, 3, 5, 8, 13, 21$ ← پاسخ $21$.