The sequence $(a_n)$ is given by $a_1=2$, $a_2=500$, $a_3=2000$ and $$\frac{a_{n+2}+a_{n+1}}{a_{n+1}+a_{n-1}}=\frac{a_{n+1}}{a_{n-1}}\qquad\text{for }n\ge2$$Prove that all terms of this sequence are positive integers and that $a_{2000}$ is divisible by $2^{2000}$.
Problem
Source:
Tags: number theory
07.04.2021 19:35
I know I can prove that both $b_n$ and $c_n$ are nonnegative by finding the explicit relation, but I'd rather not since that seems relatively bashy (it's not too bad since the roots of the characteristic equation are somewhat nice). Is there a bounding or induction way to prove it?
07.04.2021 21:43
natmath wrote:
I know I can prove that both $b_n$ and $c_n$ are nonnegative by finding the explicit relation, but I'd rather not since that seems relatively bashy (it's not too bad since the roots of the characteristic equation are somewhat nice). Is there a bounding or induction way to prove it? You can prove that all terms are integers an easier way by doing the following: Assume a_n is divisible by both a_(n-1) and a_(n-2) By a_(n+1)=(a_n)^2/(a_(n-2)), a_n divides a_(n+1) By a_(n+2)=(a_(n+1))^2/(a_(n-1)), or a_(n+2)=(a_(n+1))((a_n)/(a_(n-1)))((a_n)/(a_(n-2))), therefore a_(n+1) divides a_(n+2), and therefore a_n divides a_(n+2). Therefore a_(n+2) is divisible by both a_(n+1) and a_n (1), and both a_(n+1) and a_(n+2) are divisible by a_n (2) Because of (1), the steps used can be recursively reused to do the same steps for all terms in the sequence. Because of (2), a_(n+1) and a_(n+2) are both integers. Since a_1 and a_2 both divide a_3, the above statements can be used to easily prove that all terms in the sequence are integers.