2019 AMC 10A Problem 15

P11-15~5 minPrint

Sequences & Series Algebraic Manipulation Compute small cases, spot the pattern, generalize Substitute to simplify (u = x+1/x, shifting, scaling)

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 ?$

Show solution without answering

Key insight

Flip every term upside down. The flipped terms go up by the same amount each time: 1, 7/3, 11/3, 15/3, and so on.

Solution

Step 1: compute a few terms to look for a pattern.

1. $a_3 = \dfrac{a_1 \cdot a_2}{2a_1 - a_2} = \dfrac{1 \cdot \frac37}{2 - \frac37} = \dfrac{\frac37}{\frac{11}{7}} = \dfrac{3}{11}$ .
2. $a_4 = \dfrac{a_2 \cdot a_3}{2a_2 - a_3} = \dfrac{\frac37 \cdot \frac3{11}}{\frac67 - \frac3{11}} = \dfrac{\frac{9}{77}}{\frac{45}{77}} = \dfrac{9}{45} = \dfrac{3}{15}$ .
3. Write $a_1 = \frac33$ . The terms so far are
$\frac33,\ \frac37,\ \frac3{11},\ \frac3{15},$
with bottoms $3, 7, 11, 15$ going up by $4$ each time.

Step 2: see why the pattern keeps going.

4. The rule has a product on top and a difference on the bottom, so flipping it upside down turns it into simpler pieces:
$\frac{1}{a_n} = \frac{2a_{n-2} - a_{n-1}}{a_{n-2}\, a_{n-1}} = \frac{2}{a_{n-1}} - \frac{1}{a_{n-2}}.$
5. Call the flipped terms $b_n = \frac1{a_n}$ . The line above says $b_n = 2b_{n-1} - b_{n-2}$ . Move things around: $b_n - b_{n-1} = b_{n-1} - b_{n-2}$ . So each flipped term is the previous one plus the same step every time.
6. The flipped terms start $b_1 = 1 = \frac33$ and $b_2 = \frac73$ , so the step is $\frac43$ . Then
$b_n = \frac{3 + 4(n-1)}{3} = \frac{4n - 1}{3}, \qquad a_n = \frac{3}{4n - 1}.$
(Check: $n = 3$ gives $\frac3{11}$ .)

Step 3: plug in $n = 2019$ .

$a_{2019} = \dfrac{3}{4 \cdot 2019 - 1} = \dfrac{3}{8075}$ .
Is it in lowest terms? $8075$ is not a multiple of $3$ (its digits add to $20$ ), so yes. So $p = 3$ and $q = 8075$ .
$p + q = 3 + 8075 = 8078$ .

The answer is $\boxed{\textbf{(E)}\ 8078}$ .

Why this works

When a rule has a product over a difference, flipping each term upside down usually makes it simpler. Here the flipped rule says the terms go up by equal steps, which is a pattern you can extend to any $n$ . Computing two or three terms by hand first shows you the pattern and gives a check on the formula.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The recursion has a product in the numerator and a difference in the denominator, which suggests taking reciprocals:
$\frac{1}{a_n} = \frac{2a_{n-2} - a_{n-1}}{a_{n-2}\,a_{n-1}} = \frac{2}{a_{n-1}} - \frac{1}{a_{n-2}}.$
Setting $b_n = 1/a_n$ gives $b_n = 2b_{n-1} - b_{n-2}$ , i.e. $b_n - b_{n-1} = b_{n-1} - b_{n-2}$ : the $b_n$ form an arithmetic sequence.

Its first two terms are $b_1 = 1$ and $b_2 = \tfrac73$ , so the common difference is $\tfrac43$ and
$b_n = 1 + \frac{4(n-1)}{3} = \frac{4n - 1}{3}.$
Then $b_{2019} = \frac{4 \cdot 2019 - 1}{3} = \frac{8075}{3}$ , so $a_{2019} = \frac{3}{8075}$ . Since $8075 = 3 \cdot 2691 + 2$ is not a multiple of $3$ , the fraction is reduced, and $p + q = 3 + 8075 = 8078$ .

The answer is $\boxed{\textbf{(E)}\ 8078}$ .

Review in the AoPS books

Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Introduction to Algebra, Chapter 11: Special Factorizations (§11.2, §11.3, §11.5)
Intermediate Algebra, Chapter 20: Some Advanced Strategies (§20.2)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)