For the $n$-degree polynomial $P(x)$, it holds that $P(j)=2^{j-1}$, if $j=1,2, \ldots, n, n+1$. What is the value of $P(n+2)$?
I. solution. Let $P(x)$'s first-order difference polynomial be denoted by $P_1(x) = P(x+1) - P(x)$ (this is clearly of degree $(n-1)$), the second-order difference polynomial by $P_2(x) = P_1(x+1) - P_1(x)$ (this polynomial has degree $n-2$), and generally define the $k$-th order difference polynomial as $P_k(x) = P_{k-1}(x+1) - P_{k-1}(x)$. By induction on $k$, it is easy to see that the degree of $P_k(x)$ is $n-k$, so the polynomial $P_n(x)$ is constant. This constant (and the intermediate values of the difference polynomials) can be determined by repeated subtraction from our data:

![](https://cdn.mathpix.com/cropped/2024_05_02_99a5baace114832fe907g-1.jpg?height=398&width=938&top_left_y=392&top_left_x=450)

Thus, $P_n(x)$ is the constant polynomial 1. From this, we can obtain the value of $P(n+2)$ as follows:

\[
\begin{aligned}
P(n+2) & = P(n+1) + P_1(n+1) = P(n+1) + P_1(n) + P_2(n) \\
& = P(n+1) + P_1(n) + P_2(n-1) + P_3(n-1) = \ldots \\
& = P(n+1) + P_1(n) + P_2(n-1) + P_3(n-2) + \ldots + P_{n-1}(2) + P_n(2) = \\
& = 2^n + 2^{n-1} + 2^{n-2} + \ldots + 2^2 + 2 + 1 = \\
& = 2^{n+1} - 1
\end{aligned}
\]

(This is the sum of the last "diagonal" in our table).

II. solution. We use the well-known identity

\[
\sum_{i=0}^{k-1} \binom{k-1}{i} = 2^{k-1}
\]

Consider the polynomials $q_0(x) = 1$, and for $k \geq 1$,

\[
q_k(x) = \binom{x-1}{k} = \frac{(x-1) \cdot (x-2) \cdot \ldots \cdot (x-k)}{k!}
\]

which are of degree $k$. Then the polynomial

\[
q(x) = q_0(x) + q_1(x) + \ldots + q_k(x) + \ldots + q_n(x)
\]

takes the values $2^0, 2^1, 2^2, \ldots, 2^n$ at the points $x = 1, 2, \ldots, n+1$. Indeed, if $x = k$, then

\[
q_0(k) + q_1(k) + \ldots + q_{k-1}(k) = \binom{k-1}{0} + \binom{k-1}{1} + \ldots + \binom{k-1}{k-1} = 2^{k-1}
\]

and for $t \geq k$, $q_t(k) = 0$. Thus, the $n$-th degree polynomial $q(x)$ takes exactly the same values at $x = 1, 2, \ldots, n+1$ as $P(x)$. If two $n$-th degree polynomials agree at $(n+1)$ distinct points, they are identical; hence $q(x)$ is the desired polynomial. The value of this polynomial at $x = n+2$ is:

\[
\sum_{i=0}^{n} \binom{n+1}{i} = 2^{n+1} - 1
\]