Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 AIME II Problems/Problem 14"

(New page: == Problem == The sequence <math>(a_n)</math> satisfies <math>a_0=0</math> and <math>a_{n + 1} = \frac85a_n + \frac65\sqrt {4^n - a_n^2}</math> for <math>n\geq 0</math>. Find the greatest ...)
 
 
(5 intermediate revisions by 5 users not shown)
Line 4: Line 4:
 
== Solution ==
 
== Solution ==
  
−
=== The obvious substitution ===  
+
=== The "obvious" substitution ===  
  
 
An obvious way how to get the <math>4^n</math> from under the square root is to use the substitution <math>a_n = 2^n b_n</math>. Then the square root simplifies as follows:
 
An obvious way how to get the <math>4^n</math> from under the square root is to use the substitution <math>a_n = 2^n b_n</math>. Then the square root simplifies as follows:
Line 43: Line 43:
 
=== Solution 2 ===
 
=== Solution 2 ===
  
−
After we do the substitution, we can notice the fact that <math>\left( \frac 35 \right)^2 + \left( \frac 45 \right)^2 = 1</math>, which may suggest that the formula may have something to do with the unit circle. Also, the expression <math>\sqrt{1-x^2}</math> often appears in goniometry, for example in the relationship between the sine and the cosine. Both observations suggest that the formula may have a neat geometric interpretation.
+
After we do the substitution, we can notice the fact that <math>\left( \frac 35 \right)^2 + \left( \frac 45 \right)^2 = 1</math>, which may suggest that the formula may have something to do with the unit circle. Also, the expression <math>\sqrt{1-x^2}</math> often appears in trigonometry, for example in the relationship between the sine and the cosine. Both observations suggest that the formula may have a neat geometric interpretation.
  
 
Consider the equation:
 
Consider the equation:
Line 56: Line 56:
 
We have <math>b_0=0=\sin 0</math>. Therefore <math>b_1 = \sin(0+t) = \sin t</math>, <math>b_2 = \sin(t+t) = \sin (2t)</math>, and so on. (Remember that <math>t</math> is the constant defined as <math>t=\sin^{-1} \frac 35</math>.)
 
We have <math>b_0=0=\sin 0</math>. Therefore <math>b_1 = \sin(0+t) = \sin t</math>, <math>b_2 = \sin(t+t) = \sin (2t)</math>, and so on. (Remember that <math>t</math> is the constant defined as <math>t=\sin^{-1} \frac 35</math>.)
  
−
This process stops at the first <math>b_k = \sin (kt)</math>, where <math>kt</math> exceeds <math>\frac{\pi}2</math>. Then we'll have <math>b_{k+1} = \sin(kt - t) = \sin ((k-1)t) = \b_{k-1}</math> and the sequence will start to oscillate.
+
This process stops at the first <math>b_k = \sin (kt)</math>, where <math>kt</math> exceeds <math>\frac{\pi}2</math>. Then we'll have <math>b_{k+1} = \sin(kt - t) = \sin ((k-1)t) = b_{k-1}</math> and the sequence will start to oscillate.
  
 
Note that <math>\sin \frac{\pi}6 = \frac 12 < \frac 35</math>, and <math>\sin \frac{\pi}4 = \frac{\sqrt 2}2 > \frac 35</math>, hence <math>t</math> is strictly between <math>\frac{\pi}6</math> and <math>\frac{\pi}4</math>. Then <math>2t\in\left(\frac{\pi}3,\frac{\pi}2 \right)</math>, and <math>3t\in\left( \frac{\pi}2, \frac{3\pi}4 \right)</math>. Therefore surely <math>2t < \frac{\pi}2 < 3t</math>.  
 
Note that <math>\sin \frac{\pi}6 = \frac 12 < \frac 35</math>, and <math>\sin \frac{\pi}4 = \frac{\sqrt 2}2 > \frac 35</math>, hence <math>t</math> is strictly between <math>\frac{\pi}6</math> and <math>\frac{\pi}4</math>. Then <math>2t\in\left(\frac{\pi}3,\frac{\pi}2 \right)</math>, and <math>3t\in\left( \frac{\pi}2, \frac{3\pi}4 \right)</math>. Therefore surely <math>2t < \frac{\pi}2 < 3t</math>.  
  
−
Hence the process stops with <math>b_3 = \sin (3t)</math>, we then have <math>b_4 = \sin (2t) = b_2</math>. As in the previous solution, we conclude that <math>b_{10}=b_2</math>, and that the answer is <math>\lfloor a_{10} \rfloor & = \left\lfloor 2^{10} b_{10} \right\rfloor = \boxed{983}</math>.
+
Hence the process stops with <math>b_3 = \sin (3t)</math>, we then have <math>b_4 = \sin (2t) = b_2</math>. As in the previous solution, we conclude that <math>b_{10}=b_2</math>, and that the answer is <math>\lfloor a_{10} \rfloor = \left\lfloor 2^{10} b_{10} \right\rfloor = \boxed{983}</math>.
  
 +
==Video Solution 1 by SpreadTheMathLove==
 +
https://www.youtube.com/watch?v=z5uZ2PGmIUg
 
== See Also ==
 
