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 "2011 AIME II Problems/Problem 11"
m (wikify)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 +
Let <math>M_n</math> be the <math>n \times n</math> [[matrix]] with entries as follows: for <math>1 \le i \le n</math>, <math>m_{i,i} = 10</math>; for <math>1 \le i \le n - 1</math>, <math>m_{i+1,i} = m_{i,i+1} = 3</math>; all other entries in <math>M_n</math> are zero. Let <math>D_n</math> be the [[determinant]] of matrix <math>M_n</math>. Then <math>\sum_{n=1}^{\infty} \frac{1}{8D_n+1}</math> can be represented as <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are [[relatively prime]] positive integers. Find <math>p + q</math>.
  
−
Let <math>M_{n}</math> be the n x n matrix with entries as follows: for <math>1 \leq i \leq n</math>, <math>m_{i,i} = 10</math>; for <math>1 \leq i \leq n-1</math>, <math>m_{i,i+1} = m_{i+1,i} = 3</math>; all other entries in <math>M_{n}</math> are zero. Let <math>D_{n}</math> be the determinant of the matrix <math>M_{n}</math>. Then <math>\sum_{n = 1}^{\infty}\frac{1}{8D_{n} + 1}</math> can be represented as <math>\frac{p}{q}</math> where p and q are relatively prime positive integers. Find p + q.
+
Note: The determinant of the <math>1 \times 1</math> matrix <math>[a]</math> is <math>a</math>, and the determinant of the <math>2 \times 2</math> matrix <math>\left[ {\begin{array}{cc}
−
 
 
−
Note: The determinant of the 1 x 1 matrix <math>D_{1}=\left[ {\begin{array}{c}
 
−
a  \\
 
−
\end{array} } \right]</math> is a, and the determinant of the 2 x 2 matrix <math>\left[ {\begin{array}{cc}
 
 
  a & b  \\
 
  a & b  \\
 
  c & d  \\
 
  c & d  \\
−
  \end{array} } \right]</math> is ad-bc; for n <math>\geq</math> 2, the determinant of an n x n matrix with first row or first column <math>a_{1}</math> <math>a_{2}</math> <math>a_{3}</math> . . . . <math>a_{n}</math> is equal to
+
  \end{array} } \right] = ad - bc</math>; for <math>n \ge 2</math>, the determinant of an <math>n \times n</math> matrix with first row or first column <math>a_1</math> <math>a_2</math> <math>a_3</math> <math>\dots</math> <math>a_n</math> is equal to <math>a_1C_1 - a_2C_2 + a_3C_3 - \dots + (-1)^{n+1}a_nC_n</math>, where <math>C_i</math> is the determinant of the <math>(n - 1) \times (n - 1)</math> matrix formed by eliminating the row and column containing <math>a_i</math>.
−
<math>a_{1}C_{1}-a_{2}C_{2}+a_{3}C_{3}- . . . + (-1)^{n+1}a_{n}C_{n}</math> where <math>C_{i}</math> is the determinant of the (n-1) x (n-1) matrix found by eliminating the row and column containing <math>a_{i}</math>.
 
−
 
 
  
 
==Solution==
 
==Solution==
−
 
+
<cmath>D_{1}=\left| {\begin{array}{c}
−
<math>D_{1}=\left| {\begin{array}{c}
 
 
  10  \\
 
  10  \\
−
  \end{array} } \right| = 10</math>
+
  \end{array} } \right| = 10, \quad
−
 
+
D_{2}=\left| {\begin{array}{cc}
−
 
 
−
<math>D_{2}=\left| {\begin{array}{cc}
 
 
  10 & 3  \\
 
  10 & 3  \\
 
  3 & 10  \\
 
  3 & 10  \\
−
  \end{array} } \right|=(10)(10) - (3)(3) = 91</math>
+
  \end{array} } \right|=(10)(10) - (3)(3) = 91, \quad
−
 
+
D_{3}=\left| {\begin{array}{ccc}
−
 
 
−
<math>D_{3}=\left| {\begin{array}{ccc}
 
 
  10 & 3 & 0  \\
 
  10 & 3 & 0  \\
 
  3 & 10 & 3  \\
 
  3 & 10 & 3  \\
 
  0 & 3 & 10  \\
 
  0 & 3 & 10  \\
−
  \end{array} } \right|</math>
+
  \end{array} } \right|</cmath>
−
 
 
 
Using the expansionary/recursive definition of determinants (also stated in the problem):
 
Using the expansionary/recursive definition of determinants (also stated in the problem):
  
Line 47: Line 36:
 
  0 & 3  \\
 
  0 & 3  \\
 
  \end{array} } \right| = 10D_{2} - 9D_{1} = 820</math>
 
  \end{array} } \right| = 10D_{2} - 9D_{1} = 820</math>
−
 
  
 
