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 "Mock AIME 1 2006-2007 Problems/Problem 13"
m
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
13. Let <math>a_{n}</math>, <math>b_{n}</math>, and <math>c_{n}</math> be geometric sequences with different common ratios and let <math>a_{n}+b_{n}+c_{n}=d_{n}</math> for all integers <math>n</math>. If <math>d_{1}=1</math>, <math>d_{2}=2</math>, <math>d_{3}=3</math>, <math>d_{4}=-7</math>, <math>d_{5}=13</math>, and <math>d_{6}=-16</math>, find <math>d_{7}</math>.
+
==Problem==
 +
Let <math>a_{n}</math>, <math>b_{n}</math>, and <math>c_{n}</math> be geometric sequences with different common ratios and let <math>a_{n}+b_{n}+c_{n}=d_{n}</math> for all integers <math>n</math>. If <math>d_{1}=1</math>, <math>d_{2}=2</math>, <math>d_{3}=3</math>, <math>d_{4}=-7</math>, <math>d_{5}=13</math>, and <math>d_{6}=-16</math>, find <math>d_{7}</math>.
 +
==Solution==
  
−
[[Mock AIME 1 2006-2007]]
+
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 <math>P(x)=(x-\alpha)(x-\beta)(x-\gamma)</math> with <math>\alpha</math>, <math>\beta</math> and <math>\gamma</math> distinct.
 +
 
 +
Let <math>\alpha+\beta+\gamma=p</math>, <math>-(\alpha\beta+\alpha\gamma+\beta\gamma)=q</math>, and <math>\alpha\beta\gamma=r</math>. Then we can write <math>P(x)=x^3 - px^2 - qx - r</math>.
 +
 
 +
Now consider the recurrence <math>\forall n: d_n = pd_{n-1} + qd_{n-2} + rd_{n-3}</math>. (<math>P</math> is called the ''characteristic polynomial'' of this recurrence.)
 +
 
 +
We can easily verify that each of the three sequences <math>d_n=\alpha^n</math>, <math>d_n=\beta^n</math> and <math>d_n=\gamma^n</math> satisfies the recurrence. Moreover, we know the following facts:
 +
* If a sequence <math>(x_n)</math> satisfies the recurrence, then for all <math>s</math> the sequence <math>(sx_n)</math> does, too.
 +
* If sequences <math>(x_n)</math> and <math>(y_n)</math> satisfy the recurrence, then the sequence <math>(x_n+y_n)</math> does, too.
 +
Thus each linear combination of the three sequences we have satisfies the recurrence.
 +
In other words, each sequence of the form <math>d_n = s\alpha^n + t\beta^n + u\gamma^n</math> solves the recurrence. And vice versa, each solution of the recurrence can be written in this form, because given the values <math>d_0</math>, <math>d_1</math> and <math>d_2</math> one can always uniquely determine the coefficients <math>s,t,u</math>.
 +
 
 +
=== Solving the task ===
 +
 
 +
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>, <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:
 +
<cmath>
 +
\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*}
 +
</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}</math>.
 +
 
 +
----
 +
 
 +
*[[Mock AIME 1 2006-2007 Problems/Problem 12 | Previous Problem]]
 +
 
 +
*[[Mock AIME 1 2006-2007 Problems/Problem 14 | Next Problem]]
 +
 
 +
*[[Mock AIME 1 2006-2007]]

Latest revision as of 14:50, 3 April 2012

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}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_13&oldid=45989"