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)}. \]


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.


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\).