This pattern repeats because the first element in the first row of <math>M_{n}</math> is always 10, the second element is always 3, and the rest are always 0. The ten element directly expands to <math>10D_{n-1}</math>. The three element expands to 3 times the determinant of the the matrix formed from omitting the second column and first row from the original matrix. Call this matrix <math>X_{n}</math>. <math>X_{n}</math> has a first column entirely of zeros except for the first element, which is a three. A property of matrices is that the determinant can be expanded over the rows instead of the columns (still using the recursive definition as given in the problem), and the determinant found will still be the same. Thus, expanding over this first column yields <math>3D_{n-2} + 0(other things)=3D_{n-2}</math>. Thus, the <math>3 det(X_{n})</math> expression turns into <math>9D_{n-2}</math>. Thus, the equation <math>D_{n}=10D_{n-1}-9D_{n-2}</math> holds for all n > 2.
 
This pattern repeats because the first element in the first row of <math>M_{n}</math> is always 10, the second element is always 3, and the rest are always 0. The ten element directly expands to <math>10D_{n-1}</math>. The three element expands to 3 times the determinant of the the matrix formed from omitting the second column and first row from the original matrix. Call this matrix <math>X_{n}</math>. <math>X_{n}</math> has a first column entirely of zeros except for the first element, which is a three. A property of matrices is that the determinant can be expanded over the rows instead of the columns (still using the recursive definition as given in the problem), and the determinant found will still be the same. Thus, expanding over this first column yields <math>3D_{n-2} + 0(other things)=3D_{n-2}</math>. Thus, the <math>3 det(X_{n})</math> expression turns into <math>9D_{n-2}</math>. Thus, the equation <math>D_{n}=10D_{n-1}-9D_{n-2}</math> holds for all n > 2.
−
 
  
 
This equation can be rewritten as <math>D_{n}=10(D_{n-1}-D_{n-2}) + D_{n-2}</math>. This version of the equation involves the difference of successive terms of a recursive sequence. Calculating <math>D_{0}</math> backwards from the recursive formula and <math>D_{4}</math> from the formula yields <math>D_{0}=1, D_{4}=7381</math>. Examining the differences between successive terms, a pattern emerges.  
 
This equation can be rewritten as <math>D_{n}=10(D_{n-1}-D_{n-2}) + D_{n-2}</math>. This version of the equation involves the difference of successive terms of a recursive sequence. Calculating <math>D_{0}</math> backwards from the recursive formula and <math>D_{4}</math> from the formula yields <math>D_{0}=1, D_{4}=7381</math>. Examining the differences between successive terms, a pattern emerges.  
−
<math>D_{0}=1=9^{0}</math>
+
<math>D_{0}=1=9^{0}</math>, <math>D_{1}-D_{0}=10-1=9=9^{1}</math>, <math>D_{2}-D_{1}=91-10=81=9^{2}</math>, <math>D_{3}-D_{2}=820-91=729=9^{3}</math>, <math>D_{4}-D_{3}=7381-820=6561=9^{4}</math>.
 +
Thus, <math>D_{n}=D_{0} + 9^{1}+9^{2}+ . . . +9^{n}=\sum_{i=0}^{n}9^{i}=\frac{(1)(9^{n+1}-1)}{9-1}=\frac{9^{n+1}-1}{8}</math>.
  
−
<math>D_{1}-D_{0}=10-1=9=9^{1}</math>
+
Thus, the desired sum is <math>\sum_{n=1}^{\infty}\frac{1}{8\frac{9^{n+1}-1}{8}+1}=\sum_{n=1}^{\infty}\frac{1}{9^{n+1}-1+1} = \sum_{n=1}^{\infty}\frac{1}{9^{n+1}} </math>
  
−
<math>D_{2}-D_{1}=91-10=81=9^{2}</math>
+
This is an infinite [[geometric series]] with first term <math>\frac{1}{81}</math> and common ratio <math>\frac{1}{9}</math>. Thus, the sum is <math>\frac{\frac{1}{81}}{1-\frac{1}{9}}=\frac{\frac{1}{81}}{\frac{8}{9}}=\frac{9}{(81)(8)}=\frac{1}{(9)(8)}=\frac{1}{72}</math>.
  
−
<math>D_{3}-D_{2}=820-91=729=9^{3}</math>
+
Thus, <math>p + q = 1 + 72 = \boxed{073}</math>
−
 
 
−
<math>D_{4}-D_{3}=7381-820=6561=9^{4}</math>
 
−
 
 
−
Thus, <math>D_{n}=D_{0} + 9^{1}+9^{2}+ . . . +9^{n}=\sum_{i=0}^{n}9^{i}=\frac{(1)(9^{n+1}-1)}{9-1}=\frac{9^{n+1}-1}{8}</math>.
 
−
 
 
−
Thus, the desired sum is <math>\sum_{n=1}^{\infty}\frac{1}{8\frac{9^{n+1}-1}{8}+1}=\sum_{n=1}^{\infty}\frac{1}{9^{n+1}-1+1} = \sum_{n=1}^{\infty}\frac{1}{9^{n+1}} </math>
 
  
−
This is an infinite geometric sequence with first term <math>\frac{1}{81}</math> and common ratio <math>\frac{1}{9}</math>. Thus, the sum is <math>\frac{\frac{1}{81}}{1-\frac{1}{9}}=\frac{\frac{1}{81}}{\frac{8}{9}}=\frac{9}{(81)(8)}=\frac{1}{(9)(8)}=\frac{1}{72}</math>.
+
==See also==
 +
{{AIME box|year=2011|n=II|num-b=12|num-a=14}}
  
