Solving this Recurrence Relation in terms of previous values.

Question

What will be the value of $X(n)$ and $Y(n)$ in terms of given $n,X(0),Y(0)$.

$$ X(n) = X(n-1) + Y(n-1) \\ Y(n) = 2X(n-1) + Y(n-1) $$

Answer 1

This relation can be written as $$\begin{pmatrix}X(n) \\ Y(n)\end{pmatrix} = \begin{pmatrix}1 & 1 \\ 2 & 1\end{pmatrix} \begin{pmatrix}X(n - 1) \\ Y(n - 1)\end{pmatrix}. $$

If you define $A = \begin{pmatrix}1 & 1 \\ 2 & 1\end{pmatrix}$, this yields $$\begin{pmatrix}X(n) \\ Y(n)\end{pmatrix} = A^n \begin{pmatrix}X(0) \\ Y(0)\end{pmatrix}. $$

Now you only need to calculate the powers of $A$, this works straightforward via diagonalzation.

Answer 2

Observe that: $$ \begin{matrix} x_n - x_{n-1} = y_{n-1} \\ y_n - y_{n-1} = 2x_{n-1} \end{matrix} $$ by subtracting the first relation for $y_n$ and $y_{n-1}$: $$ x_{n+1} - x_n - x_n + x_{n-1} = y_n - y_{n-1} = 2x_{n-1} $$ Thus: $$ x_{n+1} - 2x_n - x_{n-1} = 0 $$ which is a linear one variable recurrence.

Answer 3

This linear recurrence may be represented matricially: $$\begin{bmatrix}X_n\\Y_n\end{bmatrix} = \begin{bmatrix}1&1\\2&1\end{bmatrix} \begin{bmatrix}X_{n-1}\\Y_{n-1}\end{bmatrix},$$ hence $$\begin{bmatrix}X_n\\Y_n\end{bmatrix} = \begin{bmatrix}1&1\\2&1\end{bmatrix}^n\begin{bmatrix}X_0\\Y_0\end{bmatrix}.$$ Set $\;A= \begin{bmatrix}1&1\\2&1\end{bmatrix}$. To compute $A^n$, you have to find the Jordan normal form of $A$: $J=D+N$, where $D$ is a diagonal matrix, with the eigenvalues of $A$ on the diagonal, and $N$ is a nilpotent matrix which commutes with $D$. It is then easy to ompute powers of $J$, as we can use the binomial formula, and $N$ has a finite number of non-zero powers. The last step consists in going back from $J^n$ to $A^n$ by the change of basis formula: if $J=P^{-1}AP$,we also have $J^n=P^{-1}A^nP$, whence $\;A^n=PJ^nP^{-1}$.

In the present case it is simple: $A$ is diagonalisable: its eigenvalues are $1\pm\sqrt2$, the corresponding eigenvectors are $\;\begin{bmatrix}1\\\mp\sqrt2\end{bmatrix}$, so that the change of basis matrix is $$P=\begin{bmatrix}1&1\\-\sqrt2&\sqrt2\end{bmatrix},\quad D=\begin{bmatrix}1+\sqrt2 & 0\\-0&1-\sqrt2\end{bmatrix},\quad P^{-1}=\frac14\begin{bmatrix}2&-\sqrt2\\2&\sqrt2\end{bmatrix}, $$

whence, if I'm not mistaken: $$A^n=\frac14\begin{bmatrix}2\bigl((1+\sqrt2)^n+((1-\sqrt2)^n\bigr) &\sqrt2\bigl((1-\sqrt2)^n-((1+\sqrt2)^n\bigr)\\2\sqrt2\bigl((1-\sqrt2)^n-((1+\sqrt2)^n\bigr)&2\bigl((1+\sqrt2)^n+((1-\sqrt2)^n\bigr)\end{bmatrix}.$$

Answer 4

One instructive solution is to use generating functions. Define:

$\begin{align} f(z) &= \sum_{n \ge 0} X(n) z^n \\ g(z) &= \sum_{n \ge 0} Y(n) z^n \end{align}$

Shift indices to get:

$\begin{align} X(n + 1) &= X(n) + Y(n) \\ Y(n + 1) &= 2 X(n) + Y(n) \end{align}$

Multiply the recurrences by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:

$\begin{align} \frac{f(z) - X(0)}{z} &= f(z) + g(z) \\ \frac{g(z) - Y(0)}{z} &= 2 f(z) + g(z) \end{align}$

This gives:

$\begin{align} f(z) &= \frac{X(0) + (Y(0) - X(0)) z}{1 - 2 z - z^2} \\ g(z) &= \frac{Y(0) - 2 (Y(0) - 2 X(0)) z}{1 - 2 z - z^2} \end{align}$

This can be written as partial fractions, the denominator factors as $(1 - (1 - \sqrt{2}) z) (1 - (1 + \sqrt{2}) z)$. The result is quite ugly, but you'll get terms of the form:

$$ \frac{1}{1 - \alpha z} = \sum_{n \ge 0} \alpha^n z^n $$

so that the coefficients of $f$ and $g$ are immediate.