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

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

אנו מקבלים את הסדרה ....,0,1,1,2,3,5,8.

פתרון נוסחאות נסיגה

---

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

הצבה חוזרת

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

דוגמה: נביט בסדרה $x\_0=a,x\_n=q\backslash cdot\; x\_\{n-1\}$. זוהי נוסחה של סדרה הנדסית, שבה המנה של כל שני איברים עוקבים היא $\backslash !\backslash ,\; q$. כעת ניקח את הנוסחה של $\backslash !\backslash ,\; x\_n$ ונציב בה את עצמה שוב ושוב עד אשר נגיע לאיבר $\backslash !\backslash ,\; x\_0$:

$x\_n=q\backslash cdot\; x\_\{n-1\}=q\backslash cdot\; q\backslash cdot\; x\_\{n-2\}=\backslash dots=q^n\backslash cdot\; x\_0=q^n\backslash cdot\; a$.

ניחוש הפתרון

לעתים אין דרך שיטתית לפתור נוסחת נסיגה, אולם ניתן להעריך את צורתו של הפתרון שיתקבל - למשל, האם יהיה מהצורה $\backslash !\backslash ,\; x\_n=Ax\_\{n-1\}+B^\{x\_n-2\}$. כשפותרים בדרך זו, יש להשתמש בתנאי ההתחלה הידועים של נוסחת הנסיגה כדי לחשב את המקדמים של הנוסחה המפורשת, ואז להוכיח (למשל באמצעות אינדוקציה מתמטית) את נכונות הנוסחה המנוחשת.

משוואה אופיינית

זוהי דרך שיטתית לפתור נוסחאות מהצורה $\backslash !\backslash ,\; x\_n=Ax\_\{n-1\}+Bx\_\{n-2\}$. עבור נוסחה שכזו, יש לפתור את המשוואה הריבועית $\backslash !\backslash ,\; r^2-Ar-B=0$ ולקבל את השורשים $\backslash !\backslash ,\; \backslash lambda\_1,\backslash lambda\_2$.

אם השורשים שונים, האיבר הכללי של נוסחת הנסיגה הוא מהצורה $\backslash !\backslash ,\; x\_n=C\backslash lambda^n\_1+D\backslash lambda^n\_2$. אם הם זהים, האיבר הכללי הוא $\backslash !\backslash ,\; x\_n=C\backslash lambda^n+nD\backslash lambda^n$. את המקדמים $\backslash !\backslash ,\; C,D$ יש למצוא באמצעות תנאי ההתחלה.

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

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

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

ממשוואה זו נקבל $\backslash !\backslash ,\; C=\backslash frac\{1\}\{\backslash sqrt\{5\}\}$. על כן, הנוסחה הכללית של פיבונאצ'י היא: $\backslash !\backslash ,\; \backslash frac\{1\}\{\backslash sqrt\{5\}\}\backslash left*$.

פונקציות יוצרות

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

Recurrence relation | Differenzengleichung | Rekurzív sorozat | Relazione di ricorrenza | 数列 | 점화식 | Differentievergelijking | 遞迴關係式