−
Thus, p + q = 1 + 72 = <math>\framebox[1.4\width]{073.}</math>
+
[[Category:Intermediate Algebra Problems]]

Revision as of 21:27, 22 August 2011

Problem

Let $M_n$ be the $n \times n$ matrix with entries as follows: for $1 \le i \le n$, $m_{i,i} = 10$; for $1 \le i \le n - 1$, $m_{i+1,i} = m_{i,i+1} = 3$; all other entries in $M_n$ are zero. Let $D_n$ be the determinant of matrix $M_n$. Then $\sum_{n=1}^{\infty} \frac{1}{8D_n+1}$ can be represented as $\frac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. Find $p + q$.

Note: The determinant of the $1 \times 1$ matrix $[a]$ is $a$, and the determinant of the $2 \times 2$ matrix $\left[ {\begin{array}{cc} a & b \\ c & d \\ \end{array} } \right] = ad - bc$; for $n \ge 2$, the determinant of an $n \times n$ matrix with first row or first column $a_1$ $a_2$ $a_3$ $\dots$ $a_n$ is equal to $a_1C_1 - a_2C_2 + a_3C_3 - \dots + (-1)^{n+1}a_nC_n$, where $C_i$ is the determinant of the $(n - 1) \times (n - 1)$ matrix formed by eliminating the row and column containing $a_i$.

Solution

\[D_{1}=\left| {\begin{array}{c} 10 \\ \end{array} } \right| = 10, \quad D_{2}=\left| {\begin{array}{cc} 10 & 3 \\ 3 & 10 \\ \end{array} } \right|=(10)(10) - (3)(3) = 91, \quad D_{3}=\left| {\begin{array}{ccc} 10 & 3 & 0 \\ 3 & 10 & 3 \\ 0 & 3 & 10 \\ \end{array} } \right|\] Using the expansionary/recursive definition of determinants (also stated in the problem):

$D_{3}=\left| {\begin{array}{ccc} 10 & 3 & 0 \\ 3 & 10 & 3 \\ 0 & 3 & 10 \\ \end{array} } \right|=10\left| {\begin{array}{cc} 10 & 3 \\ 3 & 10 \\ \end{array} } \right| - 3\left| {\begin{array}{cc} 3 & 3 \\ 0 & 10 \\ \end{array} } \right| + 0\left| {\begin{array}{cc} 3 & 10 \\ 0 & 3 \\ \end{array} } \right| = 10D_{2} - 9D_{1} = 820$

This pattern repeats because the first element in the first row of $M_{n}$ is always 10, the second element is always 3, and the rest are always 0. The ten element directly expands to $10D_{n-1}$. The three element expands to 3 times the determinant of the the matrix formed from omitting the second column and first row from the original matrix. Call this matrix $X_{n}$. $X_{n}$ has a first column entirely of zeros except for the first element, which is a three. A property of matrices is that the determinant can be expanded over the rows instead of the columns (still using the recursive definition as given in the problem), and the determinant found will still be the same. Thus, expanding over this first column yields $3D_{n-2} + 0(other things)=3D_{n-2}$. Thus, the $3 det(X_{n})$ expression turns into $9D_{n-2}$. Thus, the equation $D_{n}=10D_{n-1}-9D_{n-2}$ holds for all n > 2.

This equation can be rewritten as $D_{n}=10(D_{n-1}-D_{n-2}) + D_{n-2}$. This version of the equation involves the difference of successive terms of a recursive sequence. Calculating $D_{0}$ backwards from the recursive formula and $D_{4}$ from the formula yields $D_{0}=1, D_{4}=7381$. Examining the differences between successive terms, a pattern emerges. $D_{0}=1=9^{0}$, $D_{1}-D_{0}=10-1=9=9^{1}$, $D_{2}-D_{1}=91-10=81=9^{2}$, $D_{3}-D_{2}=820-91=729=9^{3}$, $D_{4}-D_{3}=7381-820=6561=9^{4}$. Thus, $D_{n}=D_{0} + 9^{1}+9^{2}+ . . . +9^{n}=\sum_{i=0}^{n}9^{i}=\frac{(1)(9^{n+1}-1)}{9-1}=\frac{9^{n+1}-1}{8}$.

Thus, the desired sum is $\sum_{n=1}^{\infty}\frac{1}{8\frac{9^{n+1}-1}{8}+1}=\sum_{n=1}^{\infty}\frac{1}{9^{n+1}-1+1} = \sum_{n=1}^{\infty}\frac{1}{9^{n+1}}$

This is an infinite geometric series with first term $\frac{1}{81}$ and common ratio $\frac{1}{9}$. Thus, the sum is $\frac{\frac{1}{81}}{1-\frac{1}{9}}=\frac{\frac{1}{81}}{\frac{8}{9}}=\frac{9}{(81)(8)}=\frac{1}{(9)(8)}=\frac{1}{72}$.

Thus, $p + q = 1 + 72 = \boxed{073}$

See also

2011 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_11&oldid=41864"