2019 AMC 12B Problem 22

Define a sequence recursively by

x_0=5

and

x_{n+1}=\dfrac{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\le4+\dfrac{1}{2^{20}}.

In which of the following intervals does

m

lie?

Show solution

Solution

Let

a_n=x_n-4.

A short computation gives

\begin{gathered} a_{n+1}=x_{n+1}-4 \\ =\dfrac{(x_n+5)(x_n-4)}{x_n+6} \\ =a_n\cdot\dfrac{x_n+5}{x_n+6}. \end{gathered}

Starting from

a_0=1,

the terms stay positive and decrease. Because

x_n

decreases from

5

toward

4,

each ratio

\dfrac{x_n+5}{x_n+6}

lies strictly between

\dfrac{9}{10}

and

\dfrac{10}{11}.

Hence

a_m

is squeezed between

\left(\dfrac{9}{10}\right)^m

and

\left(\dfrac{10}{11}\right)^m.

Solving

a_m\le2^{-20}

puts

m

between about

132

and

146,

which lies in

[81,242].

Thus, C is the correct answer.

Tagged: recursion · telescoping · bounding to limit cases