# Show that there is a unique sequence of positive integers $(a_n)$ satisfying $a_1=1,a_2=2,a_4=12,a_{n+1}a_{n-1}=a_n^2\pm 1$

Show that there is a unique sequence of positive integers $(a_n)$ satisfying the following conditions.
$$a_1=1,a_2=2,a_4=12,a_{n+1}a_{n-1}=a_n^2\pm 1$$

I approached the problem to find out,

$a_3=4 \pm 1$
$a_2a_4=a_3^2\pm1 \implies 24\mp1=a_3^2 \implies a_3=5$ as $a_n \in \mathbb{N}$
I could not do anything more. Even, I could not understand what should I show to prove that the sequence is unique. Please help.

• To find $a_5$ you have $a_3*a_5=a_4^2\pm 1$. Therefore $a_5*5=144 \pm 1$, and we can see that $a_5=145/5=29$. You need to show that for each $a_n$, $a_{n+1}\equiv \pm 1 \pmod{a_n}$, see oeis.org/A000129 for some possible help. – Foo Barrigno Mar 7 '14 at 12:25

Hint: For uniqueness, let $a_n$ and $b_n$ be two different sequences which satisfy the conditions. Suppose the first point at which they differ is $n+1$ - you know $n$ is at least $3$ because the sequences agree up to the fourth term. Then follow through the implications of that. It is useful to prove existence first because you may need to know something about the size of the terms.

Hint: for existence the sequence $1,2,5,12 \dots$ satisfies a simple linear recurrence relation, which can be used to show by induction that there is always a next term, and can be used to determine the general term.

The sequence is well known in other contexts - Pell's equation and continued fractions - where it is paired with $1,3,7,17 \dots$

Suppose that after $a_n$, that both possible values of $a_{n+1}$ , $\frac{a_n\,^2 - 1} {a_{n-1}}$ and $\frac{a_n\,^2 + 1} {a_{n-1}}$, are both integers.

Then $$\begin{cases} a_{n-1} | a_n\,^2 - 1 \\ a_{n-1} | a_n\,^2 + 1 \end{cases}$$

So $a_{n-1}$ can only be $1$ or $2$ if the sequence forks into to valid sequences after $a_n$. So if the sequence is increasing, then it is unique for $a_{n-1} > 2$.

For existence, just look at the sequence mechanically first:

$$\begin{array} {c|c} n & a_n \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 5 \\ 4 & 12 \\ 5 & 29 \\ 6 & 70 \\ 7 & 169 \end{array}$$

It seems to be geometric with a ratio of $\frac {169} {70} \text{ is about } 2.414 \text{ is about } 1 + \sqrt{2}$. Checking $a_n = x(1 + \sqrt{2})^n + y (1 - \sqrt{2})^n$ gets $x = 2^{-3/2}, y = -2^{-3/2}$.

Final verification of existence, put value of $a_n$ into: $$a_n = \frac{a_{n-1}\,^2 - (-1)^n} {a_{n-2}}$$

$$a_{n+1}a_{n-1}=a_n^2\pm 1$$ reminds me of Cassini's identity for the Fibonacci numbers $$F_n$$: $$F_{n-1}F_{n+1}-F_{n}^{2}=(-1)^{n}$$ This comes from the matrix formulation: $$F_{n-1}F_{n+1} - F_n^2 =\det\left[\begin{matrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{matrix}\right] =\det\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^n =\left(\det\left[\begin{matrix}1&1\\1&0\end{matrix}\right]\right)^n =(-1)^n.$$ In our case, we have exactly the same thing: $$a_{n-1}a_{n+1} - a_n^2 =\det\left[\begin{matrix}a_{n+1}&a_n\\a_n&a_{n-1}\end{matrix}\right]$$ So we guess that $$a_n$$ satisfies a linear recurrence such as $$a_{n+2}=\alpha a_{n+1} + \beta a_n$$ so that $$\left[\begin{matrix}a_{n+1}&a_n\\a_n&a_{n-1}\end{matrix}\right] = A^n \left[\begin{matrix}a_{1} \\ a_0 \end{matrix}\right] = A^n \left[\begin{matrix}1 \\ 0 \end{matrix}\right]$$ Given the first few value of $$a_n$$, we get $$\alpha=2$$ and $$\beta=1$$: $$a_{n+2}=2 a_{n+1} + a_n, \quad a_0=0, \quad a_1=1$$ and so $$a_n= \frac{(1 + \sqrt2)^n - (1 - \sqrt2)^n}{2\sqrt2}$$ This is OEIS/A000129.

The corresponding matrix is $$A=\left[\begin{matrix}2&1\\1&0\end{matrix}\right]$$ which has determinant $$-1$$ as expected.