HMMT November

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 $\{y_{n}\}$ 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.