Variable Piecewise Recurrence Relation 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?
 A: 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.)
