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$
  • 2
    $\begingroup$ Please do not use misleading titles (I modified yours). $\endgroup$ – Did Aug 20 '17 at 23:22
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Or prove by induction that $a_n = 2^{n+2}-3$. $\endgroup$ – Robert Israel Aug 21 '17 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$
  • $\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 Aug 23 '17 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$ – Cye Waldman Aug 23 '17 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.