שינויים

* נרצה לחשב את אברי <math>(a_i)_{i=0}^\infty</math> בהינתן תנאי ההתחלה <math>(a_i)_{i=0}^{k-1}</math> ונוסחת נסיגה <math>\forall i\ge k:\ a_i=fg(a_{i-1},\dots,a_{i-k})</math>. נעזר בפונקציה היוצרת <math>f(x)=\sum_{i=0}^\infty a_i x^i</math> ואם קיימת פונקציה <math>FG</math> עבורה {{left|<math>\begin{align}f(x)&=\sum_{i=0}^{k-1} a_i x^i+\sum_{i=k}^\infty fg(a_{i-1},\dots,a_{i-k})x^i\\&=\sum_{i=0}^{k-1} a_i x^i+FG\!\left(x,\sum_{i=k}^\infty a_{i-1}x^{i-1},\dots,\sum_{i=k}^\infty a_{i-k}x^{i-k}\right)\\&=\sum_{i=0}^{k-1} a_i x^i+FG\!\left(x,f(x)-\sum_{i=0}^{k-2} a_ix^i,\dots,f(x)\right)\end{align}</math>}}אז נבודד את <math>f(x)</math> ונקבל נוסחה מפורשת למקדמים <math>a_i</math> של <math>x^i</math>.* תהי נוסחת נסיגה לינארית הומוגנית עם מקדמים קבועים <math>a_n=\sum_{i=1}^k c_i a_{n-i}</math> מסדר <math>k</math>. נניח שיש <math>\alpha\in\mathbb C</math> עבורו <math>\forall n:\ a_n=\alpha^n</math> (לא תמיד זה נכון). אזי <math>\alpha=0</math> פתרון. <math>x^k-\sum_{i=1}^k c_i x^{k-i}</math> נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם <math>\alpha\ne0</math> אז הוא שווה ל־0 בנקודה <math>\alpha</math>. יש לו <math>k</math> שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם <math>\alpha_1,\dots,\alpha_k</math> אז <math>\forall n,i:\ a_n=\alpha_i^n</math>. המרחב הווקטורי של הפתרונות הוא אם כן <math>\left\{\left(\sum_{i=1}^k r_i\alpha_i^n\right)_{n=0}^\infty:\ \forall i:\ r_i\in\mathbb C\right\}</math>. אם נתונים תנאי ההתחלה ניתן גם לחשב את ה־<math>r_i</math>־ים.