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
 A: 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?
A: Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence without subtraction in indices, i.e.,
$$
a_{n + 3} - P a_{n + 2} - Q a_{n + 1} - R a_n = 0
$$
Multiply by $z^n$, sum over $n \ge 0$ to get:
$$
\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3}
 - P \frac{A(z) - a_0 - a_1 z}{z^2}
 - Q \frac{A(z) - a_0}{z}
 - R A(z)
 = 0
$$
or:
$$
A(z) 
  = \frac{a_0 - (P a_0 - a_1) z - (Q a_0 + P a_1 - a_2) z^2}
         {1 - P z - Q z^2 - R z^3}
$$
This you can split into partial fractions. The form they take depends on the zeros of the denominator, which doesn't depend on initial values.


*

*All zeros different: You'll end up with an expression of the form:
$$
A(z)
  = \frac{A_1}{1 - \alpha_1 z} 
      + \frac{A_2}{1 - \alpha_2 z}
      + \frac{A_3}{1 - \alpha_3 z}
$$
The constants $A_i$ depend on the initial values.
This is just three geometric series:
$$
a_n = A_1 \alpha_1^n + A_2 \alpha_2^n + A_2 \alpha_3^n
$$
If some zeros turn out complex, say $\alpha_2$ and $\alpha_3$, you'll have a complex pair, which you can write $\rho \mathrm{e}^{\pm \mathrm{i} \theta}$, and for some complex $A_2$ and $A_3$, complex conjugates you can write $A \mathrm{e}^{\pm \mathrm{i} \gamma}$, this gives a solution of the form 
\begin{align}
A 
  \cdot \rho^n 
  & \cdot (\mathrm{e}^{\mathrm{i} \gamma} 
               \cdot \mathrm{e}^{\mathrm{i} n \theta} 
             + \mathrm{e}^{-\mathrm{i} \gamma} 
                  \cdot \mathrm{e}^{-\mathrm{i} n \theta}) \\
 &= A
      \cdot \rho^n
      \cdot (\mathrm{e}^{\mathrm{i} (n \theta + \gamma)}
               + \mathrm{e}^{-\mathrm{i} (n \theta + \gamma)}) \\
 &= 2 A \cdot \rho^n \cdot \cos (n \theta + \gamma)
\end{align}
I.e., in all:
$$
a_n = A_1 \alpha_1^n + A \cdot \rho^n \cdot \cos(n \theta + \gamma)
$$

*

*Two equal zeros: They must all be real in this case, say $\alpha_1 \ne \alpha_2 = \alpha_3$. The partial fraction expansion is:
$$
A(z)
  = \frac{A_1}{1 - \alpha_1 z} 
     + \frac{B_2}{1 - \alpha_2 z}
     + \frac{B_3}{(1 - \alpha_2 z)^2}
$$
Expand the last term by:
$$
(1 - u)^{-m}
  = \sum_{n \ge 0} \binom{-m}{n} (-u)^n
  = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} u^n
$$
and remember that $\binom{n + 1}{1} = n + 1$ to get:
\begin{align}
a_n
  &= A_1 \alpha_1^n + B_1 \alpha_2^n + B_2 (n + 1) \alpha_2^n \\
  &= A_1 \alpha_1^n + (B_2' n + B_1') \alpha_2^n
\end{align}

*All three equal: In this case the partial fraction expansion is:
$$
A(z)
  = \frac{C_1}{1 - \alpha_1 z}
      + \frac{C_2}{(1 - \alpha_1 z)^2}
      + \frac{C_3}{(1 - \alpha_1 z)^3}
$$
Similar to the previous case, $\binom{n + 2}{2}$ is a quadratic polynomial, giving:
$$
a_n = (C'_3 n^2 + C'_2 n + C'_1) \alpha_1^n
$$


A: The generic solution to the recurrence relation in question is given below:
\begin{equation}
a(n+3) =\sum\limits_{\xi=0}^2 a(2-\xi) \cdot \\\sum\limits_{l_1=0}^n\sum\limits_{l_2=0}^n1_{n+\xi\ge 2 l_1+3 l_2} \binom{l_1+l_2-1_{\xi=2}}{l_1-1_{\xi=2}} \binom{n-l_1-2 l_2+1_{\xi=2}}{l_1+l_2-1_{\xi \ge 1}} P^{n+\xi-2 l_1-3 l_2} Q^{l_1} R^{l_2} 
\end{equation}
