Interpolating Polynomials

A polynomial of \( n \)-th degree is uniquely determined, given its values at \( n+1 \) points. So, suppose that \( P \) is an \( n \)-th degree polynomial and that \( P(x_i)=y_i \) in different points \( x_0,x_1, \dots,x_n \). There exist unique polynomials \( E_0,E_1,\dots,E_n \) of \( n \)-th degree such that \( E_i(x_i)=1 \) and \( E_i(x_j)=0 \) for \( j\neq i \). Then the polynomial \[ P(x)=y_0E_0(x)+y_1E_1(x)+\cdots+ y_nE_n(x)\] has the desired properties: indeed, \( P(x_i)=\sum_j y_jE_j (x_i)=y_iE_i(x_i)=y_i \). It remains to find the polynomials \( E_0,\dots,E_n \). A polynomial that vanishes at the \( n \) points \( x_j \), \( j\neq i \), is divisible by \( \prod_{j\neq i}(x-x_j) \), from which we easily obtain \( E_i(x)=\prod_{j\neq i}\frac {(x-x_j)}{(x_i-x_j)} \). This shows that:

Theorem 5.1 (Newton’s interpolating polynomial)
 

For given numbers \( y_0,\dots,y_n \) and distinct \( x_0 \), \( \dots \), \( x_n \) there is a unique polynomial \( P(x) \) of \( n \)-th degree such that \( P(x_i)=y_i \) for \( i=0 \), \( 1 \), \( \dots,n \). This polynomial is given by the formula \[ P(x)=\sum_{i=0}^ny_i\prod_{j\neq i}\frac{(x-x_j)}{(x_i-x_j)}. \]

Example
 

Find the cubic polynomial \( Q \) such that \( Q(i)=2^i \) for \( i=0,1,2,3 \).

In order to compute the value of a polynomial given in this way in some point, sometimes we do not need to determine its Newton’s polynomial. In fact, Newton’s polynomial has an unpleasant property of giving the answer in a complicated form.

Example
 

If the polynomial \( P \) of \( n \)-th degree takes the value 1 in points \( 0,2,4,\dots,2n \), compute \( P(-1) \).

Instead, it is often useful to consider the finite difference of polynomial \( P \), defined by \( P^{[1]}(x)=P(x+1)-P(x) \), which has the degree by 1 less than that of \( P \). Further, we define the \( k \)-th finite difference, \( P^{[k]}=(P^{[k-1]})^{[1]} \), which is of degree \( n-k \) (where \( \deg P=n \)). A simple induction gives a general formula \[ P^{[k]}=\sum_{i=0}^k (-1)^{k-i}\binom ki P(x+i).\] In particular, \( P^{[n]} \) is constant and \( P^{[n+1]}=0 \), which leads to

Theorem 5.2
 
\[ P(x+n+1)=\sum_{i=0}^n(-1)^{n-i}\binom{n+1}i P(x+i).\]

Problem 15
 

Polynomial \( P \) of degree \( n \) satisfies \( P(i)=\binom{n+1}i^{-1} \) for \( i=0,1,\dots,n \). Evaluate \( P(n+1) \).

Problem 16
 

If \( P(x) \) is a polynomial of an even degree \( n \) with \( P(0)=1 \) and \( P(i)=2^{i-1} \) for \( i=1,\dots,n \), prove that \( P(n+2)=2P(n+1)-1 \).


2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us