שלום לכולם, נתונה נוסחת הנסיגה הבאה:
f(n)=6f(n-1)-8f(n-2)-3
עם תנאי התחלה f(0)=1 ו-f(1)=9.
כיצד לפתור את נוסחת הנסיגה הנ"ל?
תודה רבה על העזרה.
אפשר להשתמש בפונקציות אופייניות על מנת לפתור את משוואת הנסיגה.
נכפול את צידי משוואת הנסיגה ב-x^{n}:
f(n)x^{n}=6f(n-1)x^{n}-8f(n-2)x^{n}-3x^{n}
נסכום ע"פ הערכים החוקיים של n\geq2:
\sum_{n=2}^{\infty}f(n)x^{n}=\sum_{n=2}^{\infty}\left(6f(n-1)x^{n}-8f(n-2)x^{n}-3x^{n}\right)\,\,\,(1)
נגדיר: g(x)=\sum_{n=0}^{\infty}f(n)x^{n}.
נתבונן על צד שמאל של המשוואה (1), כך שנקבל:
\sum_{n=2}^{\infty}f(n)x^{n}=\sum_{n=0}^{\infty}f(n)x^{n}-f(1)x-f(0)=g(x)-9x-1
עתה, נתבונן על צד ימין של המשוואה (1), כך שנקבל:
\begin{align*}
\sum_{n=2}^{\infty}\left(6f(n-1)x^{n}-8f(n-2)x^{n}-3x^{n}\right)&=6\sum_{n=2}^{\infty}f(n-1)x^{n}-8\sum_{n=2}^{\infty}f(n-2)x^{n}-3\sum_{n=2}^{\infty}x^{n}\\&=6x\sum_{n=0}^{\infty}f(n)x^{n}-6f(1)x-8x^{2}\sum_{n=0}^{\infty}f(n)x^{n}-3\sum_{n=0}^{\infty}x^{n}+3+3x\\&=6xg(x)-6x-8x^{2}g(x)-3\cdot\frac{1}{1-x}+3+3x\\&=-8x^{2}g(x)+6xg(x)-3\cdot\frac{1}{1-x}-3x+3
\end{align*}
נציב במשוואה (1):
\begin{align*}
g(x)-9x-1=-8x^{2}g(x)+6xg(x)-3\cdot\frac{1}{1-x}-3x+3&\Leftrightarrow(8x^{2}-6x+1)g(x)=-3\cdot\frac{1}{1-x}+6x+4\\&\Leftrightarrow(4x-1)(2x-1)g(x)=\frac{-3+6x-6x^{2}+4-4x}{1-x}\\&\Leftrightarrow g(x)=\frac{-6x^{2}+2x+1}{(4x-1)(2x-1)(1-x)}
\end{align*}
נפרק לגורמים חלקיים - יהיו A,B,C כך שמתקיים:
\begin{align*}
\frac{-6x^{2}+2x+1}{(4x-1)(2x-1)(1-x)}=\frac{A}{4x-1}+\frac{B}{2x-1}+\frac{C}{1-x}&\Leftrightarrow-6x^{2}+2x+1=A(2x-1)(1-x)+B(4x-1)(1-x)+C(4x-1)(2x-1)\\&\Leftrightarrow-6x^{2}+2x+1=A(-2x^{2}+3x-1)+B(-4x^{2}+5x-1)+C(8x^{2}-6x+1)\\&\Leftrightarrow-6x^{2}+2x+1=(-2A-4B+8C)x^{2}+(3A+5B-6C)x+(-A-B+C)
\end{align*}
לכן נקבל את מערכת המשוואות הבאה:
\begin{cases}
-2A-4B+8C=-6\\
3A+5B-6C=2\\
-A-B+C=1
\end{cases}\Longrightarrow\begin{cases}
A=-3\\
B=1\\
C=-1
\end{cases}
כלומר קיבלנו כי מתקיים:
\begin{align*}
g(x)&=\frac{-6x^{2}+2x+1}{(4x-1)(2x-1)(1-x)}\\&=-\frac{3}{4x-1}+\frac{1}{2x-1}-\frac{1}{1-x}\\&=\frac{3}{1-4x}-\frac{1}{1-2x}-\frac{1}{1-x}\\&=3\cdot\sum_{n=0}^{\infty}(4x)^{n}-\sum_{n=0}^{\infty}(2x)^{n}-\sum_{n=0}^{\infty}x^{n}\\&=\sum_{n=0}^{\infty}(3\cdot4^{n}-2^{n}-1)\cdot x^{n}
\end{align*}
המקדם של x^{n} הוא 3\cdot4^{n}-2^{n}-1 ולכן f(n)=3\cdot4^{n}-2^{n}-1.