8.1. It is known that $P(x)$ is a polynomial of degree 9 and $P(k)=2^{k}$ for all $k=1,2,3, \ldots, 10$. Find $P(12)$.
Answer: 4072.

Solution. Let $P(x)$ be a polynomial of degree $n$ and $P(k)=2^{k}$ for all $k=1,2,3, \ldots, n+1$. We will find $P(n+m+2), m=0,1, \ldots$. By the binomial theorem for any $k \in \mathbb{N}$ we have

$$
2^{k}=2 \cdot(1+1)^{k-1}=2 \sum_{i=0}^{k-1} C_{k-1}^{i}=2 \sum_{i=0}^{k-1} \frac{(k-1)(k-2) \ldots(k-i)}{i!}
$$

Note that the sum on the right side of this equation is a polynomial in $k$ of degree $k-1$, and if we add terms corresponding to $i=k, k+1, \ldots, n$, it will not change, since $(k-1)(k-2) \ldots(k-i)=0$ for $i \geqslant k$ (each such product contains a factor $(k-k)=0$). Therefore,

$$
2^{k}=2 \sum_{i=0}^{k-1} \frac{(k-1)(k-2) \ldots(k-i)}{i!}=2 \sum_{i=0}^{n} \frac{(k-1)(k-2) \ldots(k-i)}{i!} \quad \text { for } k \in \mathbb{N}, \quad n \geqslant k-1
$$

Consider the polynomial

$$
Q(x)=2 \sum_{i=0}^{n} \frac{(x-1)(x-2) \ldots(x-i)}{i!}
$$

This is a polynomial of degree $n$, and by the proven result, $Q(k)=2^{k}, k=1,2,3, \ldots, n+1$. Therefore, $P(x)=Q(x)$ as polynomials of degree $n$ that coincide at $n+1$ points.

Substituting $x=n+m+2(m \geqslant 0)$, we find

$$
P(n+m+2)=2 \sum_{i=0}^{n} C_{n+m+1}^{i}=2 \sum_{i=0}^{n+m+1} C_{n+m+1}^{i}-2 \sum_{i=n+1}^{n+m+1} C_{n+m+1}^{i}=2^{n+m+2}-2 \sum_{i=0}^{m} C_{n+m+1}^{i}
$$

(in the last equality, we again used the binomial theorem and the equality of binomial coefficients $\left.C_{n+m+1}^{i}=C_{n+m+1}^{n+m+1-i}\right)$. For $m=1$ we get

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

In particular, for the polynomial in the problem statement $n=9, P(12)=2^{12}-2 \cdot 9-6=4072$.

Another way to solve. A polynomial of degree $n$ is uniquely determined by its values at $n+1$ points $k=1,2,3, \ldots, n+1$. By direct substitution of these points, we verify that the condition of the problem is satisfied by the polynomial (Lagrange interpolation polynomial)

$$
\begin{aligned}
P(x)= & 2 \frac{(x-2)(x-3)(x-4) \ldots(x-(n+1))}{(1-2)(1-3)(1-4) \ldots(1-(n+1))}+2^{2} \frac{(x-1)(x-3)(x-4) \ldots(x-(n+1))}{(2-1)(2-3)(2-4) \ldots(2-(n+1))}+ \\
& +2^{3} \frac{(x-1)(x-2)(x-4) \ldots(x-(n+1))}{(3-1)(3-2)(3-4) \ldots(3-(n+1))}+\ldots+ \\
& +2^{n+1} \frac{(x-1)(x-2)(x-3) \ldots(x-n)}{(n+1-1)(n+1-2)(n+1-3) \ldots(n+1-n)}= \\
= & 2(-1)^{n} \frac{(x-2) \ldots(x-(n+1))}{n!}-2^{1} \frac{(x-1)(x-3) \ldots(x-(n+1))}{1!(n-1)!}+ \\
& \left.+2^{2} \frac{(x-1)(x-2)(x-4) \ldots(x-(n+1))}{2!(n-2)!}-\ldots+(-1)^{n} 2^{n} \frac{(x-1) \ldots(x-n)}{n!}\right) .
\end{aligned}
$$

Its value at the point $x=n+3$ is

$$
\begin{aligned}
P(n+3)= & 2(-1)^{n}\left(\frac{(n+1) n(n-1) \ldots 3 \cdot 2}{n!}-2^{1} \frac{(n+2) n(n-1) \ldots \cdot 3 \cdot 2}{1!(n-1)!}+\right. \\
& \left.+2^{2} \frac{(n+2)(n+1)(n-1) \ldots \cdot 3 \cdot 2}{2!(n-2)!}-\ldots+(-1)^{n} 2^{n} \frac{(n+2)(n+1) \ldots \cdot 4 \cdot 3}{n!}\right)= \\
= & \left.2(-1)^{n}(n+2)(n+1)\left(\frac{1}{n+2}-2^{1} C_{n}^{1} \cdot \frac{1}{n+1}+2^{2} C_{n}^{2} \cdot \frac{1}{n}+\ldots+(-1)^{n} 2^{n} C_{n}^{n} \cdot \frac{1}{2}\right)\right)= \\
= & 2(-1)^{n}(n+2)(n+1) \sum_{k=0}^{n}(-2)^{k} \frac{C_{n}^{k}}{n-k+2}=2(-1)^{n}(n+2)(n+1) S(1)
\end{aligned}
$$

where

$$
S(x)=\sum_{k=0}^{n} C_{n}^{k} \frac{(-2)^{k} x^{n-k+2}}{n-k+2}
$$

Since

$$
S^{\prime}(x)=\left(\sum_{k=0}^{n} C_{n}^{k} \frac{(-2)^{k} x^{n-k+2}}{n-k+2}\right)^{\prime}=\sum_{k=0}^{n} C_{n}^{k}(-2)^{k} x^{n-k+1}=x(x-2)^{n}=(x-2)^{n+1}+2(x-2)^{n}
$$

with the condition $S(0)=0$ we find $S(x)=\frac{(x-2)^{n+2}-(-2)^{n+2}}{n+2}+2 \frac{(x-2)^{n+1}-(-2)^{n+1}}{n+1}$. Therefore,

$$
\begin{aligned}
P(n+3) & =2(-1)^{n}(n+2)(n+1)\left(\frac{(-1)^{n+2}-(-2)^{n+2}}{n+2}+2 \frac{(-1)^{n+1}-(-2)^{n+1}}{n+1}\right)= \\
& =-2(n+1)(n+2)\left(\frac{2^{n+2}-1}{n+2}-\frac{2^{n+2}-2}{n+1}\right)=2\left(2^{n+2}-1\right)-2(n+2)=2^{n+3}-2 n-6
\end{aligned}
$$