Find the general solution of the recurrence relation $3x_{n+2} − x_{n+1} − 2x_{n} = 5$.

Question

Find the general solution of the recurrence relation $3x_{n+2} − x_{n+1} − 2x_{n} = 5$.

Attempt

First I found the auxiliary equation:

$3 \lambda ^ 2 - \lambda - 2 = 0$.

To get the solutions:

$\lambda = 1$ , $\lambda = -2/3$. This lead to a general solution of: $$x_{n} = A.(-\frac{2}{3})^n + B.$$

The issue for me arises when trying to find a particular solution. Plugging in the usual solution $x_{n} = c$ does not work here as: $3c - c - 2c = 5.$

This leads to $0 = 5.$ I'm assuming I'm doing something wrong, can someone give me a hand?

Answer 1

Define $y_n=x_n-n\implies x_n=y_n +n$, Then we have that $$3(y_{n+2}+(n+2))-(y_{n+1}+(n+1))-2(y_n+n)=5\implies 3y_{n+2}-y_{n+1}-2y_n=0 $$ From here what you have done is correct for $y_n$ and not $x_n$, id est $y_n=A\cdot\left(\frac{-1}{3}\right)^n+B \implies x_n=A\cdot\left(\frac{-1}{3}\right)^n+B+n$ where $A,B$ are determined by initial conditions. linear difference equation you've formed is used to solve recuurences of the form $x_{n+2}=ax_{n+1}+bx_{n}$, otherwise if you have that $x_{n+2}=ax_{n+1}+bx_{n}+c$, then you need to make addition of an appropriate linear function to $x_n$, just like i defined $y_n$. In 'most' cases a constant will work and when it does not, then $nd$ would work, where $d$ is a constant(which is $1$ in this case).

Answer 2

Your general solution is for the homogeneous equation

$3x_{n+2}-x_{n+1}-2x_n=0.$

To solve your given inhomogeneous equation

$3x_{n+2}-x_{n+1}-2x_n=5,$

you need to add one or more fixed terms so that when the initial conditions work properly. We call these fixed terms a particular solution of the inhomogeneous equation.

There are several methods for finding such a particular solution. Here I will look into a "brute force" approach that reveals the origin of such terms.

Given your original equation

$3x_{n+2}-x_{n+1}-2x_n=5,$

you can increment the index by one unit to get

$3x_{n+3}-x_{n+2}-2x_{n+1}=5.$

Now you can take the difference between these equations and get

$3x_{n+3}-4_{n+2}-x_{n+1}+2x_n=0.$

Now the equation is homogeneous and you can solve it by the standard method for homogeneous equations with constant coefficients. The indicial roots you found before, $\lambda=1$ and $\lambda=-2/3$, carry over from your original second-order equation. Factoring those out you find a second root $\lambda=1$ that was introduced by taking the difference.

With the double indicial root $\lambda=1$ you have a general solution to your modified equation:

$x_n = A(-2/3)^n+B\color{blue}{+Cn}$

versus your original homogeneous solution

$x_n = A(-2/3)^n+B.$

The blue term contains the extra piece you need for the original inhomogenous equation, the particular solution you need for that equation. To wit, the equation

$3x_{n+2}-x_{n+1}-2x_n=5$

will have a solution of the form

$x_n = A(-1/3)^n+B+Cn$

for some value of $C$. You can find this value of $C$ by putting in your initial conditions $x_0=a_0, x_1=a_1$; you find that for all such initial conditions the equation holds by rendering

$\color{blue}{C=1}.$

So your solution with the particular term included is

$\color{blue}{x_n = A(-2/3)^n+B+n},$

and you get $A$ and $B$ if you are given initial values for $x_0$ and $x_1$.

Answer 3

Here's an alternative approach that uses generating functions and doesn't require any guessing of the functional form of $x_n$. Let $f(z)=\sum_{n \ge 0} x_n z^n$ be the ordinary generating function. The recurrence relation $$3x_{n+2} − x_{n+1} − 2x_{n} = 5$$ implies that $$3 \sum_{n \ge 0} x_{n+2} z^{n+2} − \sum_{n \ge 0} x_{n+1} z^{n+2} − 2 \sum_{n \ge 0} x_{n} z^{n+2} = 5 \sum_{n \ge 0} z^{n+2}.$$ Equivalently, $$3 (f(z) - x_0 - x_1 z) − z (f(z) - x_0) − 2 z^2 f(z) = \frac{5z^2}{1-z}.$$ Solving for $f(z)$ yields \begin{align} f(z) &= \frac{5z^2/(1-z) + 3 x_0 + (3 x_1 - x_0) z}{3 − z − 2 z^2} \\ &= \frac{3 x_0 + (3 x_1 - 4 x_0) z + (x_0 - 3 x_1 + 5) z^2}{(1-z)^2(3+2z)} \\ &= \frac{A}{1-z} + \frac{B}{(1-z)^2} + \frac{C}{1+2z/3} \\ &= A \sum_{n \ge 0} z^n + B \sum_{n \ge 0} \binom{n+1}{1} z^n + C \sum_{n \ge 0} (-2z/3)^n \\ &= \sum_{n \ge 0} (A + B(n+1) + C (-2/3)^n) z^n, \end{align} which implies that $$x_n = A + B(n+1) + C (-2/3)^n,$$ where you can determine the constants $A$, $B$, and $C$ by imposing the initial conditions.