If for a polynomial $P(k) = 2^k$ for $k = 0, 1, . . . , n$, what is $P(n+1)$?

Question

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.

Answer 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

1. $Q(x)$ is a polynomial of degree $n-1$,
2. 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$.

Answer 2

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$$