2019 AMC 10B Problem 24

The target $4 + \frac{1}{2^{20}}$ is "just above $4$", so follow the distance of each term from $4$.

Step 1: a simpler sequence.

1. Let $y_n = x_n - 4$, the amount by which $x_n$ is above $4$. Then $y_0 = 5 - 4 = 1$.
2. Compute the next distance:
$$y_{n+1} = x_{n+1} - 4 = \frac{x_n^2 + 5x_n + 4 - 4(x_n + 6)}{x_n + 6} = \frac{x_n^2 + x_n - 20}{x_n + 6} = \frac{(x_n - 4)(x_n + 5)}{x_n + 6}.$$
3. Now write $x_n + 5 = y_n + 9$ and $x_n + 6 = y_n + 10$:
$$y_{n+1} = y_n \cdot \frac{y_n + 9}{y_n + 10}.$$
So each step multiplies the distance by the factor $\frac{y_n + 9}{y_n + 10}$.

Step 2: how big is that factor?

4. Write the factor as $1 - \frac{1}{y_n + 10}$. The distance starts at $1$ and, as we will see, stays between $0$ and $1$.
5. If $y_n$ is between $0$ and $1$, then $y_n + 10$ is between $10$ and $11$, so the factor is between $1 - \frac1{10} = \frac{9}{10}$ and $1 - \frac1{11} = \frac{10}{11}$.
6. A positive factor smaller than $1$ keeps the distance positive and makes it shrink, so it does stay between $0$ and $1$.
7. Multiplying $n$ such factors starting from $y_0 = 1$:
$$\left(\frac{9}{10}\right)^n \le y_n \le \left(\frac{10}{11}\right)^n.$$

Step 3: we need $y_m \le \frac{1}{2^{20}}$, the first time.

1. $m$ is more than $120$. $9^6 = 531{,}441$ and $10^6 = 1{,}000{,}000$, so $\left(\frac{9}{10}\right)^6$ is more than $\frac12$. Raising to the $20$th power, $\left(\frac{9}{10}\right)^{120}$ is more than $\frac{1}{2^{20}}$. So for every $n$ up to $120$, $y_n$ is still above the target.
2. $m$ is at most $160$. $1.1^2 = 1.21$, $1.1^4 = 1.4641$, $1.1^8 \approx 2.14$, which is more than $2$. So $\left(\frac{10}{11}\right)^8$ is less than $\frac12$, and $\left(\frac{10}{11}\right)^{160}$ is less than $\frac{1}{2^{20}}$. So $y_{160}$ is already below the target.
3. Together: $m$ is between $121$ and $160$. That lies inside $[81, 242]$.

The answer is $\boxed{\textbf{(C)}\ [81,242]}$.

When a sequence creeps toward a number, study the gap between them instead of the terms. Factoring showed that the gap is multiplied by almost the same fraction each step, so it shrinks like a power. Rough power estimates were enough because the answer intervals are wide: each one is about three times the one before.