1999 Bulgaria National Olympiad #2

Let $\{a_n\}$ be a sequence of integers satisfying $(n-1)a_{n+1}=(n+1)a_n-2(n-1) \forall n\ge 1$. If $2000|a_{1999}$, find the smallest $n\ge 2$ such that $2000|a_n$.

The answer is $\boxed{249}$. 

Define $a_n=b_n+2(n-1) $ . Using the given condition we have $$n(b_{n+1}-b_{n})=b_n+b_{n+1} \implies$$ $$\frac{b_{n+1}}{b_n}=\frac{n+1}{n-1}.$$Plugging in $n=2,3,.....,n$ and multiplying the terms results in a telescoping product from which we obtain $$b_n = \frac{n(n-1)}{2} \cdot b_2.$$ Hence, we plug into our original expression for $a_n$ to get $$a_n = \frac{n(n-1)}{2}b_2+2(n-1).$$It is given that $a_{2009} \equiv 0 \pmod{2000}$, so we know that $b_2 \equiv 4 \pmod{2000}$. Now, $b_2 \pmod{2000}$ combined with our above expression for $a_n$ gives us that the least possible $n$ such that $2000|a_n$ is $249$, as desired. $\square$



Popular posts from this blog

1995 IMO #2

2014 IMO SL #C2

2015 IMO SL #A1