1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.