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 "2019 AMC 10A Problems/Problem 15"

m (→‎Solution 2)
(→‎Solution 4 (Arithmetic Sequence))
 
(50 intermediate revisions by 22 users not shown)
Line 4: Line 4:
  
 
A sequence of numbers is defined recursively by <math>a_1 = 1</math>, <math>a_2 = \frac{3}{7}</math>, and
 
A sequence of numbers is defined recursively by <math>a_1 = 1</math>, <math>a_2 = \frac{3}{7}</math>, and
−
<cmath>a_n=\frac{a_{n-2} \cdot a_{n-1}}{2a_{n-2} - a_{n-1}}</cmath>for all <math>n \geq 3</math> Then <math>a_{2019}</math> can be written as <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive inegers. What is <math>p+q ?</math>
+
<cmath>a_n=\frac{a_{n-2} \cdot a_{n-1}}{2a_{n-2} - a_{n-1}}</cmath>for all <math>n \geq 3</math> Then <math>a_{2019}</math> can be written as <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. What is <math>p+q ?</math>
  
 
<math>\textbf{(A) } 2020 \qquad\textbf{(B) } 4039 \qquad\textbf{(C) } 6057 \qquad\textbf{(D) } 6061 \qquad\textbf{(E) } 8078</math>
 
<math>\textbf{(A) } 2020 \qquad\textbf{(B) } 4039 \qquad\textbf{(C) } 6057 \qquad\textbf{(D) } 6061 \qquad\textbf{(E) } 8078</math>
  
−
==Solution 1==
+
==Solution 1 (Induction)==
  
 
Using the recursive formula, we find <math>a_3=\frac{3}{11}</math>, <math>a_4=\frac{3}{15}</math>, and so on. It appears that <math>a_n=\frac{3}{4n-1}</math>, for all <math>n</math>. Setting <math>n=2019</math>, we find <math>a_{2019}=\frac{3}{8075}</math>, so the answer is <math>\boxed{\textbf{(E) }8078}</math>.
 
Using the recursive formula, we find <math>a_3=\frac{3}{11}</math>, <math>a_4=\frac{3}{15}</math>, and so on. It appears that <math>a_n=\frac{3}{4n-1}</math>, for all <math>n</math>. Setting <math>n=2019</math>, we find <math>a_{2019}=\frac{3}{8075}</math>, so the answer is <math>\boxed{\textbf{(E) }8078}</math>.
  
−
 
+
To prove this formula, we use induction. We are given that <math>a_1=1</math> and <math>a_2=\frac{3}{7}</math>, which satisfy our formula. Now assume the formula holds true for all <math>n\le m</math> for some positive integer <math>m</math>. By our assumption, <math>a_{m-1}=\frac{3}{4m-5}</math> and <math>a_m=\frac{3}{4m-1}</math>. Using the recursive formula, <cmath>a_{m+1}=\frac{a_{m-1}\cdot a_m}{2a_{m-1}-a_m}=\frac{\frac{3}{4m-5}\cdot\frac{3}{4m-1}}{2\cdot\frac{3}{4m-5}-\frac{3}{4m-1}}=\frac{\left(\frac{3}{4m-5}\cdot\frac{3}{4m-1}\right)(4m-5)(4m-1)}{\left(2\cdot\frac{3}{4m-5}-\frac{3}{4m-1}\right)(4m-5)(4m-1)}=\frac{9}{6(4m-1)-3(4m-5)}=\frac{3}{4(m+1)-1},</cmath>
−
To prove this formula, we use induction. We are given that <math>a_1=1</math> and <math>a_2=\frac{3}{7}</math>, which satisfy our formula. Now assume the formula holds true for all <math>n\le m</math> for some positive integer <math>m</math>. By our assumption, <math>a_{m-1}=\frac{3}{4m-5}</math> and <math>a_m=\frac{3}{4m-1}</math>. Using the recursive formula, <cmath>a_{m+1}=\frac{a_{m-1}\cdot a_m}{2a_{m-1}-a_m}=\frac{\frac{3}{4m-5}\cdot\frac{3}{4m-1}}{2\cdot\frac{3}{4m-5}-\frac{3}{4m-1}}=\frac{(\frac{3}{4m-5}\cdot\frac{3}{4m-1})(4m-5)(4m-1)}{(2\cdot\frac{3}{4m-5}-\frac{3}{4m-1})(4m-5)(4m-1)}=\frac{9}{6(4m-1)-3(4m-5)}=\frac{3}{4(m+1)-1},</cmath>
 
 
so our induction is complete.
 
