Difference between revisions of "2007 AIME I Problems/Problem 14"

Revision as of 10:54, 16 April 2020

Problem

A sequence is defined over non-negative integral indexes in the following way: $a_{0}=a_{1}=3$ , $a_{n+1}a_{n-1}=a_{n}^{2}+2007$ .

Find the greatest integer that does not exceed $\frac{a_{2006}^{2}+a_{2007}^{2}}{a_{2006}a_{2007}}.$

Solution 1

We are given that

$a_{n+1}a_{n-1}= a_{n}^{2}+2007$ , $a_{n-1}^{2}+2007 = a_{n}a_{n-2}$ .

Add these two equations to get

$a_{n-1}(a_{n-1}+a_{n+1}) = a_{n}(a_{n}+a_{n-2})$

$\frac{a_{n+1}+a_{n-1}}{a_{n}}= \frac{a_{n}+a_{n-2}}{a_{n-1}}$ .

This is an invariant. Defining $b_{i}= \frac{a_{i}}{a_{i-1}}$ for each $i \ge 2$ , the above equation means

$b_{n+1}+\frac{1}{b_{n}}= b_{n}+\frac{1}{b_{n-1}}$ .

We can thus calculate that $b_{2007}+\frac{1}{b_{2006}}= b_{3}+\frac{1}{b_{2}}= 225$ . Using the equation $a_{2007}a_{2005}=a_{2006}^{2}+2007$ and dividing both sides by $a_{2006}a_{2005}$ , notice that $b_{2007}= \frac{a_{2007}}{a_{2006}}= \frac{a_{2006}^{2}+2007}{a_{2006}a_{2005}}> \frac{a_{2006}}{a_{2005}}= b_{2006}$ . This means that

$b_{2007}+\frac{1}{b_{2007}}< b_{2007}+\frac{1}{b_{2006}}= 225$ . It is only a tiny bit less because all the $b_i$ are greater than $1$ , so we conclude that the floor of $\frac{a_{2007}^{2}+a_{2006}^{2}}{a_{2007}a_{2006}}= b_{2007}+\frac{1}{b_{2007}}$ is $224$ .

Solution 2

The equation $a_{n+1}a_{n-1}-a_n^2=2007$ looks like the determinant $\left|\begin{array}{cc}a_{n+1}&a_n\\a_n&a_{n-1}\end{array}\right|=2007.$ Therefore, the determinant of this matrix is invariant. Guessing that this sequence might be a linear recursion because of the matrix form given below, we define the sequence $b_n$ defined by $b_1=b_2=3$ and $b_{n+1}=\alpha b_n+\beta b_{n-1}$ for $n\ge 2$ . We wish to find $\alpha$ and $\beta$ such that $a_n=b_n$ for all $n\ge 1$ . To do this, we use the following matrix form of a linear recurrence relation

$\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).$

When we take determinants, this equation becomes

$\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\text{det}\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).$

We want $\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=2007$ for all $n$ . Therefore, we replace the two matrices by $2007$ to find that

$2007=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\cdot 2007$ $1=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)=-\beta.$ Therefore, $\beta=-1$ . Computing that $a_3=672$ , and using the fact that $b_3=\alpha b_2-b_1$ , we conclude that $\alpha=225$ . Clearly, $a_1=b_1$ , $a_2=b_2$ , and $a_3=b_3$ . We claim that $a_n=b_n$ for all $n\ge 1$ . We proceed by induction. If $a_k=b_k$ for all $k\le n$ , then clearly, $b_nb_{n-2}-b_{n-1}^2=a_na_{n-2}-a_{n-1}^2=2007.$ We also know by the definition of $b_{n+1}$ that

$\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\text{det}\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).$

We know that the RHS is $2007$ by previous work. Therefore, $b_{n+1}b_{n-1}-b_n^2=2007$ . After substuting in the values we know, this becomes $b_{n+1}a_{n-1}-a_n^2=2007$ . Thinking of this as a linear equation in the variable $b_{n+1}$ , we already know that this has the solution $b_{n+1}=a_{n+1}$ . Therefore, by induction, $a_n=b_n$ for all $n\ge 1$ . We conclude that $a_n$ satisfies the linear recurrence $a_{n+1}=225a_n-a_{n-1}$ .

It's easy to prove that $a_n$ is a strictly increasing sequence of integers for $n\ge 3$ . Now

$\frac{a_{2007}^2+a_{2006}^2}{a_{2007}a_{2006}}=\frac{a_{2007}}{a_{2006}}+\frac{a_{2006}}{a_{2007}}=\frac{225a_{2006}-a_{2005}}{a_{2006}}+\frac{a_{2006}}{a_{2007}}.$

$=225+\frac{a_{2006}}{a_{2007}}-\frac{a_{2005}}{a_{2006}}=225+\frac{a_{2006}^2-a_{2005}a_{2007}}{a_{2005}a_{2006}}.$

$=225-\frac{2007}{a_{2005}a_{2006}}.$

