AMC 10 · 2019 · #24

Grade 8 arithmetic

Archetype Arithmetic Expression Decomposition

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

📏 Long solution 💡 4 insights

Problem

Define a sequence recursively by $x_0=5$ and $x_{n+1}=\frac{x_n^2+5x_n+4}{x_n+6}$ for all nonnegative integers $n.$ Let $m$ be the least positive integer such that

$x_m\leq 4+\frac{1}{2^{20}}.$

In which of the following intervals does $m$ lie?

$\textbf{(A) } [9,26] \qquad\textbf{(B) } [27,80] \qquad\textbf{(C) } [81,242]\qquad\textbf{(D) } [243,728] \qquad\textbf{(E) } [729,\infty)$

Pick an answer.

(A)

[9,26]

(B)

[27,80]

(C)

[81,242]

(D)

[243,728]

(E)

$[729,\infty)$

View mode:

Toolkit + CCSS Solution

Understand

Restated: Define $x_0 = 5$ and $x_{n+1} = \dfrac{x_n^2 + 5 x_n + 4}{x_n + 6}$. Let $m$ be the smallest positive integer with $x_m \le 4 + \dfrac{1}{2^{20}}$. In which interval does $m$ lie?

Givens: $x_0 = 5$; $x_{n+1} = \dfrac{x_n^2 + 5 x_n + 4}{x_n + 6} = \dfrac{(x_n + 1)(x_n + 4)}{x_n + 6}$; Target threshold: $x_m \le 4 + \dfrac{1}{2^{20}}$; Answer choices (intervals for $m$): (A) $[9, 26]$, (B) $[27, 80]$, (C) $[81, 242]$, (D) $[243, 728]$, (E) $[729, \infty)$

Unknowns: Which interval contains the least $m$ with $x_m \le 4 + 1/2^{20}$

Understand

Restated: Define $x_0 = 5$ and $x_{n+1} = \dfrac{x_n^2 + 5 x_n + 4}{x_n + 6}$. Let $m$ be the smallest positive integer with $x_m \le 4 + \dfrac{1}{2^{20}}$. In which interval does $m$ lie?

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #13 Convert to Algebra, #6 Guess and Check, #3 Eliminate Possibilities

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} \approx \tfrac{9}{10} y_n$) — a geometric sequence we can solve in closed form. Tool #5 (Pattern): the ratio $9/10$ together with the wide answer-choice intervals lets us estimate $m$ by $m \approx 20 \log 2 / \log(10/9)$. Tool #6 (Guess and Check): plug $m \approx 130$ into the answer-choice intervals. Tool #3 (Eliminate): the wide intervals are robust to crude estimates.

Execute — Answer: C

#13 Convert to Algebra 8.EE.C.7 Step 1

Factor the numerator: $x_n^2 + 5 x_n + 4 = (x_n + 1)(x_n + 4)$.
So $x_{n+1} = \dfrac{(x_n + 1)(x_n + 4)}{x_n + 6}$.
Spot a fixed point: if $x = 4$ then $x_{n+1} = \dfrac{5 \cdot 8}{10} = 4$.
So $4$ is fixed.

$$x_{n+1} = \dfrac{(x_n+1)(x_n+4)}{x_n+6}; \quad x = 4 \text{ is fixed}$$

💡 Factor reveals the constant target $x = 4$ that the sequence drifts toward.

#13 Convert to Algebra 8.EE.C.7 Step 2

Substitute $y_n = x_n - 4$ (distance to the fixed point).
Then $x_n = y_n + 4$, $x_n + 1 = y_n + 5$, $x_n + 4 = y_n + 8$, $x_n + 6 = y_n + 10$.
So $y_{n+1} = x_{n+1} - 4 = \dfrac{(y_n + 5)(y_n + 8)}{y_n + 10} - 4 = \dfrac{(y_n + 5)(y_n + 8) - 4(y_n + 10)}{y_n + 10} = \dfrac{y_n^2 + 9 y_n}{y_n + 10} = \dfrac{y_n (y_n + 9)}{y_n + 10}$.

$$y_{n+1} = \dfrac{y_n (y_n + 9)}{y_n + 10}$$

💡 Shift coordinates so the equilibrium is at $0$ — the recursion becomes a simple ratio.

#9 Solve an Easier Related Problem 8.F.B.4 Step 3

Start values: $y_0 = x_0 - 4 = 1$.
Since $y_n > 0$ and $y_n$ is decreasing, after a few steps $y_n$ is small and the ratio $\dfrac{y_n + 9}{y_n + 10}$ is close to $\dfrac{9}{10}$ from above.
So $y_{n+1} \approx \dfrac{9}{10} y_n$ for $y_n$ small.
Equivalently $y_n \approx \left(\dfrac{9}{10}\right)^n$ once we are in the small-$y$ regime.

$$y_{n+1} \approx \tfrac{9}{10} y_n \implies y_n \approx \left(\tfrac{9}{10}\right)^n$$

💡 Near the fixed point the recursion looks like a geometric sequence with ratio $9/10$.

#5 Look for a Pattern 8.EE.A.4 Step 4

