לכל n\geq 1 טבעי, נסמן ב-A_n את קבוצת המספרים הטבעיים בעלי n ספרות, שבהם מופיעות רק הספרות 1,2,3,4,5,6, אך 1 לא מופיע בצמוד ל-1 ו-2 לא מופיע בצמוד ל-2.
למשל 12121\in A_5 ו-33215\in A_5 אבל 12114\not\in A_5 ו-12256\not\in A_5.
לכל n\geq 1 טבעי, נסמן a_n=|A_n| כאשר a_0 מוגדר כשווה ל-1 ובנוסף נסמן:
את b_n להיות מספר המספרים השייכים ל-A_n שבהם הספרה השמאלית ביותר היא 1.
את c_n להיות מספר המספרים השייכים ל-A_n שבהם הספרה השמאלית ביותר היא 2.
א. מצאו את a_1,a_2,a_3,b_1,b_2,c_1,c_2.
ב. לכל n\geq 2, הביעו את a_n בעזרת a_{n-1}, b_n ו-c_n.
ג. השתמשו בתוצאות של סעיף ב’ כדי למצוא יחס נסיגה a_n.
ד. פתרו את יחס הנסיגה וקבלו נוסחה מפורשת עבור a_n.
אשמח לעזרה בפתירת השאלה.