0

Given $x_0 = 1, y_0 = 2, z_0 = 2$ solve the following recurrence relation for $x_n, y_n, z_n, n \in \Bbb{N}$:

\begin{cases} x_{n+1} = \frac{1}{2}x_n + y_n + 3z_n, \\ y_{n+1} = y_n + \frac{3}{2}z_n, \\ z_{n+1} = -\frac{1}{2}y_n - z_n. \\ \end{cases}

What do I approach this case with? I believe I have to transform it into simple linear case where each $x_n, y_n, z_n$ is given by the previous value in order to be able to apply eigendecomposition.

Are my thoughts correct? If not, what is the preferred method here?

Thanks in advance.

dxiv
  • 76,497
E.Z
  • 273
  • I think you mistyped the last equation. It probably is $z_{n+1}$ – polfosol Dec 17 '17 at 06:38
  • 1
    General hint: write in matrix form, then derive this. For a shortcut, note that adding the last two relations gives $y_{n+1}+z_{n+1}= \frac{1}{2}(y_n+z_n)$ so you can reduce the dimension by $1$ right away. – dxiv Dec 17 '17 at 06:51

2 Answers2

2

This is just a tip, and I assume that I was right and the last equation is $z_{n+1}=-\frac12 y_n-z_n$ which means $$z_n+z_{n+1}=-\frac12 y_n$$ on the other hand, the second equation leads to $$z_n=\frac23(y_{n+1}-y_n)$$so $z_{n+1}=\frac23(y_{n+2}-y_{n+1})$, and if you put this into the third equation you end up with $$\frac23(y_{n+2}-y_{n})=-\frac12y_n$$ Now you have a recursive equation only in terms of $y$. The rest should be straightforward.

polfosol
  • 9,245
1

While shortcuts may exist in special cases, the general case could be handled like this: We have a recursion $$r_{n+1}=Ar_n,$$ where $$A=\pmatrix{ \frac{1}{2}&1&3\cr 0&1&\frac{3}{2}\cr 0&-\frac{1}{2}&-1\cr }$$ and $$r_n=\pmatrix{ x_n\cr y_n\cr z_n\cr }.$$ We can write $A=BDB^{-1}$, where $$B=\pmatrix{ -2&1&0\cr -1&0&-3\cr 1&0&1\cr }$$ is the matrix formed of the eigenvectors of $A$ and the diagonal matrix $$D=\pmatrix{ -\frac{1}{2}&0&0\cr 0&\frac{1}{2}&0\cr 0&0&\frac{1}{2}\cr }$$ contains the eigenvalues. Obviously, $A^n=BD^nB^{-1}$, that means $r_n=A^nr_0=BD^nB^{-1}r_0$, and since $$r_0=\pmatrix{ 1\cr 2\cr 2\cr }$$ and $$B^{-1}r_0=\pmatrix{ 4\cr 9\cr -2\cr },$$ we finally arrive at $$r_n=\frac1{2^n}\pmatrix{ -8(-1)^n+9\cr -4(-1)^n+6\cr 4(-1)^n-2\cr }.$$