Polynomials (Table of contents)
# Interpolating Polynomials

**Theorem 5.1 (Newton’s interpolating polynomial)**
**Example**
**Example**
**Theorem 5.2**
\[ P(x+n+1)=\sum_{i=0}^n(-1)^{n-i}\binom{n+1}i
P(x+i).\]
**Problem 15**
**Problem 16**

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:

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

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

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