נוסחת נסיגה

נוסחת נסיגה היא כלל ההגדרה של רשימת מספרים, שנקראת סדרה, שנכתבת בצורה רקורסיבית. רקורסיבי כאן אומר שכל איבר בסדרה מוגדר בעזרת איברים קודמים שלו. לדוגמה, בסדרת פיבונאצ'י כל איבר הוא סכום שני הקודמים: F_{n+1}=F_n+F_{n-1}, עם תנאי התחלה (המספרים הראשונים) F_0=F_1=1.


הגדרה רקורסיבית מורכבת משני חלקים פשוטים:

1) תנאי התחלה, האיברים הראשונים שמגדירים את הסדרה.
2) נוסחת הנסיגה, הכלל שמחשב כל איבר מתוך איברים קודמים.


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


בשיטות פשוטות אפשר להציב שוב ושוב את הנוסחה בעצמה עד שנגיעה לתנאי ההתחלה. לדוגמה, בסדרה הנדסית x_0=a ו-x_n=q x_{n-1} (המשמעות: כל איבר הוא q כפול האיבר הקודם), אם נציב חוזר נקבל x_n=q^n a.


לפעמים אין שיטה סדורה, אבל אפשר לנחש את צורת הפתרון, למשל x_n=A+Bn+C^n. לאחר הניחוש משתמשים בתנאי ההתחלה כדי למצוא את המקדמים A,B,C ואוכחים את הנכונות בדרך כלל בעזרת אינדוקציה מתמטית (הוכחה בשלבים).


לנוסחאות מהצורה x_n=A x_{n-1}+B x_{n-2} יש שיטה מובנית. כותבים את המשוואה הריבועית r^2-Ar-B=0 ומוצאים את השורשים λ_1,λ_2. אם השורשים שונים, הפתרון הכללי הוא x_n=C λ_1^n + D λ_2^n. אם השורשים שווים, מקבלים ביטוי עם רכיב נוסף שמתייחס ל-n, כלומר x_n=Cλ^n + nDλ^n. המקדמים C,D נקבעים מתנאי ההתחלה.

כדוגמה, בסדרת פיבונאצ'י מתקבלת המשוואה r^2-r-1=0 עם פתרונות (1±√5)/2. לכן x_n=C((1+√5)/2)^n + D((1-√5)/2)^n. בעזרת תנאי ההתחלה מוצאים C=1/ √5 ו-D=-C, ומקבלים את הנוסחה הסגורה הידועה.


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


אם יחס הנסיגה כולל גם חלק קבוע b נכתב y_n=a_1 y_{n-1}+...+a_k y_{n-k}+b, קוראים לזה סדרה ליניארית לא-הומוגנית. תחילה מוצאים את הגבול האפשרי y_\infty=b/(1-a_1-...-a_k) אם סכום המקדמים שונה מאחד. לאחר מכן מגדירים z_n=y_n-y_\infty, שהופכת לסדרה הומוגנית. את z_n פותרים בעזרת הפולינום האופייני λ^k-a_1 λ^{k-1}-...-a_k=0. אם יש k שורשים שונים, z_n=
c_1 λ_1^n+...+c_k λ_k^n. במקרה של שורש מרובה או שורשים מרוכבים מוסיפים גורמים של n או משתמשים בביטויי סינוס וקוסינוס המתאימים כדי לקבל פתרון ממשי.

נוסחת נסיגה היא כלל שמספר איך לבנות רשימת מספרים, שנקראת סדרה. היא אומרת איך לקבל כל מספר מהמספרים שלפניו. המילה "רקורסיבי" אומרת בדיוק את זה: משתמשים בקודמים כדי למצוא את הבא.


יש שני חלקים חשובים:

1) תנאי התחלה, המספרים הראשונים שמתחילים את הסדרה.
2) כלל (נוסחת נסיגה), איך מחשבים כל מספר מהקודמים.


לפעמים פשוט מוציאים את הנוסחה שוב ושוב עד שמגיעים למספר הראשון. למשל בסדרה הנדסית x_0=a ו-x_n=q x_{n-1}, כל איבר הוא q פעמים הקודם, ולכן x_n=q^n a.


בסדרת פיבונאצ'י כל מספר הוא סכום שני הקודמים. המספרים הראשונים הם 1 ו-1. אפשר גם לכתוב נוסחה ישירה שמחשבת את האיבר ה-n בלי לחשב את כולם. כדי לקבל אותה מוציאים משוואות ופותרים אותן.


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


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