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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: