13. (ROM) Let $P$ be a polynomial of degree $n$ satisfying
$$
P(k)=\binom{n+1}{k}^{-1} \quad \text { for } k=0,1, \ldots, n
$$

Determine $P(n+1)$.
13. Lemma. For any polynomial $P$ of degree at most $n$,
$$
\sum_{i=0}^{n+1}(-1)^{i}\binom{n+1}{i} P(i)=0 \text {. }
$$

Proof. We shall use induction on $n$. For $n=0$ it is trivial. Assume that it is true for $n=k$ and suppose that $P(x)$ is a polynomial of degree $k+1$. Then $P(x)-P(x+1)$ clearly has degree at most $k$; hence (1) gives
$$
\begin{aligned}
0 & =\sum_{i=0}^{k+1}(-1)^{i}\binom{k+1}{i}(P(i)-P(i+1)) \\
& =\sum_{i=0}^{k+1}(-1)^{i}\binom{k+1}{i} P(i)+\sum_{i=1}^{k+2}(-1)^{i}\binom{k+1}{i-1} P(i) \\
& =\sum_{i=0}^{k+2}(-1)^{(}\binom{k+2}{i} P(i) .
\end{aligned}
$$

This completes the proof of the lemma.
Now we apply the lemma to obtain the value of $P(n+1)$. Since $P(i)=$ $\binom{n+1}{i}^{-1}$ for $i=0,1, \ldots, n$, we have
$$
0=\sum_{i=0}^{n+1}(-1)^{\prime}\binom{n+1}{i} P(i)=(-1)^{n+1} P(n+1)+\left\{\begin{array}{ll}
1, & 2 \mid n \\
0, & 2 \nmid n
\end{array}\right.
$$

It follows that $P(n+1)=\left\{\begin{array}{ll}1, & 2 \mid n ; \\ 0, & 2 \nmid n\end{array}\right.$