AMC 10 · 2019 · #24

Grade 8 arithmetic

Archetype Arithmetic Expression Decomposition └ Sub-archetype Fraction / Expression Sum Evaluation

recursive-sequencesequences-geometricexponentspolynomial-factoringestimation pattern-recognitionidentify-subproblems ↑ Prerequisites: recursive-sequencesequences-geometricexponents

📏 Long solution 💡 4 insights

Problem

Define x₀ = 5 and x_n+1 =

\frac{x_n² + 5 x_n + 4}{x_n + 6}

. Let m be the smallest positive integer with x_m ≤ 4 +

\frac{1}{2²⁰}

. In which interval does m lie?

Pick an answer.

(A)

[9,26]

(B)

[27,80]

(C)

[81,242]

(D)

[243,728]

(E)

$[729,\infty)$

AMC 10 2019 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

Tool #13 (Algebra): factor the numerator to expose the fixed point x = 4, then substitute y_n = x_n - 4 to move the equilibrium to 0. Tool #9 (Easier Problem): near y = 0 the recursion becomes nearly linear (y_n+1 ≈ $\frac{9}{10}$ y_n) — a geometric sequence we can solve in closed form. Tool #5 (Pattern): the ratio $\frac{9}{10}$ together with the wide answer-choice intervals lets us estimate m by m ≈ $\frac{20 log 2}{log(\frac{10}{9})}$ . Tool #6 (Guess and Check): plug m ≈ 130 into the answer-choice intervals. Tool #3 (Eliminate): the wide intervals are robust to crude estimates.

1STEP 1

Factor: x_n² + 5 x_n + 4 = (x_n + 1)(x_n + 4). Testing x = 4 gives $\frac{5 · 8}{10}$ = 4, so 4 is a fixed point.

x_n+1 =

\frac{(x_n+1)(x_n+4)}{x_n+6}

; x = 4 is fixed

2STEP 2

Substitute y_n = x_n - 4 (distance to the fixed point); the recursion collapses to y_n+1 = $\frac{y_n(y_n + 9)}{y_n + 10}$ , equilibrium now at 0.

y_n+1 =

\frac{y_n (y_n + 9)}{y_n + 10}

3STEP 3

With y₀ = 1 and y_n decreasing, the ratio $\frac{y_n + 9}{y_n + 10}$ tends to $\frac{9}{10}$ , so y_n ≈ ( $\frac{9}{10}$ )ⁿ once y is small.

y_n+1 ≈

\frac{9}{10}

y_n → y_n ≈ (

\frac{9}{10}

)ⁿ

4STEP 4

Need y_m ≤ $\frac{1}{2²⁰}$ , so solve ( $\frac{9}{10}$ )^m = $\frac{1}{2²⁰}$ ; taking logs gives m = $\frac{20 log 2}{log(\frac{10}{9})}$ .

m ≈

\frac{20 log₁0 2}{log₁0(\frac{10}{9})}

5STEP 5

Plug log 2 ≈ 0.301 and log( $\frac{10}{9}$ ) ≈ 0.046: m ≈ $\frac{20 · 0.301}{0.046}$ ≈ 131.

m ≈

\frac{6.02}{0.046}

≈ 131

6STEP 6

Among the answer intervals, m ≈ 131 lands cleanly inside [81, 242].

131 ∈ [81, 242]

7STEP 7

The answer is (C).

[81, 242]

Answer

[81,242]

Two sanity checks. (1) The actual ratio

\frac{y_n + 9}{y_n + 10}

starts at

\frac{10}{11}

≈ 0.909 (when y₀ = 1) and tends to

\frac{9}{10}

= 0.9. So in the early phase the decay is slightly slower than

\frac{9}{10}

per step, meaning the true m is a touch larger than the (

\frac{9}{10}

)^m = 2⁻²⁰ estimate — still in [81, 242] with room. (2) The bounds: if we replaced the ratio with

\frac{10}{11}

throughout, we would need m log(

\frac{11}{10}

) ≥ 20 log 2, i.e. m ≥

\frac{20 · 0.301}{0.0414}

≈ 145 — still in [81, 242]. The lower bound on m would be at least

\frac{20 · 0.301}{0.046}

≈ 131 once we are deep in the small-y regime. The intervals are wide enough that any reasonable estimate lands in (C).

💡Key takeaway

This AMC 10 problem only needs Grade 8 logs and geometric sequences — shift coordinates with y_n = x_n - 4 to expose the ratio $\frac{9}{10}$ , then ( $\frac{9}{10}$ )^m ≈ $\frac{1}{2²⁰}$ gives m ≈ 131, which lands in [81, 242].

More like this