If $a_{n+1}=\frac {a_n^2+5} {a_{n-1}}$ then $a_{n+1}=Sa_n+Ta_{n-1}$ for some $S,T\in \Bbb Z$.

Question

Question

Let $$a_{n+1}:=\frac {a_n^2+5} {a_{n-1}},\, a_0=2,a_1=3$$

Prove that there exists integers $S,T$ such that $a_{n+1}=Sa_n+Ta_{n-1}$.

Attempt

I calculated the first few values of $a_n$: $a_2=7,a_3=18, a_4=47$ so I'd have the system of diophantine equations: $$ 7=3S+2T\\ 18=7S+3T\\ 47=18S+7T $$

Now: it seems that all of the $a_i$ are pairwise coprime, so these equations should always have solutions, but how could I check that the intersection of all the solutions is not $\emptyset$?

Answer 1

From the initial data and recursion, compute $a_0=2,a_1=3,a_2=7,a_3=18$.

If we have an $S$ and $T$ so that $a_{n+1}=Sa_n+Ta_{n-1}$, then $$ \begin{bmatrix}3&2\\7&3\end{bmatrix}\begin{bmatrix}S\\T\end{bmatrix}=\begin{bmatrix}7\\18\end{bmatrix}\implies\begin{bmatrix}S\\T\end{bmatrix}=\begin{bmatrix}3&2\\7&3\end{bmatrix}^{-1}\begin{bmatrix}7\\18\end{bmatrix}=\begin{bmatrix}3\\-1\end{bmatrix} $$ Now, to verify that the linear recursion $a_{n+1}=3a_n-a_{n-1}$ implies $$ a_{n+1}a_{n-1}-a_n^2=5\tag{1} $$ Assume the linear recursion, then $$ \begin{align} &\left(a_{n+2}a_n-a_{n+1}^2\right)-\left(a_{n+1}a_{n-1}-a_n^2\right)\\ &=(3a_{n+1}-a_n)a_n-a_{n+1}^2-a_{n+1}a_{n-1}+a_n^2\\ &=3a_{n+1}a_n-a_{n+1}^2-a_{n+1}a_{n-1}\\ &=a_{n+1}(3a_n-a_{n-1})-a_{n+1}^2\\ &=a_{n+1}^2-a_{n+1}^2\\ &=0\tag{2} \end{align} $$ Thus, the linear recursion and $(1)$ imply that $$ a_{n+2}a_n-a_{n+1}^2=5\tag{3} $$

Answer 2

Note that the base case $n=1$ is easily verifiable. Since the sequence is increasing, $a_n >1$ for $n>1.$

Now assume for all natural numbersn $n$ less than or equal to $k$ that:

$a_{n+1} = Pa_n +Qa_{n-1}$ has integer solutions $Q$ and $P$ (inductive hypothesis).

Then note that:

$a_{k+2} =M_1a_{k+1} +N_1a{k}$ $\Leftrightarrow$ $a_{k+2}=M_1(M_2a_k +N_2a_{k-1}) +N_1(M_3a_{k-1} +N_3a_{k-2})$$=...=C_{1}a_1 +C_2a_0=3C_1 +2C_2 $ for some arbitrary integers $C_1$ and $C_2$

But since the Diophantine equation $N=ax+by$ has integer solutions $x$ and $y$ for all $N>ab-a-b$, and since $a_{k+2} >1$, it follows that there exists integer solutions $C_1$ and $C_2$.

Answer 3

Assume that $a_n$ can be expressed as $a_{n+1}=Sa_n+Ta_{n-1}$.

Then $a_n$ is expressed as $$a_n=A\alpha^n+B\beta^n$$ Then $$a_{n+1}a_{n-1}=(A\alpha^{n+1}+B\beta^{n+1})(A\alpha^{n-1}+B\beta^{n-1})$$ $$=A^2\alpha^{2n}+AB\alpha^{n-1}\beta^{n+1}+AB\alpha^{n+1}\beta^{n-1}+B^2\beta^{2n}$$ And $$a_n^2+5=A^2\alpha^{2n}+2AB\alpha^n\beta^n+B^2\beta^{2n}+5$$ Therefore, $$AB(\alpha^{n-1}\beta^{n+1}+\alpha^{n+1}\beta^{n-1})=2AB\alpha^n\beta^n+5$$ should hold for all $n$.