so our induction is complete.
  
 
==Solution 2==
 
==Solution 2==
  
−
Since we are finding the sum of the numerator and the denominator, consider the function <math>b_n = \frac{1}{a_n}</math>.
+
We have <math>\frac{1}{a_n} = \frac{2a_{n-2}-a_{n-1}}{a_{n-2} \cdot a_{n-1}}=\frac{2}{a_{n-1}}-\frac{1}{a_{n-2}}</math>, in other words, <math>\frac{1}{a_n}-\frac{1}{a_{n-1}} = \frac{1}{a_{n-1}}-\frac{1}{a_{n-2}}</math>. So <math>\{\frac{1}{a_n}\}</math> is an arithmetic sequence with step size <math>\frac{7}{3}-1=\frac{4}{3}</math>, which means <math>\frac{1}{a_{2019}} = 1+2018 \cdot \frac{4}{3} = \frac{8075}{3}</math>. Since the numerator and the denominator are relatively prime, the answer is <math>\boxed{\textbf{(E) } 8078}</math>.
 +
 
 +
-eric2020 (modified by Dolphindesigner)
 +
 
 +
==Solution 3==
 +
 
 +
It seems reasonable to transform the equation into something else. Let <math>a_{n}=x</math>, <math>a_{n-1}=y</math>, and <math>a_{n-2}=z</math>. Therefore, we have <cmath>x=\frac{zy}{2z-y}</cmath>
 +
<cmath>2xz-xy=zy</cmath>
 +
<cmath>2xz=y(x+z)</cmath>
 +
<cmath>y=\frac{2xz}{x+z}</cmath>
 +
Thus, <math>y</math> is the harmonic mean of <math>x</math> and <math>z</math>. This implies <math>a_{n}</math> is a harmonic sequence or equivalently <math>b_{n}=\frac{1}{a_{n}}</math> is arithmetic. Now, we have <math>b_{1}=1</math>, <math>b_{2}=\frac{7}{3}</math>, <math>b_{3}=\frac{11}{3}</math>, and so on. Since the common difference is <math>\frac{4}{3}</math>, we can express <math>b_{n}</math> explicitly as <math>b_{n}=\frac{4}{3}(n-1)+1</math>. This gives <math>b_{2019}=\frac{4}{3}(2019-1)+1=\frac{8075}{3}</math> which implies <math>a_{2019}=\frac{3}{8075}=\frac{p}{q}</math>. <math>p+q=\boxed{\textbf{(E) } 8078}</math>
 +
~jakeg314
 +
 
 +
== Solution 4 (Arithmetic Sequence) ==
 +
 
 +
Notice that<cmath>a_n = \frac{1}{\frac{2}{a_{n-1}} - \frac{1}{a_{n-2}}}.</cmath>Therefore,<cmath>\frac{1}{a_n} = \frac{2}{a_{n-1}} - \frac{1}{a_{n-2}}, \ \ \implies \ \ \frac{\frac{1}{a_n} + \frac{1}{a_{n-2}}}{2} = \frac{1}{a_{n-1}}.</cmath>Therefore, the sequence <math>b_n = \frac{1}{a_n}</math> is an arithmetic sequence. Notice that the common difference of <math>b</math> is <math>\frac{4}{3},</math> and therefore<cmath>b_{2019} = b_1 + 2018 \bigg(\frac{4}{3}\bigg) = 1 + 2018 \bigg(\frac{4}{3} \bigg) = \frac{8075}{3}.</cmath>Therefore, we see that <math>a_{2019} = \frac{3}{8075},</math> so that <math>p + q = \boxed{\text{(E) } 8078}.</math>
 +
 
 +
~Professor-Mom
 +
 
 +
Note: This is similar to solutions #2 and #3, although you can notice that in #2's case the new sequence <math>B</math> actually forms an arithmetic sequence.
 +
 
 +
==Solution 5 (Characteristic Equation - Overkill but Generic) ==
 +
 
 +
We have <math>\frac{1}{a_n} = \frac{2a_{n-2}-a_{n-1}}{a_{n-2} \cdot a_{n-1}}=\frac{2}{a_{n-1}}-\frac{1}{a_{n-2}}</math>,
 +
 
 +
let <math>b_n = \frac{1}{a_n}</math> , then <math> b_n = 2b_{n-1} - b_{n-2}</math>
 +
 
 +
