If for a polynomial $P(k) = 2^k$ for $k = 0, 1, . . . , n$, what is $P(n+1)$?
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$.
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$$