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.
 A: Following are two approaches to show $P(n+1) = 2^{n+1} - 1$.

*

*Method I is more systematic and use finite differences.

*Method II is more elementary and do the job with induction.


Method I - finite differences
Given any function $f(x)$ and positive number $h$, the finite difference $\Delta_h f(x)$ is the function defined by
$$\Delta_h f(x) \stackrel{def}{=} f(x+h) - f(x)$$
When $f(x)$ is a non-zero polynomial, $\Delta_h f(x)$ is again a polynomial
but with degree one less.
A corollary of this is if $f(x)$ has degree $n$, then the $(n+1)^{th}$ order finite difference of $f(x)$ vanishes. i.e
$$\sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^{n+1-k} f(x+kh) = 0$$
Consider the special case $h = 1$ and apply this to the polynomial $P(x)$ whose degree is $n$,  we get
$$\begin{align}
 &\left.\Delta^{n+1} P(x) \right|_{x=0} = 0 \\
\iff & 
\sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^{n+1-k} P(k) = 0\\
\implies & 
\sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^{n+1-k} 2^k = 2^{n+1} - P(n+1)\\
\end{align}$$
This leads to
$$
P(n+1) = 2^{n+1} - \sum_{k=1}^{n+1} \binom{n+1}{k} (-1)^{n+1-k} 2^k
= 2^{n+1} - (2-1)^{n+1}
= 2^{n+1} - 1
$$
Method II - mathematical induction
Let $\mathcal{S}_n$ be the induction statement

If $P(x)$ is a polynomial of degree $n$ such that $P(k) = 2^k$ for all $0 \le k \le n$, then $P(n+1) = 2^{n+1} - 1$.

It is trivial to check the base case $\mathcal{S}_0$.
Assume $\mathcal{S}_{n-1}$ is true and $P(x)$ is a polynomial satisfies the assumption in $\mathcal{S}_n$.
Consider the polynomial $Q(x) = P(x+1) - P(x)$, it is easy to see

*

*$Q(x)$ is a polynomial of degree $n-1$,

*For all $k$, $0 \le k \le n - 1$, $Q(k) = P(k+1) - P(k) = 2^{k+1} - 2^k = 2^k$.

This means $Q(x)$ satisfies the assumption in $\mathcal{S}_{n-1}$.
By $\mathcal{S}_{n-1}$, $Q(n) = 2^n - 1$ and hence
$$P(n+1) = P(n) + Q(n) = 2^n + (2^n - 1) = 2^{n+1} - 1$$
This establishes $\mathcal{S}_{n-1} \implies \mathcal{S}_n$ and by principle of mathematical induction, $\mathcal{S}_n$ is true for all $n$.
A: 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$$
