1975 USAMO Problems/Problem 3: Difference between revisions
| Line 41: | Line 41: | ||
<cmath>= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} </cmath> | <cmath>= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} </cmath> | ||
<cmath>= \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)!} </cmath> | <cmath>= \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)!} </cmath> | ||
<cmath>= -(\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} </cmath> | <cmath>= -\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} </cmath> | ||
<cmath>= 1 + \frac{1}{n+2} (\sum_{k=-1}^{n+1} (-1)^{n+2 - (k+1)} \binom{n+2}{k+1} - (-1)^{n+2} - 1) </cmath> | <cmath>= 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) </cmath> | ||
<cmath>= \boxed{1 - \frac{(-1)^n + 1}{n+2}}</cmath> | <cmath>= \boxed{1 - \frac{(-1)^n + 1}{n+2}}</cmath> | ||
Revision as of 14:39, 11 June 2019
Problem
If 
denotes a polynomial of degree 
such that ![\[P(k)=\frac{k}{k+1}\]](http://latex.artofproblemsolving.com/d/4/c/d4c0efa59cf43ae9af6aa6db9c74ff752004728b.png)
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:
![\[P(n+1) = \sum_{k=0}^n \frac{k}{k+1} \prod_{j \ne k} \frac{n+1-j}{k-j}\]](http://latex.artofproblemsolving.com/4/3/8/438ad973b360dc2f9555b39ed3010b3062b7c061.png)
![\[= \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)}\]](http://latex.artofproblemsolving.com/e/f/6/ef6a1bde828d320b12b2f46fb5a4411f984e2782.png)
![\[= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!}\]](http://latex.artofproblemsolving.com/8/c/a/8ca4e986fe5e55422e5ca789196c44aff0e8fd70.png)
![\[= \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)!}\]](http://latex.artofproblemsolving.com/b/6/1/b6142da89b4addcc9d3293c1a51f2b8d72da9121.png)
![\[= -\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}\]](http://latex.artofproblemsolving.com/e/4/c/e4cadb1922d05df1a8c346cf95978175ef9ee059.png)
![\[= 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)\]](http://latex.artofproblemsolving.com/f/4/d/f4dcf621b5984554439865079a4de694ad78bbf3.png)
![\[= \boxed{1 - \frac{(-1)^n + 1}{n+2}}\]](http://latex.artofproblemsolving.com/2/f/8/2f8171ab97f0ce605123e975c10edd75b3d8f8dc.png)
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 | ||
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing
