Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 13"

Revision as of 11:27, 30 January 2009

Problem

Let $a_{n}$ , $b_{n}$ , and $c_{n}$ be geometric sequences with different common ratios and let $a_{n}+b_{n}+c_{n}=d_{n}$ for all integers $n$ . If $d_{1}=1$ , $d_{2}=2$ , $d_{3}=3$ , $d_{4}=-7$ , $d_{5}=13$ , and $d_{6}=-16$ , find $d_{7}$ .

Solution

The problem tempts us to simply introduce six variables: the first term and the ratio for each of the three geometric sequences. The problem statement then gives us six independent (non-linear) equations in these variables, which does uniquely determine these variables - but there is no obvious way of computing them. We will show a different solution.

Insight

Consider the polynomial $P(x)=(x-\alpha)(x-\beta)(x-\gamma)$ with $\alpha$ , $\beta$ and $\gamma$ distinct.

Let $\alpha+\beta+\gamma=p$ , $-(\alpha\beta+\alpha\gamma+\beta\gamma)=q$ , and $\alpha\beta\gamma=r$ . Then we can write $P(x)=x^3 - px^2 - qx - r$ .

Now consider the recurrence $\forall n: d_n = pd_{n-1} + qd_{n-2} + rd_{n-3}$ . ( $P$ is called the characteristic polynomial of this recurrence.)

We can easily verify that each of the three sequences $d_n=\alpha^n$ , $d_n=\beta^n$ and $d_n=\gamma^n$ satisfies the recurrence. Moreover, we know the following facts:

If a sequence $(x_n)$ satisfies the recurrence, then for all $s$ the sequence $(sx_n)$ does, too.
If sequences $(x_n)$ and $(y_n)$ satisfy the recurrence, then the sequence $(x_n+y_n)$ does, too.

Thus each linear combination of the three sequences we have satisfies the recurrence. In other words, each sequence of the form $d_n = s\alpha^n + t\beta^n + u\gamma^n$ solves the recurrence. And vice versa, each solution of the recurrence can be written in this form, because given the values $d_0$ , $d_1$ and $d_2$ one can always uniquely determine the coefficients $s,t,u$ .

Solving the task

We just proved the following observation: If we have three geometric sequences with distinct ratios $\alpha$ , $\beta$ , and $\gamma$ , their sum always satisfies the recurrence $\forall n: d_n = pd_{n-1} + qd_{n-2} + rd_{n-3}$ for the $p,q,r$ defined above, and some $d_0,d_1,d_2$ determined by the initial values of these sequences.

In our situation, we do not need to know the ratios $\alpha$ , $\beta$ , and $\gamma$ . All we need to compute $d_7$ are the coefficients $p$ , $q$ , and $r$ .

But this is easy. We know that: $\begin{align*} d_4 &= pd_3 + qd_2 + rd_1 \\ d_5 &= pd_4 + qd_3 + rd_2 \\ d_6 &= pd_5 + qd_4 + rd_3 \end{align*}$

This is a set of three linear equations. In our case, it has a unique solution $(p,q,r)=(-2,-1,1)$ , hence $d_7 = -2d_6 - d_5 + d_4 = \boxed{012}$ .

Previous Problem

Next Problem

Mock AIME 1 2006-2007

@@ Line 23: / Line 23: @@
 We just proved the following observation: If we have three geometric sequences with distinct ratios <math>\alpha</math>, <math>\beta</math>, and <math>\gamma</math>, their sum always satisfies the recurrence <math>\forall n: d_n = pd_{n-1} + qd_{n-2} + rd_{n-3}</math> for the <math>p,q,r</math> defined above, and some <math>d_0,d_1,d_2</math> determined by the initial values of these sequences.
-In our situation, we do not need to know the ratios <math>\alpha</math>, \beta<math>, and </math>\gamma<math>. All we need to compute </math>d_7<math> are the coefficients </math>p<math>, </math>q<math>, and </math>r<math>.
+In our situation, we do not need to know the ratios <math>\alpha</math>, <math>\beta</math>, and <math>\gamma</math>. All we need to compute <math>d_7</math> are the coefficients <math>p</math>, <math>q</math>, and <math>r</math>.
 But this is easy. We know that:
@@ Line 34: / Line 34: @@
 </cmath>
-This is a set of three linear equations. In our case, it has a unique solution </math>(p,q,r)=(-2,-1,1)<math>, hence </math>d_7 = -2d_6 - d_5 + d_4 = \boxed{012}$.
+This is a set of three linear equations. In our case, it has a unique solution <math>(p,q,r)=(-2,-1,1)</math>, hence <math>d_7 = -2d_6 - d_5 + d_4 = \boxed{012}</math>.
 ----

Page

Toolbox

Search