Chaitanya's Random Pages

September 16, 2013

Polynomial extrapolation of finite exponential sequences

Filed under: mathematics — ckrao @ 11:40 am

Here is a cute problem I first encountered many years ago:

A polynomial $P(x)$ of degree $n$ satisfies $P(k) = 2^k$ for $k = 0, 1, 2, \ldots, n$. Determine $P(n+1)$.

Recall that a polynomial of degree $n$ is uniquely determined by its value at $n+1$ points. Hence $P(n+1)$ could have only one possible value. Is it $2^{n+1}$? Let’s see: here is the solution I saw at the time.

Consider the polynomial $\displaystyle P(x) = \binom{x}{0} + \binom{x}{1} + \ldots + \binom{x}{n}$. Then $P(x)$ is a polynomial of degree $n$ (the $k$‘th term has degree $k+1$). Furthermore, since $\binom{x}{k} = 0$ for $x = 0, 1, \ldots, k-1$, we have for $k = 0, 1, 2, \ldots, n$ the following:

$\displaystyle P(k) = \binom{k}{0} + \binom{k}{1} + \ldots + \binom{k}{n} = \binom{k}{0} + \binom{k}{1} + \ldots + \binom{k}{k} = 2^k.$

(Here we recall that the sum of a row of Pascal’s triangle is a power of 2.)

This shows that $P(x)$ is our unique polynomial with the desired properties, and we find

$\displaystyle P(n+1) = \binom{n+1}{0} + \binom{n+1}{1} + \ldots + \binom{n+1}{n} = 2^{n+1} - 1.$

Neat isn’t it that the polynomial almost climbs up to $2^n$ but ends up one short. 🙂 Let’s see how this result generalises. Modify the above question so that $P(k) = a^k$ for $k = 0, 1, 2, \ldots, n$ (where $a$ is a constant not equal to 1). What is $P(n+1)$? This time we let

$\displaystyle P(x) := (a-1)^0 \binom{x}{0} + (a-1)^1 \binom{x}{1} + \ldots + (a-1)^n \binom{x}{n} = \sum_{i=0}^n (a-1)^i \binom{x}{i}.$

As before $P(x)$ is clearly a degree $n$ polynomial. Furthermore, for $k = 0, 1, 2, \ldots, n$ we apply the binomial theorem to obtain

\begin{aligned} P(k) &= \sum_{i=0}^n (a-1)^i \binom{k}{i}\\ &= \sum_{i=0}^k (a-1)^i \binom{k}{i}\\ &= (a-1+1)^k\\ &= a^k. \end{aligned}

This constructed polynomial has the desired properties, so by uniqueness we simply substitute $x=n+1$ to find $P(n+1)$:

\begin{aligned} P(n+1) &= \sum_{i=0}^n (a-1)^i \binom{n+1}{i}\\ &= \sum_{i=0}^{n+1} (a-1)^i \binom{n+1}{i} - (a-1)^{n+1} \binom{n+1}{n+1}\\ &= a^{n+1} - (a-1)^{n+1}.\end{aligned}

The way such polynomials can be constructed (i.e. not pulled out of thin air!) is to write down a finite difference table – refer to an earlier blog post here: if the first diagonal of the table is $a_0, a_1, \ldots, a_n$ where $a_0 = P(0)$, then

$\displaystyle p(x) = \sum_{i=0}^n a_i \binom{x}{i}.$

In the first problem it is easy to verify that $a_i = 1$, in the generalisation $a_i = (a-1)^i$.