Show an identity from Friezes Let $a$ and $b$ be two variables. Consider the recurrence below:
$$u_{n+2}=\frac{1+u_{n+1}^{2}}{u_{n}}$$
with $u_{0}=a$ and $u_{1}=b$ with $ab\neq 0$. I know how to show that $u_{n}$ must satisfy the following linear recurrence:
$$ u_{n+2}=\frac{a^2+b^2+1}{ab}u_{n+1}-u_{n}.$$
Using Maple I saw that you can find two matrices $X$ such that:
$$ u_{n} = \frac{1}{a^{n-1}b^{n-2}}\big(1 \ \ b\big)X^{n-2}\left(\begin{array}{c} 1 \\b\end{array}\right)$$
There is one having rational entries and $M$ be the matrix bellow:
$$M=\left(\begin{array}{cc} a^2+1 & b \\ b & b^2 \end{array}\right).$$
which has polynomial entries. It can be shown that $M$ satisfy the matrix equation above for $X$, but where $M$ comes from ?
can we show this without using Friezes ? (see: http://www.sciencedirect.com/science/article/pii/S0001870810002136). 
My Question: Can we establish a similar result for the case:
$$ v_{n+2} = \frac{1+v_{n+1}^3}{v_{n}} $$
with $v_0=a$ and $v_1=b$, that is, can we find a matrix $Y$ of some size such that $$v_{n} = F(a,b,Y,n)$$
for some polynomial $g$ in the matrix variable $Y$ given by  $g(Y)=F(a,b,Y,n)$.

In the general case: \begin{equation} 
w_{n}:=
 \begin{cases}\label{Ecuacion1}
 \displaystyle{\frac{1+w_{n-1}^d}{w_{n-2}}} & if\ n\ \text{is even},\\
 &\\ \displaystyle{\frac{1+w_{n-1}^c}{w_{n-2}}} & if\ n\ \text{is odd}.
 \end{cases} \end{equation} 
  can we find similar solutions ? Here $d,c$
  are positive integers and $w_0=x$ and $w_1=y$ where $x$ and $y$ are
  non zero values.

 A: A partial answer (just about the first part).
If we have a sequence $\{u_n\}_{n\geq 0}$ such that $u_{n+2}=K u_{n+1}-u_n$, its characteristic polynomial is $p(x)=x^2-Kx+1$, with roots $\zeta_{\pm}=\frac{K\pm\sqrt{K^2-4}}{2}$ fulfilling $\zeta_+ +\zeta_-=K$ and $\zeta_+ \zeta_- = 1$. The closed form for $u_n$ is given by
$$ u_n = C_+ \zeta_+^n + C_- \zeta_-^n $$
with $C_+,C_-$ depending on the initial conditions. Given such closed form, we have
$$\begin{eqnarray*}u_{n}u_{n+2}-u_{n+1}^2 &=&C_+ C_-\left(\zeta_+^2+\zeta_-^2-2\right)=C_+ C_-\left(K^2-4\right) \end{eqnarray*}$$
and given two arbitrary values for $u_0$ and $u_1$ we may find a value for $K$ such that the RHS of the previous line equals one. This proves the first part of the claim: any sequence fulfilling the recurrence $u_{n+2}=\frac{1+u_{n+1}^2}{u_n}$ matches a linear recurrent sequence with a characteristic polynomial of the $x^2-Kx+1$ kind.

About the second part.
Linear recurrent sequences have an exponential growth/decay, while any sequence fulfilling $u_n u_{n+2} \approx u_{n+1}^{\color{red}3}$ has a super-exponential growth/decay: $u_n\approx \exp\left(D\left(\frac{3+\sqrt{5}}{2}\right)^n\right)$. It follows that the above phenomenon does not extend to the cubic (or worse) case.
