Skip to main content

2021 Fall AMC 12B Problem 18

Problem 18 of 25IntermediateAlgebra

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

Answer choices

Show solution

Solution

The limit satisfies L=2L−2L2,L = 2L - 2L^2, giving L=12.L = \tfrac12. Let vk=1−2uk.v_k = 1 - 2u_k. Then vk+1=1−2uk+1=1−4uk+4uk2=(1−2uk)2=vk2. \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 v0=1−2⋅14=12,v_0 = 1 - 2 \cdot \tfrac14 = \tfrac12, we get vk=(12)2k,v_k = \left(\tfrac12\right)^{2^k}, so ∣uk−L∣=∣vk∣2=2−2k−1.|u_k - L| = \dfrac{|v_k|}{2} = 2^{-2^k - 1}. We need 2k+1≥1000,2^k + 1 \ge 1000, i.e. 2k≥999.2^k \ge 999. The least such kk is 10,10, since 210=1024.2^{10} = 1024. Thus, the correct answer is A.

More practice

Concepts: recursion · substitution

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.