# 1975 USAMO Problems/Problem 3

## 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 1

Let $Q(x) = (x+1)P(x) - x$, and 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)\cdot \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 of the $n+1^{\text{th}}$ degree polynomial, we can write $Q(x)$ as $$Q(x) = c(x)(x-1)(x-2) \cdots (x-n)$$ where $c$ is a constant.

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

We plug in $x = -1$ to cancel the $(x+1)P(x)$ and find $c$:

\begin{align*} -(-1) &= c(-1)(-1-1)(-1-2) \cdots (-1-n) \\ 1 &= c(-1)^{n+1}(1)(2) \cdots (n+1) \\ c &= (-1)^{n+1}\dfrac{1}{(n+1)!} \\ \end{align*}

Finally, plugging in $x = n+1$ to find $P(n+1)$ gives:

\begin{align*} Q(n+1)&=(n+2)P(n+1)-(n+1)\\ (-1)^{n+1}\dfrac{1}{(n+1)!}\cdot(n+1)! &=(n+2)P(n+1)-(n+1)\\ (-1)^{n+1}&=(n+2)P(n+1)-(n+1)\\ (-1)^{n+1}+(n+1)&=(n+2)P(n+1)\\ P(n+1) &= \dfrac{(-1)^{n+1} + (n+1)}{n+2}\\ \end{align*}

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

~Edits by BakedPotato66

## 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 \ne 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)!} \\ &= -\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} \\ &= 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) \\ &= \boxed{1 - \frac{(-1)^n + 1}{n+2}} \end{align*} through usage of the Binomial Theorem.