# 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

1. two repeated roots and a real root
2. three repeated roots

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

• Yes they are constants I'm trying to find the closed form of a general form of the third order recurrence relation – Brian Aug 9 '13 at 16:12

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?

• Let me know how this method compares with what you've done for second order recurrence relations. Does this make sense? Is it similar to your method? Is there anything you'd like clarified? – Ben Grossmann Aug 9 '13 at 16:51
• Thanks so much I kind of get it but my knowledge of math isn't that deep (I'm in high-school) so to be honest I don't really know what do do from here.. If you could write up the full solution I'd greatly appreciate it. Could you also explain how to get the closed form for the two cases 1)one real root and repeated roots b)three repeated roots Thanks – Brian Aug 10 '13 at 14:49
• Interesting that you're doing this in high-school. I would go further, but I'm not exactly sure what you meant by "the roots of the characteristic equations". If you could explain what a "characteristic equation" is here (either in a comment or by editing your question), I might be able to continue. – Ben Grossmann Aug 10 '13 at 15:22
• By "the characteristic equations", do you mean the characteristic polynomial $t^3 - Pt^2 - Qt - R=0$? – Ben Grossmann Aug 10 '13 at 17:53
• yes thats exactly it. I was implying the characteristic equation (polynomial) of the general term of a linear homogenous third order recurrence relation a(n)-Pa(n-1)-Qa(n-2)-Ra(n-3) – Brian Aug 11 '13 at 2:32

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$$

The generic solution to the recurrence relation in question is given below: $$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}$$