# Solving recurrence relation with each term defined in terms of the 2 preceding terms

$$\{ X_n \} := X_0 = 1 , X_1 = 1 , x_{n+1} = X_n + 2X_{n-1}$$ $$\{Y_n\} := Y_0 = 1, Y_1 = 7, Y_{n+1} = 2Y_n + 3 Y_{n-1}$$

How would one solve these recurrence relations?

For the first one I tried telescoping by dividing $X_n$ by $2^{n-2}$ in an attempt to cancel across 2 lines (I hope you get what I mean, I don't have the Latex skill to show this). But this got pretty ugly because even after most terms had cancelled, I was left with an instance of $X_{n-1}$.

Even with this I tried to "fall backwards spirally" coming up with expression for $X_k$ in terms of $X_{k-1}$ and so on until I hit rock bottom, but this got reallly ugly.

Motivation I'm trying to solve this problem.

Let $\{X_n\}$ and $\{Y_n\}$ denote two sequences of integers defined as follows: $X_0 = 1,\ X_1 = 1,\ X_{n + 1} = X_n + 2X_{n - 1} \quad (n = 1,2,3,\ldots)$, $Y_0 = 1,\ Y_1 = 7,\ Y_{n + 1} = 2Y_n + 3Y_{n - 1} \quad (n = 1,2,3,\ldots)$. Prove that, except for the "1", there is no term which occurs in both sequences.

My idea is to try and come up with closed forms for each recurrence and equate them using 'k' and 'm' as place-holders, and show that there are no integer solutions for either apart from 1.

The characteristic equation of the first linear reccurence relation is: $x^2 - x - 2 = (x-2)(x+1)=0$. Therefore we have $x_n = A\cdot 2^n + B \cdot (-1)^n$. Plug in the first two values for $n=0,1$ and you will find the values of $A$ and $B$. Similarly do the same for $Y_n$.
• @Airdish In the reccurence relation just substitute $x_n$ with $x^n$, $x_{n-1}$ with $x^{n-1}$ and so on. Eventually you would be able to cancel out some $x$'s. – Stefan4024 Sep 10 '16 at 18:59
• Oh ok. Is the second recurrence $y_n = 2\cdot 3^n + (-1)^{n+1}$ ? – Airdish Sep 11 '16 at 4:05
• @Airdish Yeah, it's true. While the first one is $x_n = \frac{2^{n+1} + (-1)^n}{3}$ – Stefan4024 Sep 11 '16 at 8:56