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
natmath
07.04.2021 19:35
Cross multiplying gives,
$$a_{n-1}a_{n+2}=a_{n+1}^2$$$$a_{n+2}=\frac{a_{n+1}^2}{a_{n-1}}$$$$a_n=\frac{a_{n-1}^2}{a_{n-3}}$$Since each term in the sequence is a product/quotient of previous terms, it is clear that each term will be rational. Moreover, each term $a_n$ can be expressed as $2^{b_n}5^{c_n}$, where $b_n,c_n$ are integers.
To prove that $a_n$ is always a positive integer, we must prove that $b_n,c_n$ are always nonnegative.
Note that $b_n$ satisfies the recurrence
$$b_n=2b_{n-1}-b_{n-3}$$With initial conditions $b_1=1$, $b_2=2$, $b_3=4$
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?
CircleGeometryGang
07.04.2021 21:43
natmath wrote:
Cross multiplying gives,
$$a_{n-1}a_{n+2}=a_{n+1}^2$$$$a_{n+2}=\frac{a_{n+1}^2}{a_{n-1}}$$$$a_n=\frac{a_{n-1}^2}{a_{n-3}}$$Since each term in the sequence is a product/quotient of previous terms, it is clear that each term will be rational. Moreover, each term $a_n$ can be expressed as $2^{b_n}5^{c_n}$, where $b_n,c_n$ are integers.
To prove that $a_n$ is always a positive integer, we must prove that $b_n,c_n$ are always nonnegative.
Note that $b_n$ satisfies the recurrence
$$b_n=2b_{n-1}-b_{n-3}$$With initial conditions $b_1=1$, $b_2=2$, $b_3=4$
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.