, this is 2nd order linear homogeneous recurrence sequence,  
 +
 
 +
the characteristic equation for this is <math>x^2 -2x +1 = 0</math>, which has double root x=1
 +
 
 +
so <math>b_n = (c_1 + c_2 \cdot n) \cdot 1^n </math>
 +
 
 +
plug in <math>b_1 = \frac{1}{a_1} = 1 = c_1 + c_2 \cdot 1, b_2 = \frac{1}{a_2}= \frac{7}{3} =c_1 + c_2 \cdot 2  </math>
 +
 
 +
we solve <math>c_1 = -\frac{1}{3} , c_2=\frac{4}{3}</math>, so <math>b_n = -\frac{1}{3} + \frac{4}{3} \cdot n </math>
 +
 
 +
so  <math> {b_{2019}} = -\frac{1}{3} + \frac{4}{3} \cdot 2019 = \frac{8075}{3}</math>.  
  
−
<math>\frac{1}{a_n} = \frac{2a_{n-2}-a_{n-1}}{a_{n-2} \cdot a_{n-1}}=frac{1}{a_{n-1}}+\frac{1}{a_{n-2}}</math>
+
<math>a_{2019} = \frac{1}{b_{2019}} = \frac{3}{8075}</math>  
  
−
<math>b_n = 2b_{n-1}-b_{n-2}=3b_{n-2}-2b{n-3}</math>
+
Since the numerator and the denominator are relatively prime, the answer is <math>\boxed{\textbf{(E) } 8078}</math>.
  
−
By recursively following this pattern, we can see that <math>b_n=(n-1) \cdot b_2 - (n-1) \cdot b_1</math>.
+
*note: characteristic equation is overkill for this simple one but is more generic solution for other parameter values.
  
