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 "1993 AIME Problems/Problem 5"
(→‎Solution 3 (Overkill))
 
(13 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Let <math>P_0(x) = x^3 + 313x^2 - 77x - 8\,</math>.  For [[integer]]s <math>n \ge 1\,</math>, define <math>P_n(x) = P_{n - 1}(x - n)\,</math>.  What is the [[coefficient]] of <math>x\,</math> in <math>P_{20}(x)\,</math>?
+
<!-- don't remove the following tag, for PoTW on the Wiki front page--><onlyinclude>Let <math>P_0(x) = x^3 + 313x^2 - 77x - 8\,</math>.  For [[integer]]s <math>n \ge 1\,</math>, define <math>P_n(x) = P_{n - 1}(x - n)\,</math>.  What is the [[coefficient]] of <math>x\,</math> in <math>P_{20}(x)\,</math>?<!-- don't remove the following tag, for PoTW on the Wiki front page--></onlyinclude>
  
−
== Solution ==
+
== Solution 1 ==
 
Notice that  
 
Notice that  
 
<cmath>\begin{align*}P_{20}(x) &= P_{19}(x - 20)\\ &= P_{18}((x - 20) - 19)\\ &= P_{17}(((x - 20) - 19) - 18)\\ &= \cdots\\ &= P_0(x - (20 + 19 + 18 + \ldots + 2 + 1)).\end{align*}</cmath>
 
<cmath>\begin{align*}P_{20}(x) &= P_{19}(x - 20)\\ &= P_{18}((x - 20) - 19)\\ &= P_{17}(((x - 20) - 19) - 18)\\ &= \cdots\\ &= P_0(x - (20 + 19 + 18 + \ldots + 2 + 1)).\end{align*}</cmath>
Line 14: Line 14:
 
*<math>-77(x-210)</math> will have a linear term of <math>-77x</math>.  
 
*<math>-77(x-210)</math> will have a linear term of <math>-77x</math>.  
 
Adding up the coefficients, we get <math>630 \cdot 210 - 626 \cdot 210 - 77 = \boxed{763}</math>.
 
Adding up the coefficients, we get <math>630 \cdot 210 - 626 \cdot 210 - 77 = \boxed{763}</math>.
 +
 +
== Solution 2 ==
 +
Notice the transformation of <math>P_{n-1}(x)\to P_n(x)</math> adds <math>n</math> to the roots. Thus, all these transformations will take the roots and add <math>1+2+\cdots+20=210</math> to them. (Indeed, this is very easy to check in general.)
 +
 +
Let the roots be <math>r_1,r_2,r_3.</math> Then <math>P_{20}(x)=(x-r_1-210)(x-r_2-210)(x-r_3-210).</math> By Vieta's/expanding/common sense, you see the coefficient of <math>x</math> is <math>(r_1+210)(r_2+210)+(r_2+210)(r_3+210)+(r_3+210)(r_1+210).</math> Expanding yields <math>r_1r_2+r_2r_3+r_3r_1+210\cdot 2(r_1+r_2+r_3)+3\cdot 210^2.</math> Using Vieta's (again) and plugging stuff in yields <math>-77+210\cdot 2\cdot -313+3\cdot 210^2=\boxed{763}.</math>
 +
 +
== Solution 3 (Overkill) ==
 +
Denote the coefficient of term <math>x^m</math> of polynomial <math>P_n(x)</math> as <math>c_{m, n}</math>. We can see that <math>c_{2, 0} = 313</math>, <math>c_{1, 0} = -77</math>, and <math>c_{0, 0} = -8</math>. Note that <math>(x-n)^3 = x^3-3nx^2+3n^2x-n^3</math> and <math>(x-n)^2 = x^2-2nx+n^2</math>
 +
When substituting <math>x-1</math> for <math>x</math> in <math>P_0(x)</math>, we get that <math>P_1(x) = P_0(x-1) = (x^3-3x^2+3x-1) + 313(x^2-2x+1) -77(x-1) -8</math>. Observe that
 +
<cmath>c_{2,1} = c_{2,0} - 3(1) = 313 - 3 = 310</cmath>
 +
It is evident that
 +
<cmath>c_{2,n} = c_{2,n-1} - 3n</cmath>
 +
Define the generating function <math>C_2(X)</math> as
 +
<cmath>C_2(X) := \sum_{n \geq 0} c_{2,n}X^n</cmath>
 +
By multiplying both sides of the previous recurrence relation and taking the sum of the terms <math>\forall n\geq 1</math>, we get that
 +
<cmath>\implies \sum_{n\geq1} c_{2,n}X^n = \sum_{n\geq1}c_{2,n-1}X^n + 3\sum_{n\geq1}nX^n</cmath>
 +
<cmath>\implies \sum_{n\geq0} c_{2,n}X^n - c_{2,0} = X\sum_{n\geq0}c_{2,n}X^n + 3\sum_{n\geq1}nX^n</cmath>
 +
<cmath>\implies C_2(X) - 313 = XC_2(X) + 3\cdot \frac{X}{(1-X)^2}^*</cmath>
 +
<cmath>\implies C_2(X) = \frac{313}{1-X} - \frac{3X}{(1-X)^3}</cmath>
 +
<cmath>= \frac{313X^2 - 629X + 313}{(1-X)^3} = (313X^2 - 629X + 313) \cdot \sum_{n\geq0}{n+2 \choose 2}X^n\ ^\dagger</cmath>
 +
<cmath>\implies c_{2,n} = 313{n+2 \choose 2} - 629{n+1 \choose 2} + 313{n \choose 2}^\ddagger = \frac{-3n^2 - 3n + 626}{2}</cmath>
 +
We can perform a similar analysis on <math>c_{1,n}</math> to get the recurrence relation
 +
<cmath>c_{1,n} = c_{1, n-1} + c_{2,n-1}\cdot(-2n) + 3n^2</cmath>
 +
<cmath>= c_{1, n-1} +3n^3 - 626n</cmath>
 +
Define the generating function <math>C_1(X)</math> as
 +
<cmath>C_1(X) := \sum_{n\geq0}c_{1,n}X^n</cmath>
 +
We can then perform this process again on our new recurrence relation:
 +
<cmath>\implies \sum_{n\geq1} c_{1,n}X^n = \sum_{n\geq1}c_{1,n-1}X^n + 3\sum_{n\geq1}n^3X^n - 626\sum_{n\geq1}nX^n</cmath>
 +
<cmath>\implies \sum_{n\geq0} c_{1,n}X^n - c_{1,0} = X\sum_{n\geq0}c_{1,n}X^n + 3\sum_{n\geq1}n^3X^n - 626\sum_{n\geq1}nX^n</cmath>
 +
<cmath>\implies C_1(X) + 77 = XC_1(X) + 3\cdot \frac{X(X^2+4X+1)}{(1-X)^4} - 626\cdot \frac{X}{(1-X)^2}</cmath>
 +
<cmath>\implies C_1(X) = \frac{-77(1-X)^4 + 3X(X^2+4X+1) - 626X(1-X)^2}{(1-X)^5}</cmath>
 +
<cmath>= \frac{-77X^4-315X^3+802X^2-315X-77}{(1-X)^5} </cmath>
 +
<cmath>=(-77X^4-315X^3+802X^2-315X-77) \cdot \sum_{n\geq0}{n+5 \choose 5}X^n</cmath>
 +
<cmath>\implies c_{1,n} = -77{n+4 \choose 4} - 315{n+3 \choose 4} + 802{n+2 \choose 4} - 315{n+1 \choose 4} -77{n \choose 4}</cmath>
 +
<cmath>= \frac{3n^4+6n^3-1249n^2-1252n-308}{4}</cmath>
 +
Finally, we can plug <math>n=20</math> into our new explicit formula to get <cmath>c_{1,20} = \boxed{763}</cmath>
 +
<math>^*</math>This can be calculated by differentiating the generating function of the sequence 1, 1, 1, ... <math>(\sum_{n\geq0}X^n)</math> and multiplying by <math>X</math>.
 +
 +
<math>^\dagger</math>This form can be found by applying Newton's generalized binomial theorem.
 +
 +
<math>^\ddagger</math>This formula can be found by convolving the polynomial with the series.
 +
 +
- MathCactus0_0 (don't try this on a test unless you can't think of anything else!!!)
  
 
== See also ==
 
== See also ==

Latest revision as of 13:17, 16 September 2024

Problem

Let $P_0(x) = x^3 + 313x^2 - 77x - 8\,$. For integers $n \ge 1\,$, define $P_n(x) = P_{n - 1}(x - n)\,$. What is the coefficient of $x\,$ in $P_{20}(x)\,$?

Solution 1

Notice that \begin{align*}P_{20}(x) &= P_{19}(x - 20)\\ &= P_{18}((x - 20) - 19)\\ &= P_{17}(((x - 20) - 19) - 18)\\ &= \cdots\\ &= P_0(x - (20 + 19 + 18 + \ldots + 2 + 1)).\end{align*}


Using the formula for the sum of the first $n$ numbers, $1 + 2 + \cdots + 20 = \frac{20(20+1)}{2} = 210$. Therefore, \[P_{20}(x) = P_0(x - 210).\]

Substituting $x - 210$ into the function definition, we get $P_0(x-210) = (x - 210)^3 + 313(x - 210)^2 - 77(x - 210) - 8$. We only need the coefficients of the linear terms, which we can find by the binomial theorem.

  • $(x-210)^3$ will have a linear term of ${3\choose1}210^2x = 630 \cdot 210x$.
  • $313(x-210)^2$ will have a linear term of $-313 \cdot {2\choose1}210x = -626 \cdot 210x$.
  • $-77(x-210)$ will have a linear term of $-77x$.

Adding up the coefficients, we get $630 \cdot 210 - 626 \cdot 210 - 77 = \boxed{763}$.

Solution 2

Notice the transformation of $P_{n-1}(x)\to P_n(x)$ adds $n$ to the roots. Thus, all these transformations will take the roots and add $1+2+\cdots+20=210$ to them. (Indeed, this is very easy to check in general.)

Let the roots be $r_1,r_2,r_3.$ Then $P_{20}(x)=(x-r_1-210)(x-r_2-210)(x-r_3-210).$ By Vieta's/expanding/common sense, you see the coefficient of $x$ is $(r_1+210)(r_2+210)+(r_2+210)(r_3+210)+(r_3+210)(r_1+210).$ Expanding yields $r_1r_2+r_2r_3+r_3r_1+210\cdot 2(r_1+r_2+r_3)+3\cdot 210^2.$ Using Vieta's (again) and plugging stuff in yields $-77+210\cdot 2\cdot -313+3\cdot 210^2=\boxed{763}.$

Solution 3 (Overkill)

Denote the coefficient of term $x^m$ of polynomial $P_n(x)$ as $c_{m, n}$. We can see that $c_{2, 0} = 313$, $c_{1, 0} = -77$, and $c_{0, 0} = -8$. Note that $(x-n)^3 = x^3-3nx^2+3n^2x-n^3$ and $(x-n)^2 = x^2-2nx+n^2$ When substituting $x-1$ for $x$ in $P_0(x)$, we get that $P_1(x) = P_0(x-1) = (x^3-3x^2+3x-1) + 313(x^2-2x+1) -77(x-1) -8$. Observe that \[c_{2,1} = c_{2,0} - 3(1) = 313 - 3 = 310\] It is evident that \[c_{2,n} = c_{2,n-1} - 3n\] Define the generating function $C_2(X)$ as \[C_2(X) := \sum_{n \geq 0} c_{2,n}X^n\] By multiplying both sides of the previous recurrence relation and taking the sum of the terms $\forall n\geq 1$, we get that \[\implies \sum_{n\geq1} c_{2,n}X^n = \sum_{n\geq1}c_{2,n-1}X^n + 3\sum_{n\geq1}nX^n\] \[\implies \sum_{n\geq0} c_{2,n}X^n - c_{2,0} = X\sum_{n\geq0}c_{2,n}X^n + 3\sum_{n\geq1}nX^n\] \[\implies C_2(X) - 313 = XC_2(X) + 3\cdot \frac{X}{(1-X)^2}^*\] \[\implies C_2(X) = \frac{313}{1-X} - \frac{3X}{(1-X)^3}\] \[= \frac{313X^2 - 629X + 313}{(1-X)^3} = (313X^2 - 629X + 313) \cdot \sum_{n\geq0}{n+2 \choose 2}X^n\ ^\dagger\] \[\implies c_{2,n} = 313{n+2 \choose 2} - 629{n+1 \choose 2} + 313{n \choose 2}^\ddagger = \frac{-3n^2 - 3n + 626}{2}\] We can perform a similar analysis on $c_{1,n}$ to get the recurrence relation \[c_{1,n} = c_{1, n-1} + c_{2,n-1}\cdot(-2n) + 3n^2\] \[= c_{1, n-1} +3n^3 - 626n\] Define the generating function $C_1(X)$ as \[C_1(X) := \sum_{n\geq0}c_{1,n}X^n\] We can then perform this process again on our new recurrence relation: \[\implies \sum_{n\geq1} c_{1,n}X^n = \sum_{n\geq1}c_{1,n-1}X^n + 3\sum_{n\geq1}n^3X^n - 626\sum_{n\geq1}nX^n\] \[\implies \sum_{n\geq0} c_{1,n}X^n - c_{1,0} = X\sum_{n\geq0}c_{1,n}X^n + 3\sum_{n\geq1}n^3X^n - 626\sum_{n\geq1}nX^n\] \[\implies C_1(X) + 77 = XC_1(X) + 3\cdot \frac{X(X^2+4X+1)}{(1-X)^4} - 626\cdot \frac{X}{(1-X)^2}\] \[\implies C_1(X) = \frac{-77(1-X)^4 + 3X(X^2+4X+1) - 626X(1-X)^2}{(1-X)^5}\] \[= \frac{-77X^4-315X^3+802X^2-315X-77}{(1-X)^5}\] \[=(-77X^4-315X^3+802X^2-315X-77) \cdot \sum_{n\geq0}{n+5 \choose 5}X^n\] \[\implies c_{1,n} = -77{n+4 \choose 4} - 315{n+3 \choose 4} + 802{n+2 \choose 4} - 315{n+1 \choose 4} -77{n \choose 4}\] \[= \frac{3n^4+6n^3-1249n^2-1252n-308}{4}\] Finally, we can plug $n=20$ into our new explicit formula to get \[c_{1,20} = \boxed{763}\] $^*$This can be calculated by differentiating the generating function of the sequence 1, 1, 1, ... $(\sum_{n\geq0}X^n)$ and multiplying by $X$.

$^\dagger$This form can be found by applying Newton's generalized binomial theorem.

$^\ddagger$This formula can be found by convolving the polynomial with the series.

- MathCactus0_0 (don't try this on a test unless you can't think of anything else!!!)

See also

1993 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_AIME_Problems/Problem_5&oldid=227324"