The sequence certainly grows fast enough such that $\frac{2007}{a_{2005}a_{2006}}<1$ . Therefore, the largest integer less than or equal to this value is $224$ .

Solution 3 ( generalized )

This is a more elementary and rigorous solution to a slightly generalized version. The defining recursive sequence is generalized to

$a_{n+1}a_{n-1} = a_n^2 + 9k, ---------(1)$ where $k$ is a positive integer and $a_0 = a_1 = 3.$

Lemma 1 : For $n \geq 1$ , $a_{n+1} = ( k + 2)a_n - a_{n-1}. ---------(2)$ We shall prove by induction. From (1), $a_2 = 3k + 3$ . From the lemma, $a_2 = (k + 2) 3 - 3 = 3k + 3.$ Base case proven. Assume that the lemma is true for some $t \geq 1$ . Then, eliminating the $a_{t-1}$ using (1) and (2) gives

$(k+2)a_ta_{t+1} = a_t^2 + a_{t+1}^2 + 9k. ---------(3)$

It follows from (2) that

$(k+2)a_{t+1} - a_t =\frac{(k+2)a_{t+1}a_t - a_t^2}{a_t} =\frac{a_{t+1}^2 + 9k}{a_t} =a_{t+2},$

where the last line followed from (1) for case $n = t+1$ .

Lemma 2 : For $n \geq 0,$ $a_{n+1} \geq a_{n}.$ Base case is obvious. Assume that $a_{t+1} \geq a_{t}$ for some $t \geq 0$ . Then it follows that $a_{t+2} =\frac{a_{t+1}^2 + 9k}{a_t} = a_{t+1}(\frac{a_{t+1}}{a_t} ) + 9k \geq a_{t+1} + 9k > a_{t+1}.$

This completes the induction.

Lemma 3 : For $n \geq 1,$ $a_n a_{n+1} > 9k$

Using (1) and Lemma 2, for $n \geq 1,$ $a_{n+1}a_n \geq a_{n+1}a_{n-1} = a_n^2 + 9k > 9k$

Finally, using (3), for $n \geq 1,$ $\frac{a_n^2 + a_{n+1}^2}{a_n a_{n+1}} =\frac{(k+2)a_n a_{n+1} - 9k}{a_n a_{n+1}} = k+2 -\frac{9k}{a_n a_{n+1}}.$ Using lemma 3, the largest integer less than or equal to this value would be $k + 1$ .

Solution 4 (pure algebra)

We will try to manipulate $\frac{a_0^2+a_1^2}{a_0a_1}$ to get $\frac{a_1^2+a_2^2}{a_1a_2}$ .

$\frac{a_0^2+a_1^2}{a_0a_1} = \frac{a_0+\frac{a_1^2}{a_0}}{a_1} = \frac{a_0+\frac{a_1^2+2007}{a_0}-\frac{2007}{a_0}}{a_1}$ Using the recurrence relation, $= \frac{a_0+a_2-\frac{2007}{a_0}}{a_1} = \frac{a_0a_2+a_2^2-\frac{2007a_2}{a_0}}{a_1a_2}$ Applying the relation to $a_0a_2$ , $= \frac{a_1^2+2007+a_2^2-\frac{2007a_2}{a_0}}{a_1a_2} = \frac{a_1^2+a_2^2}{a_1a_2}+\frac{2007}{a_1a_2}-\frac{2007}{a_0a_1}$

We can keep on using this method to get that $\frac{a_0^2+a_1^2}{a_0a_1} = \frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}}+\frac{2007}{a_{2006}a_{2007}}-\frac{2007}{a_{2005}a_{2006}}+\frac{2007}{a_{2005}a_{2006}}-\ldots-\frac{2007}{a_{0}a_{1}}$

This telescopes to $\frac{a_0^2+a_1^2}{a_0a_1} = \frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}}+\frac{2007}{a_{2006}a_{2007}}-\frac{2007}{a_{0}a_{1}}$

or $\frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}} = \frac{a_0^2+a_1^2}{a_0a_1}+\frac{2007}{a_{0}a_{1}}-\frac{2007}{a_{2006}a_{2007}}$

Finding the first few values, we notice that they increase rapidly, so $\frac{2007}{a_{2006}a_{2007}} < 1$ . Calculating the other values, $\frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}} = 2+223-\frac{2007}{a_{2006}a_{2007}}$ .

The greatest number that does not exceed this is $224$

Solution 5 (using limits)

Let's start by computing the first couple terms of the given sequence so we know what we're working with. It's given that $a_0 = a_1 = 0$ , and solving for $a_2$ and $a_3$ using the given relation we get $a_2 = 672 = 3(224)$ and $a_3 = 3(224^{2} + 223)$ , respectively. It will be clear why I decided to factor these expressions as I did momentarily.