== See Also ==
  
 
{{AIME box|year=2009|n=II|num-b=13|num-a=15}}
 
{{AIME box|year=2009|n=II|num-b=13|num-a=15}}
 +
{{MAA Notice}}

Latest revision as of 12:49, 23 December 2023

Problem

The sequence $(a_n)$ satisfies $a_0=0$ and $a_{n + 1} = \frac85a_n + \frac65\sqrt {4^n - a_n^2}$ for $n\geq 0$. Find the greatest integer less than or equal to $a_{10}$.

Solution

The "obvious" substitution

An obvious way how to get the $4^n$ from under the square root is to use the substitution $a_n = 2^n b_n$. Then the square root simplifies as follows: $\sqrt{4^n - a_n^2} = \sqrt{4^n - (2^n b_n)^2} = \sqrt{4^n - 4^n b_n^2} = 2^n \sqrt{1 - b_n^2}$.

The new recurrence then becomes $b_0=0$ and $b_{n+1} = \frac45 b_n + \frac 35\sqrt{1 - b_n^2}$.

Solution 1

We can now simply start to compute the values $b_i$ by hand:

\begin{align*} b_1 & = \frac 35 \\ b_2 & = \frac 45\cdot \frac 35 + \frac 35 \sqrt{1 - \left(\frac 35\right)^2} = \frac{24}{25} \\ b_3 & = \frac 45\cdot \frac {24}{25} + \frac 35 \sqrt{1 - \left(\frac {24}{25}\right)^2} = \frac{96}{125} + \frac 35\cdot\frac 7{25} = \frac{117}{125} \\ b_4 & = \frac 45\cdot \frac {117}{125} + \frac 35 \sqrt{1 - \left(\frac {117}{125}\right)^2} = \frac{468}{625} + \frac 35\cdot\frac {44}{125} = \frac{600}{625} = \frac{24}{25} \end{align*}

We now discovered that $b_4=b_2$. And as each $b_{i+1}$ is uniquely determined by $b_i$, the sequence becomes periodic. In other words, we have $b_3=b_5=b_7=\cdots=\frac{117}{125}$, and $b_2=b_4=\cdots=b_{10}=\cdots=\frac{24}{25}$.

Therefore the answer is

\begin{align*} \lfloor a_{10} \rfloor & = \left\lfloor 2^{10} b_{10} \right\rfloor = \left\lfloor \dfrac{1024\cdot 24}{25} \right\rfloor = \left\lfloor \dfrac{1025\cdot 24}{25} - \dfrac{24}{25} \right\rfloor \\ & = \left\lfloor 41\cdot 24 - \dfrac{24}{25} \right\rfloor = 41\cdot 24 - 1 = \boxed{983} \end{align*}

Solution 2

After we do the substitution, we can notice the fact that $\left( \frac 35 \right)^2 + \left( \frac 45 \right)^2 = 1$, which may suggest that the formula may have something to do with the unit circle. Also, the expression $\sqrt{1-x^2}$ often appears in trigonometry, for example in the relationship between the sine and the cosine. Both observations suggest that the formula may have a neat geometric interpretation.

Consider the equation: \[y = \frac45 x + \frac 35\sqrt{1 - x^2}\]

Note that for $t=\sin^{-1} \frac 35$ we have $\sin t=\frac 35$ and $\cos t = \frac 45$. Now suppose that we have $x=\sin s$ for some $s$. Then our equation becomes:

\[y=\cos t \cdot \sin s + \sin t \cdot |\cos s|\]

Depending on the sign of $\cos s$, this is either the angle addition, or the angle subtraction formula for sine. In other words, if $\cos s \geq 0$, then $y=\sin(s+t)$, otherwise $y=\sin(s-t)$.

We have $b_0=0=\sin 0$. Therefore $b_1 = \sin(0+t) = \sin t$, $b_2 = \sin(t+t) = \sin (2t)$, and so on. (Remember that $t$ is the constant defined as $t=\sin^{-1} \frac 35$.)

This process stops at the first $b_k = \sin (kt)$, where $kt$ exceeds $\frac{\pi}2$. Then we'll have $b_{k+1} = \sin(kt - t) = \sin ((k-1)t) = b_{k-1}$ and the sequence will start to oscillate.

Note that $\sin \frac{\pi}6 = \frac 12 < \frac 35$, and $\sin \frac{\pi}4 = \frac{\sqrt 2}2 > \frac 35$, hence $t$ is strictly between $\frac{\pi}6$ and $\frac{\pi}4$. Then $2t\in\left(\frac{\pi}3,\frac{\pi}2 \right)$, and $3t\in\left( \frac{\pi}2, \frac{3\pi}4 \right)$. Therefore surely $2t < \frac{\pi}2 < 3t$.

Hence the process stops with $b_3 = \sin (3t)$, we then have $b_4 = \sin (2t) = b_2$. As in the previous solution, we conclude that $b_{10}=b_2$, and that the answer is $\lfloor a_{10} \rfloor = \left\lfloor 2^{10} b_{10} \right\rfloor = \boxed{983}$.

Video Solution 1 by SpreadTheMathLove

https://www.youtube.com/watch?v=z5uZ2PGmIUg

See Also

2009 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_14&oldid=208245"