2009 AIME II Problem 14

Attempt Problem 14 of the 2009 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2009 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

14.

The sequence (an)(a_n) satisfies a0=0a_0 = 0 and an+1=85an+654nan2a_{n+1} = \frac{8}{5}a_n + \frac{6}{5}\sqrt{4^n - a_n^2} for n0.n \ge 0. Find the greatest integer less than or equal to a10.a_{10}.

Answer: 983
Concepts:recursiontrigonometric identitysubstitution
Difficulty rating: 3160
Small Hint:

Try an=2nsinθn:a_n = 2^n \sin\theta_n: then 4nan2=2ncosθn\sqrt{4^n - a_n^2} = 2^n\,|\cos\theta_n| and the recursion is angle addition with θ=arcsin35\theta = \arcsin\frac{3}{5}

Big Hint:

Since 30<θ<45,30^\circ \lt \theta \lt 45^\circ, the angle climbs to 3θ,3\theta, whose cosine is negative, and then oscillates between 2θ2\theta and 3θ3\theta

Solution:

Write an=2nsinθna_n = 2^n \sin\theta_n with θ0=0,\theta_0 = 0, so 4nan2=2ncosθn.\sqrt{4^n - a_n^2} = 2^n\,|\cos\theta_n|. Let θ=arcsin35,\theta = \arcsin\frac{3}{5}, so cosθ=45.\cos\theta = \frac{4}{5}. The recursion becomes an+1=2n+1(cosθsinθn+sinθcosθn)=2n+1sin(θn±θ), \begin{aligned} &a_{n+1} \\ &= 2^{n+1} \\ &\quad {}\cdot \left(\cos\theta \sin\theta_n + \sin\theta\,|\cos\theta_n|\right) \\ &= 2^{n+1}\sin(\theta_n \pm \theta), \end{aligned} with the plus sign when cosθn0\cos\theta_n \ge 0 and the minus sign when cosθn<0.\cos\theta_n \lt 0.

Since 12<35<22,\frac{1}{2} \lt \frac{3}{5} \lt \frac{\sqrt{2}}{2}, we have 30<θ<45.30^\circ \lt \theta \lt 45^\circ. The angles θ,\theta, 2θ2\theta have positive cosine, so the sequence of angles runs 0,0, θ,\theta, 2θ,2\theta, 3θ.3\theta. But 90<3θ<13590^\circ \lt 3\theta \lt 135^\circ has negative cosine, so θ4=2θ,\theta_4 = 2\theta, and from then on the angle alternates between 3θ3\theta and 2θ.2\theta. In particular θn=2θ\theta_n = 2\theta for every even n2.n \ge 2.

With sin2θ=23545=2425,\sin 2\theta = 2 \cdot \frac{3}{5} \cdot \frac{4}{5} = \frac{24}{25}, a10=210sin2θ=10242425=2457625=983.04, \begin{aligned} a_{10} &= 2^{10} \sin 2\theta \\ &= 1024 \cdot \frac{24}{25} \\ &= \frac{24576}{25} = 983.04, \end{aligned} so the answer is 983.983.

Problem 13#13
Full Exam

Problem 14 in Other Years