נוסחת נסיגה

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

## הגדרה רקורסיבית של סדרה
בהגדרה רקורסיבית יש שני חלקים: 
# תנאי התחלה הקובעים את האיברים הראשונים בסדרה, 
# נוסחת הנסיגה, המגדירה כל איבר בסדרה באופן רקורסיבי לפי האיברים הקודמים לו.

## מעבר מנוסחת נסיגה להצגה מפורשת

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

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

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

x_n=q\cdot x_{n-1}=q\cdot q\cdot x_{n-2}=\dots=q^n\cdot x_0=q^n\cdot a.

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

### משוואה אופיינית
זוהי דרך שיטתית לפתור נוסחאות מהצורה \!\, x_n=Ax_{n-1}+Bx_{n-2}  (סדרת לוקאס) (הערה: נוסחת נסיגה זו, בה יש התייחסות לשני איברים קודמים בסדרה, נקראת "**נוסחת נסיגה כפולה**"). עבור נוסחה שכזו, יש לפתור את המשוואה הריבועית \!\, r^2-Ar-B=0  ולקבל את השורשים \!\, \lambda_1,\lambda_2.

אם השורשים שונים, האיבר הכללי של נוסחת הנסיגה הוא מהצורה \!\, x_n=C\lambda^n_1+D\lambda^n_2. אם הם זהים, האיבר הכללי הוא \!\, x_n=C\lambda^n+nD\lambda^n. את המקדמים \!\, C,D יש למצוא באמצעות תנאי ההתחלה.

בתור דוגמה נפתור את סדרת פיבונאצ'י, שהיא כזכור מהצורה \!\, x_n=x_{n-1}+x_{n-2}, כלומר אנו מחפשים את שורשי המשוואה \!\, r^2-r-1=0. הפתרונות למשוואה זו הם 
\!\, \lambda_{1,2}=\frac{1\pm\sqrt{5}}{2}. לכן האיבר הכללי הוא מהצורה \!\, x_n=C\left(\frac{1+\sqrt{5}}{2}\right)^n+D\left(\frac{1-\sqrt{5}}{2}\right)^n.

כעת נמצא את המקדמים. ראשית נציב \!\, n=0 ונקבל \!\,x_0=C+D. כעת נציב \!\, n=1 ונקבל \!\, x_1=C\left(\frac{1+\sqrt{5}}{2}\right)+D\left(\frac{1-\sqrt{5}}{2}\right).

מהמשוואה הראשונה נקבל: \!\,C+D=0 (כי האיבר הראשון הוא 0) ולכן \!\,C=-D. האיבר השני הוא 1, ולכן לאחר שנציב את הנתונים במשוואה השנייה נקבל: \!\, C\left(\frac{1+\sqrt{5}}{2}\right)-C\left(\frac{1-\sqrt{5}}{2}\right)=1.

ממשוואה זו נקבל \!\, C=\frac{1}{\sqrt{5}}. על כן, הנוסחה הכללית של פיבונאצ'י היא: \!\, \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right].

### פונקציות יוצרות
דרך נוספת לפתרון נוסחאות נסיגה היא באמצעות פונקציות יוצרות שמקדמיהן הם איברי הנוסחה.

### סדרה ליניארית לא הומוגנית

אם נתון יחס הנסיגה y_{n} = a_1 y_{n-1} + a_2 y_{n-2} + ... + a_k y_{n-k} + b עם תנאי התחלה (y_1,...,y_k) \in \mathbb{R}^k כאשר b \ne 0 אומרים שזו סדרת נסיגה ליניארית לא-הומוגנית. לפני שניגשים לפתור אותה בשיטות שתוארו קודם יש לבצע לה הומוגניזציה. אם לסדרה יש מצב יציב או גבול של סדרה אז הדבר אפשרי. נסמן y_{\infty} = \lim_{n \to \infty} y_n = \frac{b}{1 - a_1 - ... - a_k}
זהו הגבול של הסדרה וקיים רק אם a_1 + ... + a_k \ne 1 (נוסחה זו מתקבלת על ידי החלפת כל ה-y-ים בגבול y_{\infty}). כעת נגדיר סדרה חדשה: z_n = y_n - y_{\infty}. סדרה זו מקיימת את היחס הבא: z_n = a_1 z_{n-1} + a_2 z_{n-2} + ... + a_k z_{n-k}
ומכאן אפשר להמשיך כמו מקודם. מוצאים את k השורשים של הפולינום האופייני \lambda^k - a_1 \lambda^{n-1}  - ... - a_{k-1} \lambda^1 - a_k = 0. אם יש k שורשים שונים, הפתרון הכללי יהיה z_n = c_1 \lambda_1^n + ... + c_k \lambda_k^n
כאשר את המקדמים c_1,...,c_k מוצאים באמצעות תנאי ההתחלה. אם יש שורש מריבוי m אז במקום m מופעים שלו רושמים את הביטוי \tilde{c}_1 \lambda_m^n + \tilde{c}_2 n \lambda_m^n + ... + \tilde{c}_{m} n^{m-1}\lambda_m^n. אם יש שורש מרוכב, אז הוא בא עם שורש צמוד. נרשום את שני השורשים כך \lambda_{\pm} = \alpha \pm i \beta = r \cdot e^{i \theta} = r \cdot (\cos\theta + i\sin\theta) ואז נשתמש בנוסחת אוילר (אנליזה מרוכבת) ונוסחת דה-מואבר כדי לרשום אותם בצורה c_{+} \lambda_{+}^n + c_{-} \lambda_{-}^n = k_1 r^n \cos(n \theta) + k_2 r^n \sin(n \theta)
כאשר k_1, k_2 הם קבועים ממשיים אותם מוצאים מתנאי ההתחלה (ביחד עם שאר מקדמי הצירוף הליניארי).

## קישורים חיצוניים

* 
* 

קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה
קטגוריה:קומבינטוריקה
קטגוריה:רקורסיה