<s>[INST] If for a polynomial $P(k) = 2^k$ for $k = 0, 1, . . . , n$, what is $P(n+1)$? 
For a polynomial $P(x)$ of degree $n$, $P(k) = 2^k$ for $k = 0, 1, 2, . . . , n$. Find $P(n+1)$.

If $n=1$, $P(x)=x+1$ and $P(2)=3$.
If $n=2$, $P(x)=0.5x^2+0.5x+1$ and $P(3)=7$.
How to approach further cases? I am stuck.
 [/INST] Here's a link to the method I mentioned in the comments.
First, we construct a difference table for the degree $n$ polynomial $P(k)$
$$\begin{array}{c|c|c|c|c|c|c|c} k&P(k)&D_1(k)&D_2(k)&\ldots\ldots\ldots&D_{n-2}(k)&D_{n-1}(k)&D_n(k)\\ \hline\\ 0&1&1&1&\ldots\ldots\ldots&1&1&1\\ 1&2&2&2&\ldots\ldots\ldots&2&2&1\\ 2&4&4&4&\ldots\ldots\ldots&4&3&\\ 3&8&8&8&\ldots\ldots\ldots&7\\ 4&16&16&&\\ 5&32&\vdots\\ \vdots&\vdots&\vdots\\ n-1&2^{n-1}&2^{n-1}\\ n&2^n\\ n+1\end{array}$$
Now, take the diagonal starting from $D_n(2)$ and ending at $P(n+1)$.
The diagonal goes like this: $1,3,7,\ldots$ i.e, at each term, powers of $2$ are added.
This gives us with,
$$P(n+1)=1+2+4+\dots+\textrm{upto }(n+1)\textrm{ terms}\\ P(n+1)=\sum_{i=0}^{n}2^i=\frac{2^{n+1}-1}{2-1}=2^{n+1}-1$$
</s>