HMMT-Nov 2017 guts, Problem 29

Consider a sequence $x_{n}$ such that $x_{1}=x_{2}=1, x_{3}=\frac{2}{3}$. Suppose that $x_{n}=\frac{x_{n-1}^{2} x_{n-2}}{2 x_{n-2}^{2}-x_{n-1} x_{n-3}}$ for all $n \geq 4$. Find the least $n$ such that $x_{n} \leq \frac{1}{10^{6}}$.

Solution: The recursion simplifies to $\frac{x_{n-1}}{x_{n}}+\frac{x_{n-3}}{x_{n-2}}=2 \frac{x_{n-2}}{x_{n-1}}$. So if we set $y_{n}=\frac{x_{n-1}}{x_{n}}$ for $n \geq 2$ then we have $y_{n}-y_{n-1}=y_{n-1}-y_{n-2}$ for $n \geq 3$, which means that $\left\{y_{n}\right\}$ is an arithmetic sequence. From the\\ starting values we have $y_{2}=1, y_{3}=\frac{3}{2}$, so $y_{n}=\frac{n}{2}$ for all $n$. (This means that $x_{n}=\frac{2^{n-1}}{n !}$.) Since $\frac{x_{1}}{x_{n}}=y_{2} y_{3} \cdots y_{n}$, it suffices to find the minimal $n$ such that the RHS is at least $10^{6}$. Note that $y_{2} y_{3} \cdots y_{12}=1 \cdot(1.5 \cdot 2 \cdot 2.5 \cdot 3 \cdot 3.5) \cdot(4 \cdot 4.5 \cdot 5 \cdot 5.5 \cdot 6)<2.5^{5} \cdot 5^{5}=12.5^{5}<200^{2} \cdot 12.5=500000<10^{6}$, while \[ y_{2} y_{3} \cdots y_{13}=1 \cdot(1.5 \cdot 2 \cdot 2.5 \cdot 3) \cdot(3.5 \cdot 4 \cdot 4.5) \cdot(5 \cdot 5.5 \cdot 6 \cdot 6.5)>20 \cdot 60 \cdot 900=1080000>10^{6} \] so the answer is 13 . $\fbox{13}$.

Answer: 13