AMC 10 · 2019 · #24
Grade 8 arithmeticProblem
Define a sequence recursively by x0=5 and xn+1=xn+6xn2+5xn+4 for all nonnegative integers n. Let m be the least positive integer such that
xm≤4+2201.
In which of the following intervals does m lie?
Pick an answer.
AMC 10 2019 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
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?
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)$
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
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.
💡 Factor reveals the constant target $x = 4$ that the sequence drifts toward.
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}$.
💡 Shift coordinates so the equilibrium is at $0$ — the recursion becomes a simple ratio.
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.
💡 Near the fixed point the recursion looks like a geometric sequence with ratio $9/10$.
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)}$.
💡 Solve the geometric-decay equation by taking logs.
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$.
💡 Plug standard log values to get a numerical estimate.
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]$.
💡 Estimate sits in (C) with plenty of room — even crude estimate suffices.
6.NS.C.7 Step 7 The answer is (C).
💡 Match estimate to the unique containing interval.
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 8.EE.C.7 Substitute $y_n = x_n - 4$ (distance to the fixed point). Then $x_n = y_n + 4$, 8.F.B.4 Start values: $y_0 = x_0 - 4 = 1$. Since $y_n > 0$ and $y_n$ is decreasing, afte 8.EE.A.4 We need $y_m \le \dfrac{1}{2^{20}}$. Using $y_n \approx (9/10)^n$, solve $(9/10) 8.EE.A.4 Estimate with $\log_{10} 2 \approx 0.301$ and $\log_{10}(10/9) = 1 - \log_{10} 9 6.NS.C.7 Check the answer-choice intervals: (A) $[9, 26]$, (B) $[27, 80]$, (C) $[81, 242] 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.7Understand ordering and absolute value of rational numbers (Comparing the estimate $m \approx 131$ against the answer-choice interval endpoints.)8.EE.A.4Perform 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.7Solve 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.4Construct 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]$.
⭐ 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]$.
More like this
Same archetype — closest grade level first.