Solving for the closed term solution of a third order recurrence relation with real constant coefficients
How would you solve for the closed term form of $a(n)$ given the general form of the third order linear homogenous recurrence relation with real constant coefficients.
$a(n)-P\,a(n-1)-Q\,a(n-2)-R\,a(n-3)=0$
with the initial terms of a1, a2, and a3
and given that the roots of the characteristic equations have
- two repeated roots and a real root
- three repeated roots
(can you give answers for both cases please)
For second order recurrence relations I know that you can use generating functions to deduce a closed form because it is then expressed as a arithmetic series which can be converted into a closed form.
However in the case of the general term of the third order recurrence relations if I follow the same steps what I did with the second order recurrence relation, instead of getting a simple arithmetic series I seemed to get a second order recurrence relation inside the series.
What am I doing wrong?
or is there a different method of approach in this case?
When I search the web I get these results
S(n) = nAx1^n + Bx1^n + Cx2^n,for the case when there are two repeated roots
and
S(n) = n^2Ax^n + nBx^n + Cx^n, for the case when there are three repeated roots
I just don't know how to get to these results
Please help
Solution 1:
Note: I changed the terminology somewhat; this sequence starts with $a_0$ rather than $a_1$.
Suppose we have a sequence $a_0,a_1,a_2,\dots$ whose generating function is $$ f_a(x)=a_0+a_1x+a_2x^2+\cdots $$ satisfying the recurrence relation $$ a_n-P\,a_{n-1}-Q\,a_{n-2}-R\,a_{n-3}=0\iff\\ a_n=P\,a_{n-1}+Q\,a_{n-2}+R\,a_{n-3} $$ Multiply $f_a(x)$ by the polynomial $1-Px-Qx^2-Rx^3$ to get the polynomial $$ g(x) = b_0+b_1 x+ b_2 x^2+\cdots $$ where for $n\geq 3$, $b_n=a_n-P\,a_{n-1}-Q\,a_{n-2}-R\,a_{n-3}$. By our recurrence relation, this means that $b_n=0$ whenever $n\geq 3$. So, we have
$$ (1-Px-Qx^2-Rx^3)f_a(x)=b_0+b_1 x+ b_2 x^2 $$ Which is to say that $$ f_a(x)=\frac{b_0+b_1 x+ b_2 x^2}{1-Px-Qx^2-Rx^3} $$ Where $$ b_0 = a_0\\ b_1 = a_1 - P\,a_0\\ b_2 = a_2 - P\,a_1 - Q\,a_0 $$ Can you take it from there?
So in order to bring this back to the characteristic equation, we just need to use another little trick. Instead of writing this as a function of $x$, write it as a function of $\frac1x$. You could do this by making a substitution like $x=\frac1\omega$, but I prefer a more direct approach.
We have: $$ f_a(x)=\frac{b_0+b_1 x+ b_2 x^2}{1-Px-Qx^2-Rx^3} $$ With $b_1,b_2,b_3$ as defined above. From there, just divide the top and bottom by $x^3$ to get $$ f_a(x)=\frac{b_0\left(\frac1{x}\right)^3+b_1 \left(\frac1{x}\right)^2 + b_2 \left(\frac1{x}\right)}{ \left(\frac1{x}\right)^3-P\left(\frac1{x}\right)^2- Q\left(\frac1{x}\right)-R} $$ Now, suppose we have one repeated root. That is, $t^3 - Pt^2 - Qt - R=(t-r_1)(t-r_2)^2$ for roots $r_1,r_2$. We then can write the above as $$ f_a(x)=\frac{b_0\left(\frac1{x}\right)^3+b_1 \left(\frac1{x}\right)^2 + b_2 \left(\frac1{x}\right)}{ \left(\left(\frac1{x}\right)-r_1\right) \left(\left(\frac1{x}\right)-r_2\right)^2} $$ Where would you go from there? For the case of a triply repeated root, we have $t^3 - Pt^2 - Qt - R=(t-r)^3$ for the repeated root $r$. We then can write the generating function as $$ f_a(x)=\frac{b_0\left(\frac1{x}\right)^3+b_1 \left(\frac1{x}\right)^2 + b_2 \left(\frac1{x}\right)}{ \left(\left(\frac1{x}\right)-r\right)^3} $$ Where would you go from there?