Is it possible to find a closed form for the nth term of the following recurrence relation
$$A_n = x_nA_{n-1} + A_{n-2}$$
where $A_{-1} = 1$ and $A_0$ equals some constant.
I know the values of $x_1$, $x_2$, ..., $x_k$ and these values repeat after $k$. For eg, $x_{k+1} = x_1$, $x_{k+2} = x_2$ and so on.
I tried to define $A_i$ as a piecewise function but since $A_i$ is a general function, values of $x_i$ and the repeating period $k$ may differ for different experiments. I also tried finding the first few terms but I couldn't observe any pattern.
If it is possible to find a closed form, can you please provide some hints or readings to approach this?
You have that
$$\begin{align} % \begin{bmatrix} A_{n} & A_{n - 1} \end{bmatrix} & = \begin{bmatrix} A_{n - 1} & A_{n - 2} \end{bmatrix} \begin{bmatrix} x_{n} & 1 \\ 1 & 0 \end{bmatrix} \\ % & = \begin{bmatrix} A_{n - 2} & A_{n - 3} \end{bmatrix} \begin{bmatrix} x_{n - 1} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x_{n } & 1 \\ 1 & 0 \end{bmatrix} \\ % & = \begin{bmatrix} A_{n - 3} & A_{n - 4} \end{bmatrix} \begin{bmatrix} x_{n - 2} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x_{n - 1} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x_{n } & 1 \\ 1 & 0 \end{bmatrix} \\ % \vdots \\ % & = \begin{bmatrix} A_{0} & A_{-1} \end{bmatrix} \prod_{r = 1}^n{ \begin{bmatrix} x_r & 1 \\ 1 & 0 \end{bmatrix}} \\ \end{align}$$
Since $x$ is periodic, you can choose the unique $(p, q)$ such that $n = pk + q$ for $0 \le q < k$:
$$\begin{align} % \prod_{r = 1}^n{ \begin{bmatrix} x_r & 1 \\ 1 & 0 \end{bmatrix}} % &= \prod_{r = 1}^{pk + q}{ \begin{bmatrix} x_r & 1 \\ 1 & 0 \end{bmatrix}} \\ % &= \left(\prod_{r = 1}^{q}{ \begin{bmatrix} x_r & 1 \\ 1 & 0 \end{bmatrix}}\right) \left(\prod_{r = q+1}^{pk+q}{ \begin{bmatrix} x_r & 1 \\ 1 & 0 \end{bmatrix}}\right) \\ % &= \left(\prod_{r = 1}^{q}{ \begin{bmatrix} x_r & 1 \\ 1 & 0 \end{bmatrix}}\right) \left(\prod_{r = 1}^{k}{ \begin{bmatrix} x_r & 1 \\ 1 & 0 \end{bmatrix}}\right)^p \end{align}$$
which reduces the problem to approximiately* $O(k)$ which is the lowest bound since you have $k$ unique $x$ values as inputs.
(Approximately because of considerations of whether there are finite fields, or calculating partial components of a Chinese Remainder Representation, etc. Exponential functions have very large outputs.)