This is possible only when $\alpha\beta=1$ and if $\alpha\beta=1$, $$AB(\alpha^2+\beta^2)=2AB+5$$ $$AB({\alpha-\beta})^2=5\tag{1}$$ Using initial conditions $$a_0=A+B$$ $$a_1=A\alpha+B\beta$$ Solving linear equations, $$A=\frac{a_1-a_0\beta}{\alpha-\beta}$$ $$B=\frac{a_0\alpha-a_1}{\alpha-\beta}$$ Applying to (1), $$(a_0\beta-a_1)(a_0\alpha-a_1)+5=0$$ $$a_0^2-a_0a_1(\alpha+\beta)+a_1^2+5=0$$ $$\therefore \alpha+\beta=\frac{a_0^2+a_1^2+5}{a_0a_1}$$ As $\alpha$ and $\beta$ are roots of $x^2-Sx-T$, $$S=\alpha+\beta=\frac{a_0^2+a_1^2+5}{a_0a_1}$$ $$T=-\alpha\beta=-1$$ (*) In our case, $a_0=2$ and $a_1=3$ gives us $\alpha+\beta=3$ that leads to lulu's solution.

Answer 4

The result is $a_{n + 1} = 3 a_n - a_{n - 1}$.

HINT: Let $a_{k + 1} = a_k + b_k$. Then, by the original equation, we get $$a_{n - 1} + b_{n - 1} + b_n = \frac {(a_{n - 1} + b_{n - 1})^2 + 5} {a_{n - 1}} = a_{n - 1} + 2 b_{n - 1} + \frac {b_{n - 1}^2 + 5} {a_{n - 1}}.$$ Hence, $$b_n = b_{n - 1} + \frac {b_{n - 1}^2 + 5} {a_{n - 1}}.$$

Answer 5

$7=3S+2T\\ 18=7S+3T$

is a linear system of two equations with two unknowns. It has a unique solution : by multiplying the first line by $3$ and the second by $2$, then substracting, you get $21-36 = 9S-14S$, so $-15 = -5S$, then $S=3$, and then $T=-1$.

Let $b_n$ be the sequence defined by $b_0=a_0, b_1=a_1, b_{n+2}=Sb_{n+1}+Tb_n$. You want to show that the recurrence relation defining $a_n$ is also valid for $b_n$, i.e. $b_nb_{n+2} - b_{n+1}^2 - 5 = 0$

Since $(b_n)$ satisfies a linear recurrent equation of order $2$, $(b_n^2)$ and $(b_nb_{n+2})$ satisfy a recurrent linear equation of order $3$ (if I'm not mistaken, $c_{n+3} = 8c_{n+2}-8c_{n+1}+c_n$)

The constant sequence $5$ also satisfies this recurrence relation, so the whole $(b_nb_{n+2} - b_{n+1}^2 - 5)$ is a linear recurrent sequence of order $3$ (it would be of order $4$ if it wasn't the case).

To show that it is the $0$ constant you only need to show that its first three terms are $0$. Since $a_0=b_0$ and $a_1=b_1$ by definition and $S$ and $T$ were chosen so that $a_2=b_2$ and $a_3=b_3$, then you only need to check that $a_4=b_4$.

since $a_4 = 47 = 3*18-7 = b_4$, this is true, and so $a_n = b_n$ forall $n$.

Answer 6

From the recurrence relation we have $$ a_{n+1} a_{n-1} - a_n^2 = 5 = a_{n+2} a_{n} - a_{n+1}^2. $$ So $$ a_{n+1} \, (a_{n-1} + a_{n+1}) = a_n \, (a_n + a_{n+2}). $$ or $$ \frac{a_{n-1} + a_{n+1}}{a_n} = \frac{a_n + a_{n+2}}{a_{n+1}}, $$ This means $$ c_n \equiv \frac{a_{n-1} + a_{n+1}}{a_n}. $$ satisfies $c_n = c_{n+1}$, and thus is a constant. Let $c_n = S$. By $a_0 = 2$, $a_1 = 3$, $a_2 = (a_1^2 +5)/a_0 = 7$, we determine $S = 3$. Thus, $$ a_{n+1} = 3 \, a_n - a_{n-1} = S \, a_n + T \, a_{n-1}, $$ where $S = 3$, $T = -1$.