Difference between revisions of "1986 AIME Problems/Problem 11"
(→Solution 4(calculus)) |
(added my solution) |
||
(One intermediate revision by one other user 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 39: | Line 39: | ||
-AOPS81619 | -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.