Difference between revisions of "1975 USAMO Problems/Problem 3"
m (Edits) |
m (→Solution 1) |
||
(2 intermediate revisions by 2 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>, and clearly, <math>Q(x)</math> has a degree of <math>n+1</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>. | ||
Line 9: | Line 9: | ||
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 of the <math>n+1^{\text{th}}</math> degree polynomial, 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. | + | 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, <cmath>(x+1)P(x) - x = c(x)(x-1)(x-2) \cdots (x-n).</cmath> | Thus, <cmath>(x+1)P(x) - x = c(x)(x-1)(x-2) \cdots (x-n).</cmath> | ||
Line 38: | Line 38: | ||
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.