1975 USAMO Problems/Problem 3
Contents
Problem
If denotes a polynomial of degree such that for , determine .
Solution
Let . Clearly, has a degree of .
Then, for , .
Thus, are the roots of .
Since these are all of the roots, we can write as: where is a constant.
Thus,
Plugging in gives:
Finally, plugging in gives:
If is even, this simplifies to . If is odd, this simplifies to .
Solution 2
It is fairly natural to use Lagrange's Interpolation Formula on this problem:
$\begin{align} P(n+1) &= \sum_{k=0}^n \frac{k}{k+1} \prod_{j \text{not} 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)!} \\ &= -(\sum_{k=0}^{n+1} (-1)^{n+1-k} \binom{n+1}{k} - 1) + \frac{1}{n+2} \cdot \sum_{k=0}^n (-1)^{n+1-k} \binom{n+2}{k+1} \\ &= 1 + \frac{1}{n+2} (\sum_{k=-1}^{n+1} (-1)^{n+2 - (k+1)} \binom{n+2}{k+1} - (-1)^{n+2} - 1) \\ &= \boxed{1 - \frac{(-1)^n + 1}{n+2}} \end{align}$ (Error compiling LaTeX. Unknown error_msg)
through usage of the Binomial Theorem.
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.