2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Toby Mak Oct 26 '17 at 23:49
  • $\begingroup$ You could also use the method of undetermined coefficients. So "guess" a particular solution based on the RHS. $\endgroup$ – Natash1 Oct 26 '17 at 23:51
  • $\begingroup$ 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. $\endgroup$ – jcandy Oct 26 '17 at 23:55
  • $\begingroup$ 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 $\endgroup$ – Rose Oct 27 '17 at 1:15
  • $\begingroup$ I have added a section in my answer to show this identification of coefficients. $\endgroup$ – zwim Oct 27 '17 at 3:01
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.