2019 AMC 10B Problem 24

Question

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?

[9,26]

[27,80]

[81,242]

[243,728]

[729,\infty)

Shift the sequence by writing

a_n=x_n-4

Bound the ratio

\frac{a_{n+1}}{a_n}

between

\frac{9}{10}

and

\frac{10}{11}

Let

a_n=x_n-4

. Then

a_0=1

, and simplifying the recurrence gives

a_{n+1}=\frac{a_n(a_n+9)}{a_n+10}.

As long as

0<a_n\le1

, this implies

\frac9{10}a_n\le a_{n+1}\le\frac{10}{11}a_n.

By induction,

\left(\dfrac9{10}\right)^n\le a_n\le\left(\dfrac{10}{11}\right)^n

. For

n=80

,

\left(\dfrac{10}{9}\right)^{80}<2^{20}

, so

\left(\dfrac9{10}\right)^{80}>2^{-20}

, and therefore

m>80

.

Also

\left(\dfrac{11}{10}\right)^8>2

, so

\left(\dfrac{10}{11}\right)^{160}<2^{-20}

, which gives

m\le160

. Hence

81\le m\le160

, so

m

lies in

[81,242]

. Thus, C is the correct answer.

Problem 24 in other years