Difference between revisions of "1993 AIME Problems/Problem 5"
m (Fixed solution number from 3 to 2) |
|||
(12 intermediate revisions by 2 users not shown) | |||
Line 15: | Line 15: | ||
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 | + | == Solution 2 (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> | |
− | |||
− | |||
− | |||
− | |||
− | 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 | ||
− | |||
− | |||
− | |||
− | |||
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 | 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> | <cmath>c_{2,1} = c_{2,0} - 3(1) = 313 - 3 = 310</cmath> | ||
Line 35: | Line 26: | ||
<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\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 \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{ | + | <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>\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>= \frac{313X^2 - 629X + 313}{(1-X)^3} = (313X^2 - 629X + 313) \cdot \sum_{n\geq0}{n+2 \choose 2}X^n\ ^\dagger</cmath> | ||
Line 42: | Line 33: | ||
<cmath>c_{1,n} = c_{1, n-1} + c_{2,n-1}\cdot(-2n) + 3n^2</cmath> | <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> | <cmath>= c_{1, n-1} +3n^3 - 626n</cmath> | ||
− | |||
Define the generating function <math>C_1(X)</math> as | Define the generating function <math>C_1(X)</math> as | ||
<cmath>C_1(X) := \sum_{n\geq0}c_{1,n}X^n</cmath> | <cmath>C_1(X) := \sum_{n\geq0}c_{1,n}X^n</cmath> | ||
Line 54: | Line 44: | ||
<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>\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> | <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 | + | Finally, we can plug <math>n=20</math> into our new explicit formula to get <cmath>c_{1,20} = \boxed{763}</cmath> |
− | <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>^\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. | + | |
+ | <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 23:28, 9 June 2025
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,
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 (Overkill)
Denote the coefficient of term of polynomial
as
. We can see that
,
, and
. Note that
and
When substituting
for
in
, we get that
. Observe that
It is evident that
Define the generating function
as
By multiplying both sides of the previous recurrence relation and taking the sum of the terms
, we get that
We can perform a similar analysis on
to get the recurrence relation
Define the generating function
as
We can then perform this process again on our new recurrence relation:
Finally, we can plug
into our new explicit formula to get
This can be calculated by differentiating the generating function of the sequence 1, 1, 1, ...
and multiplying by
.
This form can be found by applying Newton's generalized binomial theorem.
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 |
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.