Difference between revisions of "1986 AIME Problems/Problem 11"
I_like_pie (talk | contribs) (→See also) |
(added my solution) |
||
(12 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | The polynomial <math>1-x+x^2-x^3+\cdots+x^{16}-x^{17}</math> may be written in the form <math>a_0+a_1y+a_2y^2+\cdots +a_{16}y^{16}+a_{17}y^{17}</math>, where <math> | + | The [[polynomial]] <math>1-x+x^2-x^3+\cdots+x^{16}-x^{17}</math> may be written in the form <math>a_0+a_1y+a_2y^2+\cdots +a_{16}y^{16}+a_{17}y^{17}</math>, where <math>y=x+1</math> and the <math>a_i</math>'s are [[constant]]s. Find the value of <math>a_2</math>. |
+ | |||
+ | __TOC__ | ||
== Solution == | == Solution == | ||
− | Since <math>(1+x)(1-x+x^2-x^3+\cdots +x^{16}-x^{17})=1-x^{18}</math>, | + | === Solution 1 === |
+ | Using the [[geometric series]] formula, <math>1 - x + x^2 + \cdots - x^{17} = \frac {1 - x^{18}}{1 + x} = \frac {1-x^{18}}{y}</math>. Since <math>x = y - 1</math>, this becomes <math>\frac {1-(y - 1)^{18}}{y}</math>. We want <math>a_2</math>, which is the coefficient of the <math>y^3</math> term in <math>-(y - 1)^{18}</math> (because the <math>y</math> in the denominator reduces the degrees in the numerator by <math>1</math>). By the [[Binomial Theorem]], this is <math>(-1) \cdot (-1)^{15}{18 \choose 3} = \boxed{816}</math>. | ||
+ | |||
+ | === Solution 2 === | ||
+ | Again, notice <math>x = y - 1</math>. So | ||
+ | |||
+ | <cmath>\begin{align*}1 - x + x^2 + \cdots - x^{17} & = 1 - (y - 1) + (y - 1)^2 - (y - 1)^3 + \cdots - (y - 1)^{17} \\ | ||
+ | & = 1 + (1 - y) + (1 - y)^2 + (1 - y)^3 \cdots + (1 - y)^{17}\end{align*}.</cmath> | ||
+ | |||
+ | We want the coefficient of the <math>y^2</math> term of each power of each binomial, which by the binomial theorem is <math>{2\choose 2} + {3\choose 2} + \cdots + {17\choose 2}</math>. The [[Hockey Stick Identity]] tells us that this quantity is equal to <math>{18\choose 3} = \boxed{816}</math>. | ||
+ | |||
+ | === Solution 3 === | ||
+ | Again, notice <math>x=y-1</math>. Substituting <math>y-1</math> for <math>x</math> in <math>f(x)</math> gives: | ||
+ | <cmath>\begin{align*}1 - x + x^2 + \cdots - x^{17} & = 1 - (y - 1) + (y - 1)^2 - (y - 1)^3 + \cdots - (y - 1)^{17} \\ | ||
+ | & = 1 + (1 - y) + (1 - y)^2 + (1 - y)^3 \cdots + (1 - y)^{17}\end{align*}.</cmath> | ||
+ | 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) === | ||
+ | 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>. | ||
+ | |||
+ | Then, since <math>f(x)=g(y)</math>, | ||
+ | <cmath>\frac{d^2f}{dx^2}=\frac{d^2g}{dy^2}</cmath> | ||
+ | <math>\frac{d^2f}{dx^2} = 2\cdot 1 - 3\cdot 2x+\cdots-17\cdot 16x^{15}</math> by the power rule. | ||
+ | |||
+ | Similarly, <math>\frac{d^2g}{dy^2} = a_2(2\cdot 1) + a_3(3\cdot 2y)+\cdots+a_{17}(17\cdot 16y^{15})</math> | ||
+ | |||
+ | Now, notice that if <math>x = -1</math>, then <math>y = 0</math>, so <math>f^{''}(-1) = g^{''}(0)</math> | ||
+ | |||
+ | <math>g^{''}(0)= 2a_2</math>, and <math>f^{''}(-1) = 2\cdot 1 + 3\cdot 2 +\cdots + 16\cdot 17</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}=\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> | ||
− | <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 == | ||
{{AIME box|year=1986|num-b=10|num-a=12}} | {{AIME box|year=1986|num-b=10|num-a=12}} | ||
− | + | ||
− | + | [[Category:Intermediate Algebra Problems]] | |
− | + | {{MAA Notice}} |
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.