# Given a series defined by recursion. Prove that there are integers $S$ and $T$ such that $a_{n+1} = S a_n + T a_{n-1}$

I have this problem from an old exam that I can't solve.

Let $$\{a_i\}_{i \geq 0}$$ be the series define by recursion as:

$$a_0 = 2$$

$$a_1 = 3$$

$$a_{n+1} = \frac{a_n^2 +5}{a_{n-1}}$$ , $$\forall n \in \Bbb N$$

Prove that there are integers $$S$$ and $$T$$ such that $$a_{n+1} = S a_n + T a_{n-1}$$

I've been trying with induction but I guess that there must be a direct, and more algebraic, way of proving it.

Any thoughts?? Thanks!

• First things first: have you run several terms of the sequence to see what the constants $S$ and $T$ must be? – Steven Stadnicki Dec 5 '16 at 20:29
• @Steven I've found that the constants are $S=5$ and $T=(-1)$ for $n \geq 2$. – jrs Dec 5 '16 at 20:38
• Once you have the correct constants there's a nice characterization in terms of a matrix; note that the recursion can also be written as $a_{n+1}a_{n-1}=a_n^2+5$ or as $a_{n+1}a_{n-1}-a_na_n=5$; that form should look a lot like the determinant of a certain matrix, and you should be able to find a linear transformation that takes one matrix of that form to the same matrix with all indices shifted by one, using the recurrence relation. – Steven Stadnicki Dec 5 '16 at 20:46
• Should S be 3 instead of 5? – displayname Dec 5 '16 at 20:58
• Gio, it certainly does not: The next few values are $a_2=\frac{3^2+5}{2}=7$, $a_3=\frac{7^2+5}{3}=18$, and $a_4=\frac{18^2+5}{7}=47$. It's not the case, for instance, that $a_4=5a_3-a_2$. – Steven Stadnicki Dec 5 '16 at 22:14

Define a series $a_{n+1} = \frac{a_n^2 +k}{a_{n-1}}$ with some $a_0, a_1$ for $n\ge2$. Assume there are $S$ and $T$ such that $a_{n+1} = S a_n + T a_{n-1}$.
$$a_{n+1} = \frac{a_n^2+k}{a_{n-1}} \\ S a_n + T a_{n-1} = \frac{a_n^2+k}{a_{n-1}} \\ S a_n a_{n-1} + T a_{n-1}^2 = a_n^2+k \tag{1}$$ now $$a_{n+1} = \frac{a_n^2+k}{a_{n-1}} \\ a_{n+1}a_{n-1} = a_n^2+k \\ a_{n+1}a_{n-1} - k = a_n^2 \tag{2}$$ combine the two: $$S a_n a_{n-1} + T(a_n a_{n-2} - k) = a_n^2+k \\ a_n(Sa_{n-1} + Ta_{n-2}) - Tk = a_n^2+k \\ a_n^2 - Tk = a_n^2+k \\ T = -1$$ now find $S$: $$a_{2} = \frac{a_1^2+k}{a_{0}} \\ S a_1 - a_{0} = \frac{a_1^2+k}{a_{0}} \\ S = \frac{a_0^2+a_1^2+k}{a_{0}a_{1}} \\$$ and in this case: $$S = \frac{2^2+3^2+5}{2\times3} = \frac{18}{6} = 3$$ So $S$ is an integer if it exists. Prove by induction that $$S a_n - a_{n-1} = \frac{a_n^2+k}{a_{n-1}}$$ (note that the base case $n=2$ is covered by how we set $S$). Assume the equality is correct for all $n+1\ge k\ge3$.
$$a_{n+2} = \frac{a_{n+1}^2+k}{a_{n}} \\ a_{n+2} = \frac{(S a_n-a_{n-1})^2+k}{a_{n}} = \frac{S^2 a_n^2-2S a_n a_{n-1}+a_{n-1}^2+k}{a_{n}} = S^2 a_n-2Sa_{n-1}+\frac{a_{n-1}^2+k}{a_{n}} \\ a_{n+2} = S(S a_n-a_{n-1})-Sa_{n-1}+\frac{a_{n-2}}{a_{n}}\frac{a_{n-1}^2+k}{a_{n-2}} = S a_{n+1} -Sa_n + \frac{a_{n-2}}{a_{n}} a_n \\ a_{n+2} = S a_{n+1} -Sa_n + a_{n-2} = S a_{n+1} -Sa_n + (S a_{n-1} - a_n) = S a_{n+1} - a_n$$ As required.