שאלת מבחן במתמטיקה בדידה - אוניברסיטת תל אביב 2021 - נסיגה

נסמן ב $a_n$ את מספר המחרוזות באורך $n$ מעל $\{0, 1, 2, 3, 4, 5\}$ בהן יש 2 תווים צמודים שלא מתחלקים ב 3. למשל 10403 מחרוזת שאינה חוקית, בעוד ש 13423 חוקית (2 ,4 לא מתחלקים ב 3). כתבו נוסחת נסיגה (כולל תנאי התחלה) על $a_n$. נמקו בקצרה. הערה: אין צורך לפתור את נוסחת הנסיגה.

רמז: חלקו את $\{0,...,5\}$ למתחלקים ב-3 ($X=\{0,3\}$) ושאינם ($Y=\{1,2,4,5\}$), ובנו נסיגה לפי התו השמאלי ביותר.

פתרון: נסמן $X = \{0, 3\}$, $Y = \{1, 2, 4, 5\}$. נספור את $a_n$ תוך הפרדה למקרים זרים ומשלימים בהתאם לתו השמאלי ביותר. **אם התו השמאלי ביותר הוא מתוך $X$** אז ניתן להשלים את המחרוזת ב $a_{n-1}$ אפשרויות (מחייבת לבנוא מחרוזת חוקית, וכל מחרוזות חוקית באחשבון). לכן יש $2a_{n-1}$ סדרות חוקיות כאלה (2 הוא עבור 0 ו-3). **אם התו השמאלי ביותר הוא מתוך $Y$**, אז נפריד למקרים בהתאם לתו השני משמאל. אם גם הוא מתוך $Y$ אז ניתן להשלים עם כל מחרוזת באורך $n-2$. כלומר במקרה זה יש $16 \cdot 6^{n-2}$ מחרוזות באורך $n-2$. ($4 \cdot 4 \cdot 6^{n-2}$) **אם התו השני משמאל הוא מתוך $X$**, אז ניתן להשלים את המחרוזת ב $a_{n-2}$ אפשרויות, סה"כ במקרה זה: $4 \cdot 2 \cdot a_{n-2} = 8 \cdot a_{n-2}$. סה"כ עבור $n \geq 2$: $$\boxed{a_n = 2a_{n-1} + 8a_{n-2} + 16 \cdot 6^{n-2}}$$ כאשר תנאי ההתחלה הם: $a_0 = a_1 = 0$. $\blacksquare$