# Solving $a_{n+2}-6a_{n+1}+8a_n=27n^2+18$

Solve the recurrence relation $$a_{n+2}-6a_{n+1}+8a_n=27n^2+18$$

I found the homogenous solutions which are $r=2,4$ meaning that $$a_n=C_12^n+C_24^n$$. I'm not sure what to do after that.

• You can plug in $n$ when $n$ equals $1, 2, 3 \cdots$. Observe the difference between the LHS and RHS and you can calculate the other terms using the difference method. By a quick look you can determine if the other terms are polynomials or not. – Toby Mak Oct 26 '17 at 23:49
• You could also use the method of undetermined coefficients. So "guess" a particular solution based on the RHS. – Natash1 Oct 26 '17 at 23:51
• Try a solution of the form $a_n = \alpha + \beta n + \gamma n^2$ and solve the system obtained by setting the coefficients of $(1,n,n^2)$ to zero. – jcandy Oct 26 '17 at 23:55
• Natash1 I am suppose to use undetermined coefficients and have been trying for an hour but I don't understand how to do this because I cannot see how we can equate coefficients – Rose Oct 27 '17 at 1:15
• I have added a section in my answer to show this identification of coefficients. – zwim Oct 27 '17 at 3:01

Write $a_{n+2} - 6a_{n+1} + 8a_n = (a_{n+2} - 4a_{n+1})- 2(a_{n+1} - 4a_n) = 27n^2+18$. This suggests that you put $b_n = a_n - 4a_{n-1}$, then you have: $b_{n+2}-2b_{n+1} = 27n^2 + 8$. So, you now have: $b_n = (b_n - 2b_{n-1})+ 2(b_{n-1}-2b_{n-2})+ 4(b_{n-2} - 2b_{n-3})+\cdots +2^{n-2}(b_2-2b_1) + 2^{n-1}b_1 = (27(n-2)^2+8)+2(27(n-3)^2+8)+4(27(n-4)^2+8)+\cdots+2^{n-2}((a_2-4a_1)-(a_1-4a_0))+ 2^{n-1}(a_1-4a_0)$. This sum is easy to evaluate. Repeat this trick again for the $a_n$ and you can solve it without using the characteristic equation. Its a bit long but is ...fun...

Linear relations like this are solved by adding a particular solution to the general solution of homogeneous equation.

The homogeneous equation is solved by finding roots of the associated characteristic equation.

And the general solution is given by $a_n=\sum\limits_{i=1}^m P_i(n)(r_i)^n$ where $P_i$ is a polynomial and $\deg(P_i)=\text{multiplicity}(r_i)-1$

So when roots are simple, you get $a_n=C_1r_1^n+C_2r_2^n+...$

If there is a double root, the contribution from that root will be $(An+B)r^n$.

For a triple root, the contribution is $(An^2+Bn+C)r^n$

And so on...

Here the RHS is $(27n^2+18)\times 1^n$

Since $1$ is not a root of the characteristic equation then you can find a particular solution of the form $(An^2+Bn+C)\times 1^n$.

And you find $9n^2+24n+44$

If RHS would have been $(27n^2+18)\times 2^n$

Then since $2$ is a root you have to increase by one unity the degree of the polynomial to search for, thus try $(An^3+Bn^2+Cn+D)\times 2^n$

In general if:

• $r$ is of multiplicity $m$
• RHS $=P(n)\,r^n$
• then you get to search for a particular solution $Q(n)\,r^n$ where $\deg(Q)=\deg(P)+m$.

Edit: answering OP concern "I cannot see how we can equate coefficients"

Let's put $b_n=An^2+Bn+C$

$\begin{array}{l} b_{n+2}-6b_{n+1}+8b_n \\\\ =\left[A(n+2)^2+B(n+2)+C\right]-6\left[A(n+1)^2+B(n+1)+C\right]+8\left[An^2+Bn+C\right] \\\\ = \left(A-6A+8A\right)n^2+\left(4A+B-12A-6B+8B\right)n+\\\phantom{=}\left(4A+2B+C-6A-6B-6C+8C\right) \\\\ =(3A)n^2+(-8A+3B)n+(-2A-4B+3C)\\ \end{array}$

This polynomial should be equal to $(27)n^2+(0)n+(18)$ and since a polynomial is null when all its coefficients are null, identification of coefficients means that we create a system where we equate each coefficient of $n^k$ on the first polynomial to the same coefficient of the second polynomial.

In our case this becomes

$\begin{cases}3A&=27\\-8A+3B&=0\\-2A-4B+3C&=18\end{cases}\iff \begin{cases}A=9\\3B=8A=72\\3C=18+2A+4B=18+18+96=132\end{cases}\iff$

$A=9,\ B=24,\ C=44\quad$ and $\quad\boxed{b_n=9n^2+24n+44}$

Here's an alternative way of solving this recurrence. No method will be simple, but this can be written for a general form and solved once and for all. Thus consider

$$g_n+Ag_{n-1}+Bg_{n-2}=Cn^2+D$$

We can reduce this to well known problem by allowing

$$g_n=f_n+pn^2+qn+r$$

Substituting this into the above we can arrive at the coupled equations for $p, q, r$ as follows

$$\left[\begin{matrix} 1+A+B & 0 & 0 \\ -2A-4B & 1+A+B & 0 \\ A+4B & -A-2B & 1+A+B \end{matrix}\right] \left[\begin{matrix} p \\ q\\ r\end{matrix}\right]=\left[\begin{matrix} C \\ 0 \\ D \end{matrix}\right]$$

This can be readily solved for $p, q, r$ and we are left with

$$f_n=-Af_{n-1}-Bf_{n-2}\\ f_0=g_0-r\\ f_1=g_1-p-q-r$$

With characteristic roots

$$\alpha,\beta=\frac{-A\pm\sqrt{A^2-4B}}{2}\quad (=4,2 \text{ in the present case})$$

The final result is then

$$g_n=f_n+pn^2+qn+r$$

I have verified this method numerically for random values of $A,B,C,D,g_0,g_1$.