Next, let's see what the expression $\frac{a_{n}^{2}+a_{n + 1}^{2}}{a_{n}a_{n + 1}}$ looks like for small values of $n$ . For $n = 1$ , we get $\frac{1 + 224^2}{224}$ , the floor of which is clearly $224$ because the $1$ in the numerator is insignificant. Repeating the procedure for $n + 1$ is somewhat messier, but we end up getting $\frac{224^4 + 224^2\cdot223\cdot2 + 224^2 + 223^2}{224^3 + 224\cdot223}$ . It's not too hard to see that $224^4$ is much larger than the sum of the remaining terms in the numerator, and that $224^3$ is similarly a lot greater than the other term in the denominator. In fact, the second-largest term in the numerator is only barely larger than $224^3$ , while the second-largest term in the denominator is smaller than $224^2$ . Thus, the floor of this expression will come out to be $224$ as well.

Now we must consider whether this finding holds true for the rest of the sequence we're examining. First of all, notice that each time $n$ increases by $1$ , the degrees of both the numerator and denominator increase by $2$ , because we are squaring the $n+1th$ term in the numerator while the same term, appearing in the denominator, is being generated in part by squaring the term before it (seen in the relation $a_{n+1}^2 = (\frac{a_{n}^2 + 2007}{a_{n-1}})^2$ ). Thus, the degree of the numerator will always be one greater than the degree of the denominator; we have only to show that the other terms in the expression remain sufficiently small enough so as not to disturb the $\approx224:1$ ratio between the two.

For the non-greatest terms in the expression to offset this ratio for values of $n$ in the ballpark of $2006$ , they would have to have massive coefficients, because or else they are dwarfed by the additional $224$ attached to the leading term. Thankfully, this is not the case. Since we are simply squaring previous terms repeatedly to get new terms, we end up getting a sequence that is approximately equal to $\frac{224^k+224^{k-1}+224^{k-2} . . . }{224^{k-1}+224^{k-2} . . . }$ for all $k\geq2$ , an expression whose eventual limit is $\boxed{224}$ , which will be its floor when $n = 2006$ .

~anellipticcurveoverq

@@ Line 134: / Line 134: @@
 Let's start by computing the first couple terms of the given sequence so we know what we're working with. It's given that <math>a_0 = a_1 = 0</math>, and solving for <math>a_2</math> and <math>a_3</math> using the given relation we get <math>a_2 = 672 = 3(224)</math> and <math>a_3 = 3(224^{2} + 223)</math>, respectively. It will be clear why I decided to factor these expressions as I did momentarily.
-Next, let's see what the expression <math>\frac{a_{n}^{2}+a_{n + 1}^{2}}{a_{n}a_{n + 1}}</math> looks like for small values of <math>n</math>. For <math>n = 1</math>, we get <math>\frac{1 + 224^2}{224}</math>, the floor of which is clearly <math>224</math> because the <math>1</math> in the numerator is insignificant. Repeating the procedure for <math>n + 1</math> is somewhat messier, but we end up getting <math>\frac{224^4 + 224^2\cdot223\cdot2 + 224^2 + 223^2}{224^3 + 224\cdot223}</math>. It's not too hard to see that <math>224^4</math> is much larger than the sum of the remaining terms in the denominator, and that <math>224^3</math> is similarly a lot greater than the other term in the denominator. In fact, the second-largest term in the numerator is only barely larger than <math>224^3</math>, while the largest term in the denominator is smaller than <math>224^2</math>. Thus, the floor of this expression will come out to be <math>224</math> as well.
+Next, let's see what the expression <math>\frac{a_{n}^{2}+a_{n + 1}^{2}}{a_{n}a_{n + 1}}</math> looks like for small values of <math>n</math>. For <math>n = 1</math>, we get <math>\frac{1 + 224^2}{224}</math>, the floor of which is clearly <math>224</math> because the <math>1</math> in the numerator is insignificant. Repeating the procedure for <math>n + 1</math> is somewhat messier, but we end up getting <math>\frac{224^4 + 224^2\cdot223\cdot2 + 224^2 + 223^2}{224^3 + 224\cdot223}</math>. It's not too hard to see that <math>224^4</math> is much larger than the sum of the remaining terms in the numerator, and that <math>224^3</math> is similarly a lot greater than the other term in the denominator. In fact, the second-largest term in the numerator is only barely larger than <math>224^3</math>, while the second-largest term in the denominator is smaller than <math>224^2</math>. Thus, the floor of this expression will come out to be <math>224</math> as well.
 Now we must consider whether this finding holds true for the rest of the sequence we're examining. First of all, notice that each time <math>n</math> increases by <math>1</math>, the degrees of both the numerator and denominator increase by <math>2</math>, because we are squaring the <math>n+1th</math> term in the numerator while the same term, appearing in the denominator, is being generated in part by squaring the term before it (seen in the relation <math>a_{n+1}^2 = (\frac{a_{n}^2 + 2007}{a_{n-1}})^2</math>). Thus, the degree of the numerator will always be one greater than the degree of the denominator; we have only to show that the other terms in the expression remain sufficiently small enough so as not to disturb the <math>\approx224:1</math> ratio between the two.

2007 AIME I (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

Page

Toolbox

Search