|
|
| Line 19: |
Line 19: |
| | | | |
| | 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> | | 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:
| |
| − | \begin{itemize}
| |
| − | \item <math>(x-n)^3 = x^3-3nx^2+3n^2x-n^3</math>
| |
| − | \item <math>(x-n)^2 = x^2-2nx+n^2</math>
| |
| − | \end{itemize}
| |
| − | 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>
| |
| − | \pagebreak\newline
| |
| − | 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>\pushQED{\qed}c_{1,20} = \boxed{763} \qedhere \popQED</cmath>
| |
| − | {\footnotesize *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>. \newline
| |
| − | <math>^\dagger</math>This form can be found by applying Newton's generalized binomial theorem. \newline
| |
| − | <math>^\ddagger</math>This formula can be found by convolving the polynomial with the series.}
| |
| | | | |
| | == See also == | | == See also == |
Problem
Let 
. For integers 
, define 
. What is the coefficient of 
in 
?
Solution 1
Notice that
Using the formula for the sum of the first 
numbers, 
. Therefore, ![\[P_{20}(x) = P_0(x - 210).\]](//latex.artofproblemsolving.com/6/3/f/63f8ce4cbf48964dd61df68155e7c6b185964047.png)
Substituting 
into the function definition, we get 
. We only need the coefficients of the linear terms, which we can find by the binomial theorem.
will have a linear term of 
.
will have a linear term of 
.
will have a linear term of 
.
Adding up the coefficients, we get 
.
Solution 2
Notice the transformation of 
adds to the roots. Thus, all these transformations will take the roots and add 
to them. (Indeed, this is very easy to check in general.)
Let the roots be 
Then 
By Vieta's/expanding/common sense, you see the coefficient of 
is 
Expanding yields 
Using Vieta's (again) and plugging stuff in yields 
See also
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. 
. For integers 
, define 
. What is the coefficient of 
in 
?
numbers, 
. Therefore, ![\[P_{20}(x) = P_0(x - 210).\]](http://latex.artofproblemsolving.com/6/3/f/63f8ce4cbf48964dd61df68155e7c6b185964047.png)
into the function definition, we get 
. We only need the coefficients of the linear terms, which we can find by the binomial theorem.
will have a linear term of 
.
will have a linear term of 
.
will have a linear term of 
.
.
adds 
to them. (Indeed, this is very easy to check in general.)
Then 
By Vieta's/expanding/common sense, you see the coefficient of 
is 
Expanding yields 
Using Vieta's (again) and plugging stuff in yields 
