נוסחת נסיגה למספר הווקטורים הטרינאריים עם מספר זוגי של אפסים

[Gilad]

היי לכולם, אשמח לקבל עזרה עם השאלה הבאה:

מצאו נוסחה סגורה למספר הווקטורים הטרינאריים באורך n עם מספר זוגי של אפסים.

אני מבין שאני צריך להפריד למיקריים לפי תנאי כלשהו, אני פשוט לא מצליח להבין איזה תנאי בדיוק.
תודה לכולם על העזרה.

[Zeta]

היי גלעד,
נסמן ב-F(n) את מספר הווקטורים הטרינאריים באורך n עם מספר זוגי של אפסים. נסתכל על הספרה האחרונה בווקטור:

1. אם הספרה האחרונה היא 1 או 2, אז ב-n-1 המקומות הראשונים יש כבר מספר זוגי של אפסים. לכן מספר האפשרויות הוא F(n-1).

2. אם הספרה האחרונה היא 0, אז ב-n-1 המקומות הראשונים יש כבר מספר אי-זוגי של אפסים. לכן מספר האפשרויות הוא 3^{n-1}-F(n-1).

סה"כ נקבל (כאשר n\geq1):

F(n)=2\cdot F(n-1)+3^{n-1}-F(n-1)=F(n-1)+3^{n-1}

עם תנאי העצירה הבא: F(0)=1, שכן הווקטור הריק מקיים את הנדרש.