סדרה “משובחת” היא סדרה סופית של סימנים הלקוחים מבין ששת הסימנים הבאים:
הספרות 0,1, וסימני הפעולות +,־,*,/, בכפוף לתנאים הבאים:
הסדרה נפתחת ומסתיימת בספרה.
הסדרה אינה מכילה שני סימני פעולה רצופים.
לדוגמא: הסדרה 0100+01/000 הינה חוקית אבל הסדרה 1-+01 אינה חוקית שכן היא מפרה את תנאי מספר 2. הסדרה הריקה אינה חוקית שכן היא מפרה את תנאי מספר 1.
יהי a_n מספר הסדרות החוקיות שאורכן בדיוק n.
מצאו נוסחה רקורסיבית ותנאי התחלה מספיקים עבור a_n.
אשמח לעזרה עם התרגיל הנ"ל, אני תקוע עליו כבר מספר שעות.
תודה רבה על העזרה.
על-פי התנאים, האיבר הראשון בסדרה חייב להיות ספרה, ולכן יש שתי אפשרויות לבחור אותו.
נפריד למקרים לפי האיבר השני:
אם האיבר השני הוא ספרה, אז עלינו לבחור את כל n-1 האיברים הבאים כך שתתקבל סדרה שמתחילה בספרה, נגמרת בספרה, ואין בה שני סימנים עוקבים ולכן a_{n-1} אפשרויות.
אם האיבר השני הוא סימן פעולה, אז יש 4 אפשרויות לבחור אותו. אחריו חייבת להופיע ספרה. אז עלינו לבחור את כל n-2 האיברים הבאים כך שתתקבל סדרה שמתחילה בספרה, נגמרת בספרה, ואין בה שני סימנים עוקבים ולכן a_{n-2} אפשרויות.
סה"כ נקבל את הנוסחה הרקורסיבית הבאה:
a_{n}=2a_{n-1}+8a_{n-2}
עם תנאי התחלה הבאים: a_{0}=0 (הסדרה הריקה לא מקיימת את הדרישה) ו-a_{1}=2 (סדרה באורך 1 חייבת להכיל רק ספרה ולכן 2 אפשרויות).
בהצלחה
