3

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)$.

Did
  • 279,727
dcxt
  • 614

2 Answers2

5

Hint: By induction, prove that $a_n = 2a_{n-1}+3$ and you will be done.

dezdichado
  • 13,888
1

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$.

Cye Waldman
  • 7,524
  • 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 00:27
  • 1
    @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: https://math.stackexchange.com/questions/2357418/solving-fibonacci-recurrence-relation/2358956?s=1|0.1460#2358956. 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 00:39