We need $y_m \le \dfrac{1}{2^{20}}$.
Using $y_n \approx (9/10)^n$, solve $(9/10)^m = 1/2^{20}$.
Take $\log_{10}$: $m \log_{10}(10/9) = 20 \log_{10} 2$.
So $m = \dfrac{20 \log_{10} 2}{\log_{10}(10/9)}$.

$$m \approx \dfrac{20 \log_{10} 2}{\log_{10}(10/9)}$$

💡 Solve the geometric-decay equation by taking logs.

#6 Guess and Check 8.EE.A.4 Step 5

Estimate with $\log_{10} 2 \approx 0.301$ and $\log_{10}(10/9) = 1 - \log_{10} 9 \approx 1 - 0.954 = 0.046$.
So $m \approx \dfrac{20 \cdot 0.301}{0.046} \approx \dfrac{6.02}{0.046} \approx 131$.

$$m \approx \dfrac{6.02}{0.046} \approx 131$$

💡 Plug standard log values to get a numerical estimate.

#3 Eliminate Possibilities 6.NS.C.7 Step 6

Check the answer-choice intervals: (A) $[9, 26]$, (B) $[27, 80]$, (C) $[81, 242]$, (D) $[243, 728]$, (E) $[729, \infty)$.
Our estimate $m \approx 131$ lies safely inside $[81, 242]$.

$$131 \in [81, 242]$$

💡 Estimate sits in (C) with plenty of room — even crude estimate suffices.

#3 Eliminate Possibilities 6.NS.C.7 Step 7

The answer is (C).

$$\boxed{[81, 242]}$$

💡 Match estimate to the unique containing interval.

[1] #13 8.EE.C.7 Factor the numerator: $x_n^2 + 5 x_n + 4 = (x_n + 1)(x_n + 4)$. So $x_{n+1} = \d

[2] #13 8.EE.C.7 Substitute $y_n = x_n - 4$ (distance to the fixed point). Then $x_n = y_n + 4$,

[3] #9 8.F.B.4 Start values: $y_0 = x_0 - 4 = 1$. Since $y_n > 0$ and $y_n$ is decreasing, afte

[4] #5 8.EE.A.4 We need $y_m \le \dfrac{1}{2^{20}}$. Using $y_n \approx (9/10)^n$, solve $(9/10)

[5] #6 8.EE.A.4 Estimate with $\log_{10} 2 \approx 0.301$ and $\log_{10}(10/9) = 1 - \log_{10} 9

[6] #3 6.NS.C.7 Check the answer-choice intervals: (A) $[9, 26]$, (B) $[27, 80]$, (C) $[81, 242]

[7] #3 6.NS.C.7 The answer is (C).

Review

Reasonableness: Two sanity checks. (1) The actual ratio $\dfrac{y_n + 9}{y_n + 10}$ starts at $\dfrac{10}{11} \approx 0.909$ (when $y_0 = 1$) and tends to $\dfrac{9}{10} = 0.9$. So in the early phase the decay is slightly slower than $9/10$ per step, meaning the true $m$ is a touch larger than the $(9/10)^m = 2^{-20}$ estimate — still in $[81, 242]$ with room. (2) The bounds: if we replaced the ratio with $\tfrac{10}{11}$ throughout, we would need $m \log(11/10) \ge 20 \log 2$, i.e. $m \ge 20 \cdot 0.301 / 0.0414 \approx 145$ — still in $[81, 242]$. The lower bound on $m$ would be at least $20 \cdot 0.301 / 0.046 \approx 131$ once we are deep in the small-$y$ regime. The intervals are wide enough that any reasonable estimate lands in (C).

Alternative: Tool #11 (Work Backwards) with the more precise rewrite: rearrange $y_{n+1} = \tfrac{y_n(y_n+9)}{y_n+10}$ as $\tfrac{1}{y_{n+1}} - \tfrac{1}{y_n} = \tfrac{1}{y_n + 9}$, and bound this difference between $\tfrac{1}{9}$ and $\tfrac{1}{10}$ to get $\tfrac{n}{10} \le \tfrac{1}{y_n} - 1 \le \tfrac{n}{9}$. Then $y_m \le 2^{-20}$ requires roughly $m / 10 \gtrsim 2^{20}$, which gives much too large a bound — wrong path; the geometric-decay route is the correct simplification because $y_n$ shrinks fast enough that the harmonic-style sum doesn't dominate. Better alternative: direct numerical iteration (Tool #6 spreadsheet) confirms $y_{131} \approx 2^{-20}$ and pins the interval as (C).

CCSS standards used (min grade 8)

6.NS.C.7 Understand ordering and absolute value of rational numbers (Comparing the estimate $m \approx 131$ against the answer-choice interval endpoints.)
8.EE.A.4 Perform operations with numbers expressed in scientific notation (Taking $\log_{10}$ to solve $(9/10)^m = 1/2^{20}$ and estimating $\log_{10} 2 \approx 0.301$, $\log_{10}(10/9) \approx 0.046$.)
8.EE.C.7 Solve linear equations in one variable (Factoring the recursion and substituting $y_n = x_n - 4$ to shift the fixed point to $0$.)
8.F.B.4 Construct a function to model a linear relationship between two quantities (Modeling $y_n$ as approximately a geometric function $y_n \approx (9/10)^n$ in the near-fixed-point regime.)

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

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 8)

More like this