# Discrete Mathematics Nonhomogenous linear recurrence relation

Solve the recurrence relation

$$a_n=-a_{n-1}+8a_{n-1}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14\text{ for }n\ge3$$ where $a_0=6,a_1=0$ and $a_2=57$.

Just want to ask if my $p_n$ is correct because I just can't get the value of A. I have deduced $p_n$ = $A3^{n-2}-Bn^2+Cn+D$. Where $a_n = b_n + p_n$

• You are looking for a particular solution, I think. Because $3$ is a root of the characteristic polynomial, one component of the particular solution will be a term of the shape $An3^n$. Note that this comment just deals with your first term of the particular solution. – André Nicolas Apr 18 '16 at 4:50
• To repeat, the thing to try is $A(n3^n)$. There is no need for a $K(3^n)$ term, when you push that through the recurrence, you get no information. – André Nicolas Apr 18 '16 at 5:00
• The second term on the right hand side of the recurrence relation should be $8a_{n-2}$, not $8a_{n-1}$ as it is now, I believe. Am I right? – chizhek Apr 18 '16 at 12:41
Let $E$ be the shift operator acting on the two-way infinite sequences $x=(x_n\mid n\in\mathbb{Z})$, \begin{equation*} (Ex)_n=x_{n+1}~, \end{equation*} and $\Delta=E-1$ the difference operator, \begin{equation*} (\Delta x)_n=x_{n+1}-x_n~. \end{equation*} The given recurrence relation (which works also backwards for $n<0$, that is, it determines the values of $a_n$ for all integers $n$) \begin{gather*} a_n=-a_{n-1}+8a_{n-2}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14~, \\[1ex] a_0=6\,,~a_1=0\,,~a2=57~, \end{gather*} we rewrite in the form \begin{equation*} ((E^3+E^2-8E-12)a)_{n-3}=25\cdot3^{n-2}-18n^2+48n+14~, \end{equation*} where $E^3+E^2-8E-12$ factors as $(E+2)^2(E-3)$. We know that $E-3$ kills $3^{n-2}$ and that $\Delta^3$ kills every polynomial in $n$ of degree at most two, therefore the sequence $a=(a_n)$ satisfies the homogeneous recurrence relation \begin{equation*} (E-1)^3(E+2)^2(E-3)^2x=0~, \end{equation*} (with $x=a$) which has the general solution of the form \begin{equation*} x_n = \alpha_0+\alpha_1n+\alpha_2n^2 + (\beta_0+\beta_1n)\cdot(-2)^n+(\gamma_0+\gamma_1n)\cdot3^n~. \end{equation*} All it remains to do is to compute $a_3$, $a_4$, $a_5$, $a_6$ using the given recurrence relation and then solve the seven linear equations $x_k=a_k$, $0\leq k\leq 6$, for the seven unknowns $\alpha_0$, $\alpha_1$, $\alpha_2$, $\beta_0$, $\beta_1$, $\gamma_0$, $\gamma_1$, which gets us \begin{equation*} \alpha_0=0\,,~\alpha_1=3\,,~\alpha_2=1\,,~\beta_0=5\,,~\beta_1=0\,,\gamma_0=1\,,\gamma_1=1\,. \end{equation*} So we have the explicit expression for $a_n$: \begin{equation*} a_n \,=\, 3n+n^2+5\cdot(-2)^n+(1+n)\cdot3^n~. \end{equation*} Done.