Recurrence relation $a_{n+1}a_{n-1} = 1 + a_n$

Question

Consider the recurrence relation: $a_{n+1}a_{n-1} = 1 + a_n$ with initial values $a_1=x$ and $a_2=y$.

Is this an example of a homogeneous equation or just a linear one? In any case does anyone have an idea how to solve this?

Answer 1

This equation is neither homogeneous nor linear.

Hint This particular recurrence relation is a reasonably well-known example of a periodic recurrence, that is, for some $p > 0$, we have $$a_{n + p} = a_n$$ for all $n$. With this is mind, compute $a_1, a_2, a_3, \ldots$; eventually one will find terms $a_{1 + p} = x, a_{2 + p} = y$. (Often one sees this example instead written, equivalently, in terms of the iterates $f^n$ of the map $$f : (x, y) \mapsto \left(y, \frac{1 + y}{x}\right) .)$$

With this in hand, one can readily write down the general formula for $a_n$ by giving the values for each residue class mod $p$:

$$a_n = \left\{ \begin{array}{cc} x, & n \equiv 1 \pmod p \\ y, & n \equiv 2 \pmod p \\ \displaystyle{\frac{1 + y}{x}}, & n \equiv 3 \pmod p \\ \vdots & \vdots \end{array} \right. .$$