Difference between revisions of "2021 Fall AMC 12B Problems/Problem 18"
(→Solution) |
|||
Line 8: | Line 8: | ||
==Solution== | ==Solution== | ||
+ | |||
+ | If we list out the first few values of k, we get the series <math>\frac{1}{4}, \frac{3}{8}, \frac{15}{32}, \frac{255}{512}</math>, which seem to always be a negative power of 2 away from <math>\frac{1}{2}</math>. We can test this out by setting <math>u_k</math> to <math>\frac{1}{2}-\frac{1}{2^{n_k}}</math>. | ||
+ | |||
+ | Now, | ||
+ | <cmath>\begin{align*} | ||
+ | u_{k+1} &= 2\cdot(\frac{1}{2}-\frac{1}{2^{n_k}})-2\cdot(\frac{1}{2}-\frac{1}{2^{n_k}})^2 \ | ||
+ | &= 1-\frac{1}{2^{n_k - 1}}-2\cdot(\frac{1}{4}-\frac{1}{2^{n_k}}+\frac{1}{2^{2 \cdot n_k}}) \ | ||
+ | &= 1-\frac{1}{2^{n_k - 1}}-\frac{1}{2}+\frac{1}{2^{n_k-1}}-\frac{1}{2^{2 \cdot n_k-1}} \ | ||
+ | &= \frac{1}{2}-\frac{1}{2^{2 \cdot n_k-1}} \ | ||
+ | \end{align*} | ||
+ | </cmath> | ||
+ | |||
+ | This means that <math>n_{k+1}=2 \cdot n_k-1</math>. | ||
+ | |||
+ | We see that <math>n_k</math> seems to always be <math>1</math> above a power of <math>2</math>. We can prove this using induction. | ||
+ | |||
+ | Claim: <math>n_k = 2^k+1</math> | ||
+ | |||
+ | Base case: <math>n_0=2^0+1</math> | ||
+ | |||
+ | Induction: <math>n_{k+1}=2*2^k+2-1=2^{k+1}+1</math> | ||
+ | |||
+ | It follows that <math>n_{10{=2^{10}+1>1000</math>, and <math>n_9=2^9+1<1000</math>. Therefore, the least value of <math>k</math> would be <math>\boxed{\textbf{(A) }10}</math>. |
Revision as of 17:19, 24 November 2021
Problem
Set , and for let be determined by the recurrence
This sequence tends to a limit; call it . What is the least value of such that
Solution
If we list out the first few values of k, we get the series , which seem to always be a negative power of 2 away from . We can test this out by setting to .
Now,
This means that .
We see that seems to always be above a power of . We can prove this using induction.
Claim:
Base case:
Induction:
It follows that $n_{10{=2^{10}+1>1000$ (Error compiling LaTeX. Unknown error_msg), and . Therefore, the least value of would be .