Question

Set $u_0 = \dfrac{1}{4},$ and for $k \ge 0$ let $u_{k+1}$ be determined by the recurrence $u_{k+1} = 2u_k - 2u_k^2.$ This sequence tends to a limit; call it $L.$ What is the least value of $k$ such that $|u_k - L| \le \dfrac{1}{2^{1000}}?$

$10$

$87$

$123$

$329$

$401$

Answer: A

Concepts:recursion substitution

Difficulty rating: 2230

Solution:

The limit satisfies $L = 2L - 2L^2,$ giving $L = \tfrac12.$ Let $v_k = 1 - 2u_k.$ Then $\begin{aligned} v_{k+1} &= 1 - 2u_{k+1} \\ &= 1 - 4u_k + 4u_k^2 \\ &= (1 - 2u_k)^2 = v_k^2. \end{aligned}$

Since $v_0 = 1 - 2 \cdot \tfrac14 = \tfrac12,$ we get $v_k = \left(\tfrac12\right)^{2^k},$ so $|u_k - L| = \dfrac{|v_k|}{2} = 2^{-2^k - 1}.$

We need $2^k + 1 \ge 1000,$ i.e. $2^k \ge 999.$ The least such $k$ is $10,$ since $2^{10} = 1024.$

Thus, the correct answer is A.

2021 AMC 12B Fall Problem 18

Answer: A

Difficulty rating: 2230

Solution:

Problem 18 in Other Years