Difference between revisions of "1975 USAMO Problems/Problem 3"

(Problem)
Line 1: Line 1:
 
==Problem==
 
==Problem==
If <math>P(x)</math> denotes a polynomial of degree <math>n</math> such that <math>P(k)=k/(k+1)</math> 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)=k/(k+1)</cmath> for <math>k=0,1,2,\ldots,n</math>, determine <math>P(n+1)</math>.
  
 
==Solution==
 
==Solution==

Revision as of 01:42, 21 May 2015

Problem

If $P(x)$ denotes a polynomial of degree $n$ such that \[P(k)=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)=k=0nkk+1jnotkn+1jkj=k=0nkk+1(n+1)!n+1kk(k1)(k2)1(1)(2)(kn)=k=0nkk+1(1)nk(n+1)!k!(n+1k)!=k=0n(1)nk(n+1k)k=0n(n+1)!(1)nk(k+1)!(n+1k)!=(k=0n+1(1)n+1k(n+1k)1)+1n+2k=0n(1)n+1k(n+2k+1)=1+1n+2(k=1n+1(1)n+2(k+1)(n+2k+1)(1)n+21)=1(1)n+1n+2$ (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 (ProblemsResources)
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. AMC logo.png