Solving linear non homogeneous recurrence relations

Question

$a_{n+2}+3 a_{n+1}+2 a_n=5 n+3$, where $a_0=1, a_1=4$.

I am trying to solve the homogeneous part first, I have the roots as r = -1 and r = -2, by factorising the characteristic equation which I have as $r^2 + 3r + 2 = 0$.

So I have the homogenous solution as $A(-1)^n + B(-2)^n$

I plug in $a_0 = 1$ into the solution to get $A + B = 1$ hence $A = 1 - B$ then I do the same with $a_1 = 4$ then solve the simultaneous equation to get $B = -5$

However it seems this is wrong upon checking the answer, I'm not sure where I'm going wrong, although I'm not sure what to do with the $5n$ or the $3$ in this part so that might be the reason, haven't really found a helpful source for this type of recurrence relation, any help is appreciated.

Answer 1

The general solution of such a linear recurrence relation is given by $a_n = b_n + c_n$, where $b_n = A(-1)^n + (-2)^n$ is the solution of the associated homogeneous problem, which you have already solved, and $c_n$ is a particular solution to the nonhomogeneous problem.

This particular solution can be determined, by analogy with linear ODEs, thanks to the method of the variation of parameters, i.e. by recycling the homogeneous solution where the parameters $A$ and $B$ are now functions of $n$, such that $c_n = A_n(-1)^n + B_n(-2)^n$; plugging this expression into the nonhomogeneous recurrence relation, you can find suitable $A_n$ and $B_n$.

However, it is usually simpler to consider an ansatz with the same structure as the nonhomogeneous source term. In the present case, let's take $c_n = \alpha n + \beta$, hence $$ c_{n+2} + 3c_{n+1} + 2c_n = 6\alpha n + 5\alpha + 6\beta = 5n+3 $$ from which one finds $\alpha = 5/6$ and $\beta = -7/36$.

The general answer is thus $a_n = A(-1)^n + B(-2)^n + \frac{5}{6}n - \frac{7}{36}$. And now you must use your initial conditions in order to determine the constants $A$ and $B$. Here we have : $$ \left\{ \begin{array}{lll} a_0 = \color{white}{-}A + \color{white}{2}B - \frac{7}{36} = 1 \\ a_1 = -A - 2B + \frac{23}{36} = 4 \end{array} \right. $$ And I'll let you finish from there.

Answer 2

As noted in the question, the problem is that $5n+3$ is not handled in the homogeneous solution. In Abezhiko's answer, this is dealt with using variation of parameters. Here, we extend the difference operator to eliminate the $5n+3$ term and solve the extended equation.

Using the shift operator $Sa_n=a_{n+1}$, the equation $a_{n+2}+3a_{n+1}+2a_n=5n+3$ can be written as $$ (S+1)(S+2)a_n=5n+3\tag1 $$ To make this into a linear homogeneous recurrence relation, apply $(S-1)^2$: $$ (S-1)^2(S+1)(S+2)a_n=(S-1)^2(5n+3)=0\tag2 $$ As shown in this answer, the solution to $(S-\lambda)^ka_n=0$ is $p(n)\lambda^n$where $p$ is a polynomial of degree $k-1$. Since equation $(2)$ is linear, its solutions have the form $$ a_n=\overbrace{\ \ bn+c\ \ }^{(S-1)^2}+\overbrace{\ d(-1)^n\ }^{S+1}+\overbrace{\ \ e(-2)^n\ \ }^{S+2}\tag3 $$ Now, compute the first $4$ terms of $a_n$ from the initial recurrence: $1,4,-11,33$. Applying $(3)$ for $n\in\{0,1,2,3\}$ yields the $4$ equations in $4$ unknowns: $$ \begin{bmatrix} 0&1&1&1\\ 1&1&-1&-2\\ 2&1&1&4\\ 3&1&-1&-8 \end{bmatrix} \begin{bmatrix} b\\c\\d\\e \end{bmatrix} =\begin{bmatrix} 1\\4\\-11\\33 \end{bmatrix}\tag4 $$ Solving $(4)$ gives the coefficients $$ \begin{bmatrix} b\\c\\d\\e \end{bmatrix} =\frac1{36}\begin{bmatrix} 30\\-7\\207\\-164 \end{bmatrix}\tag5 $$ and finally the solution $$ a_n=\frac1{36}\left(30n-7+207(-1)^n-164(-2)^n\right)\tag6 $$

Answer 3

Another approach is to use generating functions. Let $A(z)=\sum_{n \ge 0} a_n z^n$. The recurrence relation then implies that $$\sum_{n\ge0} a_{n+2}z^{n+2}+3 \sum_{n\ge0}a_{n+1}z^{n+2}+2 \sum_{n\ge0}a_nz^{n+2} = 5 \sum_{n\ge0}nz^{n+2} + 3\sum_{n\ge0}z^{n+2}.$$ Equivalently, $$(A(z)-a_0-a_1z)+3z(A(z)-a_0)+2 z^2 A(z) = \frac{5z^3}{(1-z)^2} + \frac{3z^2}{1-z}.$$ Substituting $a_0=1$ and $a_1=4$ and solving for $A(z)$ yields \begin{align} A(z) &= \frac{1+7z + \frac{5z^3}{(1-z)^2} + \frac{3z^2}{1-z}}{1+3z+2z^2}\\ &= \frac{1+5z-10z^2+9z^3}{(1+z)(1+2z)(1-z)^2}\\ &= \frac{23/4}{1+z} - \frac{41/9}{1+2z} - \frac{37/36}{1-z} + \frac{5/6}{(1-z)^2}\\ &= \frac{23}{4}\sum_{n \ge 0} (-z)^n - \frac{41}{9}\sum_{n \ge 0} (-2z)^n - \frac{37}{36}\sum_{n \ge 0} z^n + \frac{5}{6}\sum_{n \ge 0} \binom{n+1}{1} z^n\\ &= \sum_{n \ge 0}\left(\frac{23}{4} (-1)^n - \frac{41}{9}(-2)^n - \frac{37}{36} + \frac{5}{6}(n+1)\right) z^n\\ &= \sum_{n \ge 0}\left(\frac{23}{4} (-1)^n - \frac{41}{9}(-2)^n - \frac{7}{36} + \frac{5}{6}n\right) z^n, \end{align} which immediately implies that $$a_n = \frac{23}{4} (-1)^n - \frac{41}{9}(-2)^n - \frac{7}{36} + \frac{5}{6}n.$$