# If $a_0=1$, $a_1=5$, and $a_n=\frac{2a_{n-1}^2-3a_{n-1}-9}{2a_{n-2}}$, then every $a_n$ is an integer

Given that $a_0=1, a_1=5$, and $$a_n=\frac{2a_{n-1}^2-3a_{n-1}-9}{2a_{n-2}}$$ Show that all $a_n$ are integers.

Factoring the numerator gives $$a_n=\frac{(2a_{n-1}+3)(a_{n-1}-3)}{2a_{n-2}}$$ First we notice that the numerator must be divisible by $2$ to be an integer. Assume $a_{n-1}$ and $a_{n-2}$ are both odd (which is true for the base case $a_{n-2}=1$), then $a_n - 3$ must be divisible by $2$. If $a_n$ is even, then $a_{n-1}$ cannot be an integer. Therefore, we must prove that $a_n$ is not $3$ (mod $4$), which is easy to do with induction. From here, I don't know how to prove that $a_{n-2}|(2a_{n-1}+3)(a_{n-1}-3)$.

• Please do not use misleading titles (I modified yours). – Did Aug 20 '17 at 23:22

Hint: By induction, prove that $a_n = 2a_{n-1}+3$ and you will be done.
• Or prove by induction that $a_n = 2^{n+2}-3$. – Robert Israel Aug 21 '17 at 0:28
Although you have two correct solutions, the question you asked has not been answered. I'll rephrase it slightly as: how do you prove that $2a_{n-2}|(2a_{n-1}+3)(a_{n-1}-3)$ is an integer?
Start by assuming that $\frac{2a_{n-1}+3}{2a_{n-2}}=k$, an integer. That implies that $2a_{n-1}=2ka_{n-2}-3$. Compare this with the original sequence, which becomes $a_n=k(a_{n-1}-3)$, which is inconsistent for all $k$.
Now try assuming that $\frac{a_{n-1}-3}{2a_{n-2}}=k$, an integer. That implies that $a_{n-1}=2ka_{n-2}+3$. Compare this with the original sequence, which becomes $a_n=k(2a_{n-1}+3)$, which is consistent for $k=1$.
• This is helpful as a heuristic for "guessing" the simple recursion formula in this particular case, but the answer should emphasize that in general $\,2 a_{n-2} \mid a \cdot b\,$ does not imply $\,2 a_{n-2} \mid a \,\lor\, 2 a_{n-2} \mid b\,$. – dxiv Aug 23 '17 at 0:27
• @dxiv Yes, I appreciate your comments, but I was trying to help the OP see through their attempt. Once you've reduced the recursion to a form $f_n=Af_{n-1}+B$ you can get the Binet-type closed-form solution with the method I show here: math.stackexchange.com/questions/2357418/…. I also observe that you are not limited to $a_0=1,~a_1=5$, but rather only that $a_1=2a_0+3$. – Cye Waldman Aug 23 '17 at 0:39