We have a recurrence relation:
$$a_n=1$$ $$a_{n-1}=x$$ $$a_{n-i}=xa_{n-i+1}-a_{n-i+2} $$ for $i=2,3,\ldots,n.$
How to find $a_0$ in terms of $x$? For a fixed $n$, I can solve it but it turns out very tedious for large $n$. I thought of guessing the cofficient of a general $a_i$ after finding $a_i$'s upto $i=n-10$ but to no avail. Can you help me to find $a_0$ for any given $n$?
We can use linear algebra. We can write the recurrence relation as follows:
\begin{equation}\left( \begin{array}{c} a_{n-i}\\a_{n-i+1} \end{array} \right) = M_x \cdot \left( \begin{array}{c} a_{n-i+1}\\a_{n-i+2} \end{array} \right)\end{equation}
where $i \geq 2$ and
\begin{equation}M_x=\left( \begin{array}{cc} x&-1\\1&0\end{array} \right)\end{equation}
So, for instance, we have that:
\begin{equation}\left( \begin{array}{c} a_{n-2}\\a_{n-1} \end{array} \right) = M_x \cdot \left( \begin{array}{c} a_{n-1}\\a_{n} \end{array} \right)\end{equation}
and
\begin{equation}\left( \begin{array}{c} a_{n-3}\\a_{n-2} \end{array} \right) = M_x \cdot \left( \begin{array}{c} a_{n-2}\\a_{n-1} \end{array} \right) = (M_x)^2 \cdot \left( \begin{array}{c} a_{n-1}\\a_{n} \end{array} \right)\end{equation}
So, in the end we'll have
\begin{equation}\left( \begin{array}{c} a_{0}\\a_{1} \end{array} \right) = (M_x)^{n-1} \cdot \left( \begin{array}{c} a_{n-1}\\a_{n} \end{array} \right) = (M_x)^{n-1} \cdot \left( \begin{array}{c} x\\1 \end{array} \right)\end{equation}
So now your solution hinges on your ability to calculate $(M_x)^{n-1}$. Do you think you can take it from here? A hint: diagonalization.
EDIT: We have that $M_x$ has eigenvalues $\lambda_1 = \frac12\cdot(x+\sqrt{x^2-4})$ and $\lambda_2 = \frac12\cdot(x-\sqrt{x^2-4})$. We may diagonalize it as $M_x = PDP^{-1}$ with
\begin{equation}P=\left( \begin{array}{cc} \lambda_1&\lambda_2\\1&1\end{array} \right)\end{equation}
\begin{equation}D=\left( \begin{array}{cc} \lambda_1&0\\ 0&\lambda_2\end{array} \right)\end{equation}
\begin{equation}P^{-1}=\frac{1}{\lambda_1-\lambda_2}\left( \begin{array}{cc} 1&-\lambda_2\\-1&\lambda_1\end{array} \right)\end{equation}
Working out $(M_x)^n$ we get that $$a_0 = \frac{({\lambda_1}^n-{\lambda_2}^n)x-({\lambda_1}^n\lambda_2 -{\lambda_2}^n\lambda_1)}{\lambda_1-\lambda_2}$$
Using that $$a^n-b^n = (a-b)\cdot \sum\limits_{k=0}^{n-1}a^{n-1-k}b^k$$we may simplify the expression to$$a_0 = x\cdot\left( \sum\limits_{k=0}^{n-1}{\lambda_1}^{n-1-k}{\lambda_2}^k\right)-\lambda_1\lambda_2\cdot\left( \sum\limits_{k=0}^{n-2}{\lambda_1}^{n-2-k}{\lambda_2}^k\right)$$
You can check for the first few values of $n$ that these are indeed polynomials in $x$:
\begin{equation}\begin{array}{cccccc} n&1&2&3&4&5 \\a_0&x&x^2-1&x^3-2x&x^4-3x^2+1&x^5-4x^3+3x\end{array}\end{equation}
One can notice that $\lambda_1\lambda_2 = 1$ to further modify the formulas for $a_0$, but it doesn’t really get much better than this.
$$a_0 = \frac{({\lambda_1}^n-{\lambda_2}^n)x-({\lambda_1}^{n-1}-{\lambda_2}^{n-1})}{\lambda_1-\lambda_2}$$
$$a_0 = x\cdot\left( \sum\limits_{k=0}^{n-1}{\lambda_1}^{n-1-k}{\lambda_2}^k\right)- \left( \sum\limits_{k=0}^{n-2}{\lambda_1}^{n-2-k}{\lambda_2}^k\right)$$