How do I solve the recurrence relation: $X(n) + 2X(n-1) - 8X(n-2) = 10$?

Question

How do I solve the recurrence relation: $X(n) + 2X(n-1) - 8X(n-2) = 10$?

I understand if the 10 was replaced by the 0, we could use the characteristic equation, but with that constant I am completely lost..

The initial conditions are $X(0) = 0$ and $X(1) = 14$

Answer 1

Hint:

You have $X(n) + 2X(n-1) - 8X(n-2) = 10$

so you also have $X(n-1) + 2X(n-2) - 8X(n-3) = 10$

and thus by subtraction $X(n) + X(n-1) - 10X(n-2) + 8X(n-3) = 0$ which you can solve in the usual way (the cubic factors nicely)

You may also want an additional starting value, and you can easily find the value of $X(2)$

Answer 2

Let $X(n)=Y(n)+a$

$$10=Y(n)+a+2\{Y(n-1)+a\}-8\{Y(n-2)+a\}$$

$$=Y(n)+2Y(n-1)-8Y(n-2)-5a$$

Set $-5a=10\iff a=-2$

Now use this to solve $$Y(n)+2Y(n-1)-8Y(n-2)=0$$

Answer 3

$x(n)=-2 \left((-1)^n 2^{2 n}-2^{n+1}+1\right)$

There are some methods defined in

https://en.wikipedia.org/wiki/Recurrence_relation

Find the string "Solving homogeneous linear recurrence relations with constant coefficients" there.

And here is the Mathematica command:

RSolve[{x[n] == 10 + 8 x[n - 2] - 2 x[n - 1], x[0] == 0, x[1] == 14}, x[n], n]

Answer 4

The method for solving linear equations is always the same.

• Start by solving the homogeneous equation: $$X(n)+2X(n-1)-8X(n-2)=0$$

It has characteristic equation $x^2+2x-8=0\iff (x-2)(x+4)=0$

The roots are $2$ and $-4$ so the solution is $X_h(n)=a\times 2^n+b\times(-4)^n$.

• Find one particular solution for the RHS:

You have to view $10$ as $10\times 1^n$.

Since $1$ was not a root of the characteristic equation, you can search for a constant as well (else it would be a polynomial of degree $1$ or more).

So here: $X_p(n)=c\quad$ gives $\quad c+2c-8c=10\iff -5c=10\iff c=-2$

• Solve for the initial conditions

The general solution is $X(n)=X_h(n)+X_p(n)=a2^n+b(-4)^n-2$

$\begin{cases}X(0)=0=a+b-2\\X(1)=14=2a-4b-2\end{cases}\iff\begin{cases}a+b=2\\a-2b=8\end{cases}\iff\begin{cases}a=4\\b=-2\end{cases}$

Finally $$X(n)=4\times 2^n-2\times(-4)^n-2$$

---

Here is some details about finding the particular solution, i.e. to eliminate the RHS.

All linear equations with constant coefficients have solutions of homegeneous equation of the form $$X(n)=a r_1^n+br_2^n+cr_3^n+\cdots$$

Let assume the RHS is of the form $P(n)\alpha^n$

If $\alpha$ is not one of $r_1,r_2,r_3,\cdots$ then you can search for a particular solution $X(n)=Q(n)\alpha^n$ with $\deg(Q)=\deg(P)$

If $\alpha$ is one of the roots then search for $\deg(Q)=\deg(P)+1$

If it is a double root then serach for $\deg(Q)=\deg(P)+2$ and so on...

In our case the RHS was $10=10\times 1^n$ with $\alpha=1$

Since $1$ was not a root, we search for $Q(n)1^n$ with $\deg(Q)=\deg(10)=0$ which is just a constant polynomial, i.e. $X(n)=c$