AMC 10 Daily Practice - Sequences

Complete problem set with solutions and individual problem pages

Problem 3 Easy

Define a sequence recursively by x_0=5 andx_{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? (2019 AMC 10B Problems, Question #24)

  • A.

    [9,26]

  • B.

    [27,80]

  • C.

    [81,242]

  • D.

    [243,728]

  • E.

    [729,\infty)

Answer:C

The condition where x_m\leq 4+\frac{1}{2^{20}} gives the motivation to make a substitution to change the equilibrium from 4 to 0. We can substitute x_n = y_n + 4 to achieve that. Now, we need to find the smallest value of m such that y_m\leq \frac{1}{2^{20}} given that y_0 = 1.

 

Factoring the recursion x_{n+1} = \frac{x_n^2 + 5x_n+4}{x_n + 6}, we get:

 

x_{n+1}=\dfrac{(x_n + 4)(x_n + 1)}{x_n + 6} \Rightarrow y_{n+1}+4=\dfrac{(y_n+8)(y_n+5)}{y_n+10}

 

y_{n+1}+4=\dfrac{y_n^2+13y_n+40}{y_n+10} = \dfrac{y_n^2+9y_n +(4y_n+40)}{y_n+10}

 

y_{n+1}+4=\dfrac{y_n^2+9y_n}{y_n+10} + 4

 

y_{n+1}=\dfrac{y_n^2+9y_n}{y_n+10}.

 

Using wishful thinking, we can simplify the recursion as follows:

 

y_{n+1} = \frac{y_n^2 + 9y_n + y_n - y_n}{y_n + 10}

 

y_{n+1} = \frac{y_n(y_n + 10) - y_n}{y_n + 10}

 

y_{n+1} = y_n - \frac{y_n}{y_n + 10}

 

y_{n+1} = y_n\left(1 - \frac{1}{y_n + 10}\right).

 

The recursion looks like a geometric sequence with the ratio changing slightly after each term. Notice from the recursion that the y_n sequence is strictly decreasing, so all the terms after y_0 will be less than 1. Also, notice that all the terms in sequence will be positive. Both of these can be proven by induction.

 

With both of those observations in mind, \frac{9}{10} < 1 - \frac{1}{y_n + 10} \leq \frac{10}{11}. Combining this with the fact that the recursion resembles a geometric sequence, we conclude that \left(\frac{9}{10}\right)^n < y_n \leq \left(\frac{10}{11}\right)^n.

 

\frac{9}{10} is approximately equal to \frac{10}{11} and the ranges that the answer choices give us are generous, so we should use either \frac{9}{10} or \frac{10}{11} to find a rough estimate for m.

 

Since \dfrac{1}{2}=0.5, that means \frac{1}{\sqrt{2}}=2^{-\frac{1}{2}} \approx 0.7. Additionally, \left(\frac{9}{10}\right)^3=0.729

 

Therefore, we can estimate that 2^{-\frac{1}{2}} < y_3.

 

Raising both sides to the 40th power, we get 2^{-20} < (y_3)^{40}

 

But y_3 = (y_0)^3, so 2^{-20} < (y_0)^{120} and therefore, 2^{-20} < y_{120}.

 

This tells us that m is somewhere around 120, so our answer is \boxed{\textbf{(C) } [81,242]}.

Related Problems
Problem 1 AMC 10 Daily Practice - Sequences
Problem 2 AMC 10 Daily Practice - Sequences
Think Academy Powered by ChatGPT