Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1975 USAMO Problems/Problem 3: Difference between revisions

← Older editNewer edit →
Line 37: Line 37:




<cmath>P(n+1) &= \sum_{k=0}^n \frac{k}{k+1} \prod_{j \text{not} k} \frac{n+1-j}{k-j} \\
<cmath>P(n+1) = \sum_{k=0}^n \frac{k}{k+1} \prod_{j \text{not} k} \frac{n+1-j}{k-j}</cmath>
&= \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)}\\
<cmath>= \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)}</cmath>
&= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} \\
<cmath>= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} </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>= \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>
&= -(\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>= -(\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>
&= 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>= 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>
&= \boxed{1 - \frac{(-1)^n + 1}{n+2}}
<cmath>= \boxed{1 - \frac{(-1)^n + 1}{n+2}}</cmath>
</cmath>
 


through usage of the Binomial Theorem.
through usage of the Binomial Theorem.

Revision as of 01:51, 21 May 2015

Problem

If $P(x)$ denotes a polynomial of degree $n$ such that \[P(k)=\frac{k}{k+1}\] for $k=0,1,2,\ldots,n$, determine $P(n+1)$.

Solution

Let $Q(x) = (x+1)P(x) - x$. Clearly, $Q(x)$ has a degree of $n+1$.

Then, for $k=0,1,2,\ldots,n$, $Q(k) = (k+1)P(k) - k = (k+1)\dfrac{k}{k+1} - k = 0$.

Thus, $k=0,1,2,\ldots,n$ are the roots of $Q(x)$.

Since these are all $n+1$ of the roots, we can write $Q(x)$ as: $Q(x) = K(x)(x-1)(x-2) \cdots (x-n)$ where $K$ is a constant.

Thus, $(x+1)P(x) - x = K(x)(x-1)(x-2) \cdots (x-n)$

Plugging in $x = -1$ gives:

$(-1+1)P(-1) - (-1) = K(-1)(-1-1)(-1-2) \cdots (-1-n)$

$1 = K(-1)^{n+1}(1)(2) \cdots (n+1)$

$K = (-1)^{n+1}\dfrac{1}{(n+1)!}$

Finally, plugging in $x = n+1$ gives:

$(n+1+1)P(n+1) - (n+1) =$ $(-1)^{n+1}\dfrac{1}{(n+1)!}(n+1)(n+1-1)(n+1-2) \cdots (n+1-n)$

$(n+2)P(n+1) = (-1)^{n+1}\dfrac{1}{(n+1)!}\cdot(n+1)! + (n+1)$

$(n+2)P(n+1) = (-1)^{n+1} + (n+1)$

$P(n+1) = \dfrac{(-1)^{n+1} + (n+1)}{n+2}$

If $n$ is even, this simplifies to $P(n+1) = \dfrac{n}{n+2}$. If $n$ is odd, this simplifies to $P(n+1) = 1$.

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 \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}}\]


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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_3&oldid=70391"