Difference between revisions of "1986 AIME Problems/Problem 11"
(→Solution 4(calculus)) |
(added my solution) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 21: | Line 21: | ||
From binomial theorem, the coefficient of the <math>y^2</math> term is <math>{2\choose 0} + {3\choose 1} + \cdots + {17\choose 15}</math>. This is actually the sum of the first 16 triangular numbers, which evaluates to <math>\frac{(16)(17)(18)}{6} = \boxed{816}</math>. | From binomial theorem, the coefficient of the <math>y^2</math> term is <math>{2\choose 0} + {3\choose 1} + \cdots + {17\choose 15}</math>. This is actually the sum of the first 16 triangular numbers, which evaluates to <math>\frac{(16)(17)(18)}{6} = \boxed{816}</math>. | ||
− | == Solution 4(calculus) == | + | === Solution 4(calculus) === |
Let <math>f(x)=1-x+x^2-x^3+\cdots+x^{16}-x^{17}</math> and <math>g(y)=a_0+a_1y+a_2y^2+\cdots +a_{16}y^{16}+a_{17}y^{17}</math>. | Let <math>f(x)=1-x+x^2-x^3+\cdots+x^{16}-x^{17}</math> and <math>g(y)=a_0+a_1y+a_2y^2+\cdots +a_{16}y^{16}+a_{17}y^{17}</math>. | ||
Line 36: | Line 36: | ||
Now, we can use the hockey stick theorem to see that <math>2\cdot 1 + 3\cdot 2 +\cdots + 16\cdot 17 = 2\binom{18}{3}</math> | Now, we can use the hockey stick theorem to see that <math>2\cdot 1 + 3\cdot 2 +\cdots + 16\cdot 17 = 2\binom{18}{3}</math> | ||
− | Thus, <math>2a_2 = 2\binom{18}{3}\rightarrow a_2 = \binom{18}{3}=</math> | + | Thus, <math>2a_2 = 2\binom{18}{3}\rightarrow a_2 = \binom{18}{3}=\boxed{816}</math> |
+ | |||
+ | -AOPS81619 | ||
+ | |||
+ | === Solution 5 (Linear Algebra) === | ||
+ | |||
+ | Let <math>V</math> be the vector space of polynomials of degree <math>\leq 17, </math> and let <math>B = \{1, x, x^2, ..., x^{17} \}</math> and <math>C = \{1, (x+1), (x+1)^2, ..., (x+1)^{17} \}</math> be two bases for <math>V</math>. | ||
+ | Let <math>\vec{v} \in V</math> be the polynomial given in the problem, and it is easy to see that <math>[ \vec{v} ]_B = \langle 1, -1, 1, -1, ... , 1, -1 \rangle.</math> | ||
+ | |||
+ | Note that the transformation matrix from <math>C</math> to <math>B</math> can be easily found to be <math>P_{C \to B} = [ [\vec{c_1}]_B [\vec{c_2}]_B ... [\vec{c_3}]_B ] = \begin{bmatrix} \tbinom{0}{0} & \tbinom{1}{0} & \tbinom{2}{0} & \cdots & \tbinom{17}{0} \\ 0 & \tbinom{1}{1} & \tbinom{2}{1} & \cdots & \tbinom{17}{1} \\ 0 & 0 & \tbinom{2}{2} & \cdots & \tbinom{17}{2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \tbinom{17}{17} \end{bmatrix} .</math> | ||
+ | |||
+ | I claim that <math>P_{B \to C} = \begin{bmatrix} \tbinom{0}{0} & -\tbinom{1}{0} & \tbinom{2}{0} & \cdots & -\tbinom{17}{0} \\ 0 & \tbinom{1}{1} & -\tbinom{2}{1} & \cdots & \tbinom{17}{1} \\ 0 & 0 & \tbinom{2}{2} & \cdots & -\tbinom{17}{2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \tbinom{17}{17} \end{bmatrix} ,</math> where the term <math>\dbinom{n}{k}</math> is negated if <math>n+k</math> is odd. | ||
+ | |||
+ | One can prove that the <math>i</math>th row of <math>P_{C \to B}</math> dotted with the <math>j</math>th column of <math>P_{B \to C}</math> is <math>\delta_{i, j}</math> by using combinatorial identities, which is left as an exercise for the reader. Thus, since the two matrices multiply to form <math>\mathbb{I}_{18},</math> we have proved that <math>P_{B \to C} = \begin{bmatrix} \tbinom{0}{0} & -\tbinom{1}{0} & \tbinom{2}{0} & \cdots & -\tbinom{17}{0} \\ 0 & \tbinom{1}{1} & -\tbinom{2}{1} & \cdots & \tbinom{17}{1} \\ 0 & 0 & \tbinom{2}{2} & \cdots & -\tbinom{17}{2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \tbinom{17}{17} \end{bmatrix} .</math> | ||
+ | |||
+ | To find the coordinates of <math>\vec{v}</math> under basis <math>C,</math> we compute the product <math>[ \vec{v} ]_C = P_{B \to C} [\vec{v} ]_B = \begin{bmatrix} \tbinom{0}{0} & -\tbinom{1}{0} & \tbinom{2}{0} & \cdots & -\tbinom{17}{0} \\ 0 & \tbinom{1}{1} & -\tbinom{2}{1} & \cdots & \tbinom{17}{1} \\ 0 & 0 & \tbinom{2}{2} & \cdots & -\tbinom{17}{2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \tbinom{17}{17} \end{bmatrix} \begin{bmatrix} 1 \\ -1 \\ 1 \\ \vdots \\ -1 \end{bmatrix} = \begin{bmatrix} \sum_{n=0}^{17} \tbinom{n}{0} \\ -\sum_{n=1}^{17} \tbinom{n}{1} \\ \sum_{n=2}^{17} \tbinom{n}{2} \\ \vdots \\ -\sum_{n=17}^{17} \tbinom{n}{17} \end{bmatrix} = \begin{bmatrix} \tbinom{18}{1} \\ - \tbinom{18}{2} \\ \tbinom{18}{3} \\ \vdots \\ -\tbinom{18}{18} \end{bmatrix},</math> where the last equality was obtained via Hockey Stick Identity. | ||
+ | |||
+ | Thus, our answer is <math>a_2 = [ [ \vec{v} ]_C ]_3 = \dbinom{18}{3} = \boxed{816}.</math> | ||
+ | |||
+ | -fidgetboss_4000 | ||
== See also == | == See also == |
Latest revision as of 16:51, 9 June 2023
Problem
The polynomial may be written in the form
, where
and the
's are constants. Find the value of
.
Contents
Solution
Solution 1
Using the geometric series formula, . Since
, this becomes
. We want
, which is the coefficient of the
term in
(because the
in the denominator reduces the degrees in the numerator by
). By the Binomial Theorem, this is
.
Solution 2
Again, notice . So
We want the coefficient of the term of each power of each binomial, which by the binomial theorem is
. The Hockey Stick Identity tells us that this quantity is equal to
.
Solution 3
Again, notice . Substituting
for
in
gives:
From binomial theorem, the coefficient of the
term is
. This is actually the sum of the first 16 triangular numbers, which evaluates to
.
Solution 4(calculus)
Let and
.
Then, since ,
by the power rule.
Similarly,
Now, notice that if , then
, so
, and
.
Now, we can use the hockey stick theorem to see that
Thus,
-AOPS81619
Solution 5 (Linear Algebra)
Let be the vector space of polynomials of degree
and let
and
be two bases for
.
Let
be the polynomial given in the problem, and it is easy to see that
Note that the transformation matrix from to
can be easily found to be
I claim that where the term
is negated if
is odd.
One can prove that the th row of
dotted with the
th column of
is
by using combinatorial identities, which is left as an exercise for the reader. Thus, since the two matrices multiply to form
we have proved that
To find the coordinates of under basis
we compute the product
where the last equality was obtained via Hockey Stick Identity.
Thus, our answer is
-fidgetboss_4000
See also
1986 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
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.