Closed form for these polynomials? I have a recurrence relation for these polynomials $p_i(x) $:
\begin{align}
p_0(x)&=0 \\
p_1(x)&=1 \\
p_{2i}(x)&=p_{2i-1}(x)-p_{2i-2}(x) \\
p_{2i+1}(x)&=xp_{2i}(x)-p_{2i-1}(x) \\
\end{align}
I've been unable to find a closed form, but the recurrence is simple so it seems there might be one. However the polynomials arise in a deep context, so maybe not. Is it possible to find one?
The context:
Let $G=\mathbb Z_2*\mathbb Z_2$, with generators $s, t$. Let $M$ be the free module over the ring $\mathbb Z[c, d] $ of rank $2$ with basis $x_1,x_2$. Define
\begin{align}
s(x_1)&=-x_1 \\
t(x_2)&=-x_2 \\
s(x_2)&=cx_1+x_2 \\
t(x_1)&=x_1+dx_2 \\
\end{align}
Define elements
\begin{align}
y_0&=x_1 \\
y_{2i+1}&=t(y_{2i}) \\
y_{2i}&=s(y_{2i-1}) \\
\end{align}
Then
$$y_i=p_{2\lfloor i/2\rfloor+1}(cd)x_1+dp_{2\lceil i/2\rceil}(cd)x_2$$
 A: Let $$u_i=
\begin{bmatrix} 
    p_{2i}(x)\\
    p_{2i+1}(x)
\end{bmatrix}$$
Then $$u_i=\begin{bmatrix} 
-1 && 1\\
0 && -1
\end{bmatrix}u_{i-1} + 
\begin{bmatrix} 
0 && 0\\
x && 0
\end{bmatrix}u_i
$$
In other words,
$$\begin{bmatrix} 
1 && 0\\
-x && 1
\end{bmatrix}u_{i}= 
\begin{bmatrix} 
-1 && 1\\
0 && -1
\end{bmatrix}u_{i-1}$$
This implies 
$$u_i=\begin{bmatrix} 
-1 && 1\\
-x && x-1
\end{bmatrix}u_{i-1}$$
For a closed form, you need to compute powers of $\begin{bmatrix} 
-1 && 1\\
-x && x-1
\end{bmatrix}$.
A: Writing $v_n=\begin{pmatrix} p_{2n+1} \\ p_{2n}\end{pmatrix}$, the recurrence can be written as $v_{n+1}=Av_n$ where $$A=\begin{pmatrix} x-1 & -x \\ 1 & -1\end{pmatrix}.$$  So, we have $v_n=A^nv_0$ for all $n$, and the question is just about computing powers of the matrix $A$.  This can be done by diagonalizing: the characteristic polynomial of $A$ is $q(t)=t^2-(x-2)t+1$.  Picking a root $r$ of $q$ over an algebraic closure of $\mathbb{Q}(x)$, then $r$ and $s=x-2-r$ are the eigenvalues of $A$ with eigenvectors $\begin{pmatrix}r+1\\ 1\end{pmatrix}$ and  $\begin{pmatrix}s+1\\ 1\end{pmatrix}$.  So we can write $$A=B\begin{pmatrix} r & 0 \\ 0 & s\end{pmatrix}B^{-1}$$ where $B=\begin{pmatrix} r+1 & s+1 \\ 1 & 1\end{pmatrix}$.  If I have not screwed up the calculation, this gives the following "explicit" formula for $A^n$:  $$A^n=\frac{1}{r-s}\begin{pmatrix} r^n(r+1)-s^n(s+1) & (r+1)(s+1)(s^n-r^n) \\ r^n-s^n & s^n(r+1) - r^n(s+1)\end{pmatrix}.$$  Applying this to $v_0=\begin{pmatrix} 1 \\ 0\end{pmatrix}$ we get $$p_{2n+1}=\frac{r^n(r+1)-s^n(s+1)}{r-s}$$ and $$p_{2n}=\frac{r^n-s^n}{r-s}.$$  Note that by the quadratic formula, we can write $$r=\frac{x-2+\sqrt{x^2-4x}}{2}$$ and $$s=\frac{x-2-\sqrt{x^2-4x}}{2}$$ and so substituting these into the formulas above gives a closed form for $p_{2n+1}$ and $p_{2n}$ in terms of $x$.  Or, for an explicit formula without any radicals, we can expand out $r^n$ and $s^n$ to get $$p_{2n}=\frac{1}{2^{n-1}}\sum_{0\leq 2k<n}\binom{n}{2k+1}(x^2-4x)^k(x-2)^{n-2k-1}$$ and then $p_{2n+1}$ is just $p_{2n}+p_{2n+2}$.
