Difference between revisions of "1975 USAMO Problems/Problem 3"
m (→Solution 2) |
m (→Solution 1) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
If <math>P(x)</math> denotes a polynomial of degree <math>n</math> such that <cmath>P(k)=\frac{k}{k+1}</cmath> for <math>k=0,1,2,\ldots,n</math>, determine <math>P(n+1)</math>. | If <math>P(x)</math> denotes a polynomial of degree <math>n</math> such that <cmath>P(k)=\frac{k}{k+1}</cmath> for <math>k=0,1,2,\ldots,n</math>, determine <math>P(n+1)</math>. | ||
− | ==Solution== | + | ==Solution 1== |
− | Let <math>Q(x) = (x+1)P(x) - x</math> | + | Let <math>Q(x) = (x+1)P(x) - x</math>, and clearly, <math>Q(x)</math> has a degree of <math>n+1</math>. |
− | Then, for <math>k=0,1,2,\ldots,n</math>, <math>Q(k) = (k+1)P(k) - k = (k+1)\dfrac{k}{k+1} - k = 0</math>. | + | Then, for <math>k=0,1,2,\ldots,n</math>, <math>Q(k) = (k+1)P(k) - k = (k+1)\cdot \dfrac{k}{k+1} - k = 0</math>. |
Thus, <math>k=0,1,2,\ldots,n</math> are the roots of <math>Q(x)</math>. | Thus, <math>k=0,1,2,\ldots,n</math> are the roots of <math>Q(x)</math>. | ||
− | Since these are all <math>n+1</math> of the roots, we can write <math>Q(x)</math> as | + | Since these are all <math>n+1</math> of the roots of the <math>n+1^{\text{th}}</math> degree polynomial, by the [[Factor Theorem]], we can write <math>Q(x)</math> as <cmath>Q(x) = c(x)(x-1)(x-2) \cdots (x-n)</cmath> where <math>c</math> is a constant. |
− | Thus, < | + | Thus, <cmath>(x+1)P(x) - x = c(x)(x-1)(x-2) \cdots (x-n).</cmath> |
− | + | We plug in <math>x = -1</math> to cancel the <math>(x+1)P(x)</math> and find <math>c</math>: | |
− | < | + | <cmath>\begin{align*} |
+ | -(-1) &= c(-1)(-1-1)(-1-2) \cdots (-1-n) \\ | ||
+ | 1 &= c(-1)^{n+1}(1)(2) \cdots (n+1) \\ | ||
+ | c &= (-1)^{n+1}\dfrac{1}{(n+1)!} \\ | ||
+ | \end{align*}</cmath> | ||
− | <math> | + | Finally, plugging in <math>x = n+1</math> to find <math>P(n+1)</math> gives: |
− | < | + | <cmath>\begin{align*} |
+ | Q(n+1)&=(n+2)P(n+1)-(n+1)\\ | ||
+ | (-1)^{n+1}\dfrac{1}{(n+1)!}\cdot(n+1)! &=(n+2)P(n+1)-(n+1)\\ | ||
+ | (-1)^{n+1}&=(n+2)P(n+1)-(n+1)\\ | ||
+ | (-1)^{n+1}+(n+1)&=(n+2)P(n+1)\\ | ||
+ | P(n+1) &= \dfrac{(-1)^{n+1} + (n+1)}{n+2}\\ | ||
+ | \end{align*}</cmath> | ||
− | + | If <math>n</math> is even, this simplifies to <math>P(n+1) = \dfrac{n}{n+2}</math>. If <math>n</math> is odd, this simplifies to <math>P(n+1) = 1</math>. <math>\Box</math> | |
− | + | ~Edits by BakedPotato66 | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Solution 2== | ==Solution 2== | ||
It is fairly natural to use Lagrange's Interpolation Formula on this problem: | It is fairly natural to use Lagrange's Interpolation Formula on this problem: | ||
+ | <cmath>\begin{align*} | ||
+ | P(n+1) &= \sum_{k=0}^n \frac{k}{k+1} \prod_{j \ne k} \frac{n+1-j}{k-j} \\ | ||
+ | &= \sum_{k=0}^n \frac{k}{k+1} \cdot \frac{\frac{(n+1)!}{n+1-k}}{k(k-1)(k-2) \dots 1\cdot (-1)(-2) \dots (k-n)} \\ | ||
+ | &= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} \\ | ||
+ | &= \sum_{k=0}^n (-1)^{n-k} \binom{n+1}{k} - \sum_{k=0}^n \frac{(n+1)!(-1)^{n-k}}{(k+1)!(n+1-k)!} \\ | ||
+ | &= -\left(\sum_{k=0}^{n+1} (-1)^{n+1-k} \binom{n+1}{k} - 1\right) + \frac{1}{n+2} \cdot \sum_{k=0}^n (-1)^{n+1-k} \binom{n+2}{k+1} \\ | ||
+ | &= 1 + \frac{1}{n+2} \left(\sum_{k=-1}^{n+1} (-1)^{n+2 - (k+1)} \binom{n+2}{k+1} - (-1)^{n+2} - 1\right) \\ | ||
+ | &= \boxed{1 - \frac{(-1)^n + 1}{n+2}} | ||
+ | \end{align*}</cmath> | ||
+ | through usage of the Binomial Theorem. <math>\square</math> | ||
− | + | ~lpieleanu (minor editing and reformatting) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{alternate solutions}} | {{alternate solutions}} |
Latest revision as of 17:29, 8 January 2024
Contents
Problem
If denotes a polynomial of degree
such that
for
, determine
.
Solution 1
Let , and clearly,
has a degree of
.
Then, for ,
.
Thus, are the roots of
.
Since these are all of the roots of the
degree polynomial, by the Factor Theorem, we can write
as
where
is a constant.
Thus,
We plug in to cancel the
and find
:
Finally, plugging in to find
gives:
If is even, this simplifies to
. If
is odd, this simplifies to
.
~Edits by BakedPotato66
Solution 2
It is fairly natural to use Lagrange's Interpolation Formula on this problem:
through usage of the Binomial Theorem.
~lpieleanu (minor editing and reformatting)
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
1975 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.