−
By plugging in 2019, we get: <math>b_{2019} = 2018 \cdot \frac{7}{3}-2017 = \frac{8705}{3}</math>. Since they are relatively prime, the answer is <math>8708</math> which implies <math>\rightarrow \boxed{E}</math>
+
~[https://artofproblemsolving.com/wiki/index.php/User:Cyantist luckuso]
  
 
==See Also==
 
==See Also==

Latest revision as of 20:44, 8 October 2024

The following problem is from both the 2019 AMC 10A #15 and 2019 AMC 12A #9, so both problems redirect to this page.

Problem

A sequence of numbers is defined recursively by $a_1 = 1$, $a_2 = \frac{3}{7}$, and \[a_n=\frac{a_{n-2} \cdot a_{n-1}}{2a_{n-2} - a_{n-1}}\]for all $n \geq 3$ Then $a_{2019}$ can be written as $\frac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. What is $p+q ?$

$\textbf{(A) } 2020 \qquad\textbf{(B) } 4039 \qquad\textbf{(C) } 6057 \qquad\textbf{(D) } 6061 \qquad\textbf{(E) } 8078$

Solution 1 (Induction)

Using the recursive formula, we find $a_3=\frac{3}{11}$, $a_4=\frac{3}{15}$, and so on. It appears that $a_n=\frac{3}{4n-1}$, for all $n$. Setting $n=2019$, we find $a_{2019}=\frac{3}{8075}$, so the answer is $\boxed{\textbf{(E) }8078}$.

To prove this formula, we use induction. We are given that $a_1=1$ and $a_2=\frac{3}{7}$, which satisfy our formula. Now assume the formula holds true for all $n\le m$ for some positive integer $m$. By our assumption, $a_{m-1}=\frac{3}{4m-5}$ and $a_m=\frac{3}{4m-1}$. Using the recursive formula, \[a_{m+1}=\frac{a_{m-1}\cdot a_m}{2a_{m-1}-a_m}=\frac{\frac{3}{4m-5}\cdot\frac{3}{4m-1}}{2\cdot\frac{3}{4m-5}-\frac{3}{4m-1}}=\frac{\left(\frac{3}{4m-5}\cdot\frac{3}{4m-1}\right)(4m-5)(4m-1)}{\left(2\cdot\frac{3}{4m-5}-\frac{3}{4m-1}\right)(4m-5)(4m-1)}=\frac{9}{6(4m-1)-3(4m-5)}=\frac{3}{4(m+1)-1},\] so our induction is complete.

Solution 2

We have $\frac{1}{a_n} = \frac{2a_{n-2}-a_{n-1}}{a_{n-2} \cdot a_{n-1}}=\frac{2}{a_{n-1}}-\frac{1}{a_{n-2}}$, in other words, $\frac{1}{a_n}-\frac{1}{a_{n-1}} = \frac{1}{a_{n-1}}-\frac{1}{a_{n-2}}$. So $\{\frac{1}{a_n}\}$ is an arithmetic sequence with step size $\frac{7}{3}-1=\frac{4}{3}$, which means $\frac{1}{a_{2019}} = 1+2018 \cdot \frac{4}{3} = \frac{8075}{3}$. Since the numerator and the denominator are relatively prime, the answer is $\boxed{\textbf{(E) } 8078}$.

-eric2020 (modified by Dolphindesigner)

Solution 3

It seems reasonable to transform the equation into something else. Let $a_{n}=x$, $a_{n-1}=y$, and $a_{n-2}=z$. Therefore, we have \[x=\frac{zy}{2z-y}\] \[2xz-xy=zy\] \[2xz=y(x+z)\] \[y=\frac{2xz}{x+z}\] Thus, $y$ is the harmonic mean of $x$ and $z$. This implies $a_{n}$ is a harmonic sequence or equivalently $b_{n}=\frac{1}{a_{n}}$ is arithmetic. Now, we have $b_{1}=1$, $b_{2}=\frac{7}{3}$, $b_{3}=\frac{11}{3}$, and so on. Since the common difference is $\frac{4}{3}$, we can express $b_{n}$ explicitly as $b_{n}=\frac{4}{3}(n-1)+1$. This gives $b_{2019}=\frac{4}{3}(2019-1)+1=\frac{8075}{3}$ which implies $a_{2019}=\frac{3}{8075}=\frac{p}{q}$. $p+q=\boxed{\textbf{(E) } 8078}$ ~jakeg314

Solution 4 (Arithmetic Sequence)

Notice that\[a_n = \frac{1}{\frac{2}{a_{n-1}} - \frac{1}{a_{n-2}}}.\]Therefore,\[\frac{1}{a_n} = \frac{2}{a_{n-1}} - \frac{1}{a_{n-2}}, \ \ \implies \ \ \frac{\frac{1}{a_n} + \frac{1}{a_{n-2}}}{2} = \frac{1}{a_{n-1}}.\]Therefore, the sequence $b_n = \frac{1}{a_n}$ is an arithmetic sequence. Notice that the common difference of $b$ is $\frac{4}{3},$ and therefore\[b_{2019} = b_1 + 2018 \bigg(\frac{4}{3}\bigg) = 1 + 2018 \bigg(\frac{4}{3} \bigg) = \frac{8075}{3}.\]Therefore, we see that $a_{2019} = \frac{3}{8075},$ so that $p + q = \boxed{\text{(E) } 8078}.$

~Professor-Mom

Note: This is similar to solutions #2 and #3, although you can notice that in #2's case the new sequence $B$ actually forms an arithmetic sequence.

Solution 5 (Characteristic Equation - Overkill but Generic)

We have $\frac{1}{a_n} = \frac{2a_{n-2}-a_{n-1}}{a_{n-2} \cdot a_{n-1}}=\frac{2}{a_{n-1}}-\frac{1}{a_{n-2}}$,

let $b_n = \frac{1}{a_n}$ , then $b_n = 2b_{n-1} - b_{n-2}$

, this is 2nd order linear homogeneous recurrence sequence,

the characteristic equation for this is $x^2 -2x +1 = 0$, which has double root x=1

so $b_n = (c_1 + c_2 \cdot n) \cdot 1^n$

plug in $b_1 = \frac{1}{a_1} = 1 = c_1 + c_2 \cdot 1, b_2 = \frac{1}{a_2}= \frac{7}{3} =c_1 + c_2 \cdot 2$

we solve $c_1 = -\frac{1}{3} , c_2=\frac{4}{3}$, so $b_n = -\frac{1}{3} + \frac{4}{3} \cdot n$

so ${b_{2019}} = -\frac{1}{3} + \frac{4}{3} \cdot 2019 = \frac{8075}{3}$.

$a_{2019} = \frac{1}{b_{2019}} = \frac{3}{8075}$

Since the numerator and the denominator are relatively prime, the answer is $\boxed{\textbf{(E) } 8078}$.

  • note: characteristic equation is overkill for this simple one but is more generic solution for other parameter values.

~luckuso

See Also

2019 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Problem 16
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2019 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 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=2019_AMC_10A_Problems/Problem_15&oldid=229350"