3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Please do not use misleading titles (I modified yours). $\endgroup$
    – Did
    Commented Aug 20, 2017 at 23:22

2 Answers 2

5
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Or prove by induction that $a_n = 2^{n+2}-3$. $\endgroup$ Commented Aug 21, 2017 at 0:28
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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\,$. $\endgroup$
    – dxiv
    Commented Aug 23, 2017 at 0:27
  • 1
    $\begingroup$ @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$. $\endgroup$ Commented Aug 23, 2017 at 0:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .