# Finding a closed form $x_n$ for the recurrence relation $x_{n+2} = px_{n+1} + qx_n + r$

Given a recurrence relation: $$x_{n+2} = px_{n+1} + qx_n + r$$ Find the general term $x_n$ given initial conditions $x_1 = a$ and $x_2 = b$, where $a,b,p,q,r$ are some given numbers, $n \in \mathbb N$.

Since this is a non-homogeneous linear recurrence relation i've started with solving for $x_n^h$ which is a solution for homogeneous relation:

$$x_{n+2} - px_{n+1} - qx_n = 0 \\ \lambda^2-p\lambda - q = 0$$

I'm assuming here that two distinct roots $\lambda_{1,2}$ exist for this equation (single root case is handled similarly). So the general term is in the form:

$$x_n = C_1\lambda_1^{n-1}+C_2\lambda_2^{n-1}$$

With the initial condition it's possible to find the values for $C_1$ and $C_2$:

$$C_1 + C_2 = a \\ C_1\lambda_1 + C_2\lambda_2 = b$$

After solving the system of equation with respect to $C_1$ and $C_2$:

$$C_1 = \frac{b-a\lambda_2}{\lambda_1 - \lambda_2} \\ C_2 = \frac{b-a\lambda_1}{\lambda_2 - \lambda_1} \\$$

Which eventually results in:

$$x_n^h = \frac{(a\lambda_2 - b)\lambda_1^{n-1} - (a\lambda_1-b)\lambda_2^{n-1}}{\lambda_2 - \lambda_1}$$

Final solution consists of a sum of particular and homogeneous solutions, but that is where I got stuck. What is the way to find the particular solution for the given problem? I'm pretty new to such kind of problems so any details are very much appreciated.

upd:

Based on the technique in @rtybase answer here are my findings:

\begin{align} x_1 &= a \\ x_2 &= b \\ x_3 &= pb - qa + r \end{align}

Writing the system for $c_1, c_2, c_3$:

\begin{align} a &= c_1 + c_2 + c_3 \\ b &= c_1\lambda_1 + c_2\lambda_2 + c_3 \\ pb+qa+r &= c_1\lambda_1^2 + c_2\lambda_2^2 + c_3 \end{align}

Now solving for the coefficients gives a huge formula. The answer to this problem suggests that:

$$x_n = \frac{(\lambda_2(a+\gamma) - b -\gamma)\lambda_1^{n-1} - (\lambda_1(a + \gamma) - (b-\gamma))\lambda_2^{n-1}}{\lambda_2 - \lambda_1} - \gamma$$

Where:

$$\gamma = \frac{r}{p+q-1}$$

Unfortunately I was not able to arrive at exactly the same result, but testing my solution (not posting since it's monstrously big) using SameQ in Mathematica with the given answer shows that they are equivalent. Those transformations are not very obvious to me, so i skipped them since the answer matches the given one (yet the symbolic expressions are different)

Hint. From $$x_{n+2} = px_{n+1} + qx_n + r$$ $$x_{n+3} = px_{n+2} + qx_{n+1} + r$$ we have $$x_{n+3}-(p+1)x_{n+2}+(p-q)x_{n+1}+qx_{n}=0$$ with characteristic polynomial $$x^3-(p+1)x^2+(p-q)x+q=0$$ or $$(x-1)(x^2-px-q)=0 \iff (x-1)(x-\lambda_1)(x-\lambda_2)=0$$ and finally $$x_n=C_1\lambda_1^n+C_2\lambda_2^n+C_3$$ which, judging from the question, you know how to deal with.
Since you have $x_{n+2} = px_{n+1}+qx_n + r$ where $p,q,r$ are constants and $p+q \geq 2 > 1$ you can try with a constant sequence, $x_n \equiv k$ with $k \in \mathbb{R}$.