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

Revision as of 16:48, 31 December 2008

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)$ .

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$ .

@@ Line 3: / Line 3: @@
 ==Solution==
-{{solution}}
+Let <math>Q(x) = (x+1)P(x) - x</math>. Clearly, <math>Q(x)</math> has a degree of <math>n+1</math>.
+Then, for <math>k=0,1,2,\ldots,n</math>, <math>Q(k) = (k+1)P(k) - k = (k+1)\dfrac{k}{k+1} - k = 0</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, we can write <math>Q(x)</math> as: <math>Q(x) = K(x)(x-1)(x-2) \cdots (x-n)</math> where <math>K</math> is a constant.
+Thus, <math>(x+1)P(x) - x = K(x)(x-1)(x-2) \cdots (x-n)</math>
+Plugging in <math>x = -1</math> gives:
+<math>(-1+1)P(-1) - (-1) = K(-1)(-1-1)(-1-2) \cdots (-1-n)</math>
+<math>1 = K(-1)^{n+1}(1)(2) \cdots (n+1)</math>
+<math>K = (-1)^{n+1}\dfrac{1}{(n+1)!}</math>
+Finally, plugging in <math>x = n+1</math> gives:
+<math>(n+1+1)P(n+1) - (n+1) =</math> <math>(-1)^{n+1}\dfrac{1}{(n+1)!}(n+1)(n+1-1)(n+1-2) \cdots (n+1-n)</math>
+<math>(n+2)P(n+1) = (-1)^{n+1}\dfrac{1}{(n+1)!}\cdot(n+1)! + (n+1)</math>
+<math>(n+2)P(n+1) = (-1)^{n+1} + (n+1)</math>
+<math>P(n+1) = \dfrac{(-1)^{n+1} + (n+1)}{n+2}</math>
+If <math>n</math> is even, this simplifies to <math>P(n+1) = \dfrac{n}{n+2}</math>. If <math>n</math> is odd, this simplifies to <math>P(n+1) = 1</math>.
 ==See also==

1975 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions