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

\( Q(x)=\frac{(x-1)(x-2)(x-3)}{-6}+
\frac{2x(x-2)(x-3)}{2}+\frac{4x(x-1)(x-3)}{-2}+
\frac{8x(x-1)(x-2)}{6}=\frac{x^3+5x+6}6 \).

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

\( P(x) \) is of course identically equal to 1, so
\( P(-1) =1 \). But if we apply the Newton polynomial, here is what we
get: \[ P(1)=\sum_{i=0}^n \prod_{j\neq i}\frac{1-2i}{(2j-2i)}=
\sum_{i=0}^n \prod_{j\neq i}\frac{-1-2j}{(2i-2j)}=
\frac{(2n+1)!!}{2^n}\sum_{i=1}^{n+1}\frac{(-1)^{n-i}}{(2i+1)
i!(n-i)!}. \]

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

We have
\[ 0=\sum_{i=0}^{n+1}(-1)^i\binom{n+1}{i}P(i)=
(-1)^{n+1}P(n+1)+\left\{\begin{array}{c} 1,\hspace{5mm}2\mid
n;\\ 0,\hspace{5mm}2\nmid n.\end{array}\right.\] It follows that \( \displaystyle
P(n+1)=\left\{
\begin{array}{c}1,\hspace{5mm}2\mid n;\\ 0,\hspace{5mm}2\nmid n.
\end{array}\right. \)

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

We observe that \( P^{[1]}(0)=0 \) i \( P^{[1]}(i)= 2^{i-1} \) for
\( i=1,\dots,n-1 \); furthermore, \( P^{[2]}(0)=1 \) i \( P^{[2]}(i) =2^{i-1} \)
for \( i=1,\dots,n-2 \), etc. In general, it is easily seen that
\( P^{[k]}(i)=2^{i-1} \) for \( i=1,\dots,n-k \), and \( P^{[k]}(0) \) is 0 for
\( k \) odd and 1 for \( k \) even. Now
\[ P(n+1)=P(n)+P^{[1]}(n)=
\cdots=P(n)+P^{[1]}(n-1)+\cdots+P^{[n]}(0)=\left\{\begin{array}
{ll}2^n,&2\mid n;\\ 2^n-1,&2\nmid n.\end{array}\right.\] Similarly,
\( P(n+2)=2^{2n+1}-1 \).