Closed form for these polynomials?

Question

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$$

Answer 1

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}$.

Answer 2

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}$.