Polynomial interpolation and remainder

For $n=0$, if $c_0=0$ choose the zero polynomial, whose evaluation is $0$; if $c_0\mathrm{\ne }0$, choose the one-term formal list $(c_0)$, of degree $0$ and leading coefficient $c_0$. In both cases its evaluation is $c_0{x}^0=c_0$.

Suppose the assertion holds for vectors of length $n+1$, and consider $c_0,\dots ,c_n,c_{n+1}$. If $c_{n+1}=0$, the finite-sum recursion and [F4] show that the displayed evaluation is the evaluation for the prefix vector; use its representative from the induction hypothesis. If $c_{n+1}\mathrm{\ne }0$, the formal coefficient list $(c_0,\dots ,c_n,c_{n+1})$ is valid by [F1], has degree $n+1$ and leading coefficient $c_{n+1}$, and evaluates to the displayed sum by [F2]. The zero-characterization in the first case is inherited from the prefix; in the second case both the vector and the polynomial are nonzero.

Induction [F3] now supplies the representative for every $n$. The construction also proves that it is zero exactly when all vector entries vanish, and that a nonzero final entry is its leading coefficient at degree $n$.

For $n=0$, both iterated sums are empty and equal $0$ by [F1].

Assume the identity for every $n$-by-$n$ real array, and consider an arbitrary $(n+1)$-by-$(n+1)$ array. Splitting at the last row and column and using finite-sum additivity [F1] gives ${\sum }_{j<n+1}{\sum }_{k<n+1}{a}_{jk}={\sum }_{j<n}{\sum }_{k<n}{a}_{jk}+{\sum }_{j<n}{a}_{j,n}+{\sum }_{k<n}{a}_{n,k}+a_{n,n}$. Splitting in the opposite order gives ${\sum }_{k<n+1}{\sum }_{j<n+1}{a}_{jk}={\sum }_{k<n}{\sum }_{j<n}{a}_{jk}+{\sum }_{k<n}{a}_{n,k}+{\sum }_{j<n}{a}_{j,n}+a_{n,n}$. The induction hypothesis equates the first terms, and associativity and commutativity [F3] equate the remaining sums after interchanging their order. Thus the identity holds for the successor size.

Induction [F2] using steps 1.1 and 1.2 proves the identity for every finite square array.

For $n=0$, the empty product is $1$, which is nonzero by [F3].

Suppose the prefix product ${\prod }_{k<n}{a}_k$ is nonzero and the next factor $a_n$ is nonzero. By [F1] the extended product is $({\prod }_{k<n}{a}_k)a_n$; [F4] implies it cannot be zero, since both factors are nonzero.

Induction [F2] applied to steps 1.1 and 1.2 proves the claim for every finite list of nonzero real factors.

For a nonzero formal polynomial, [F1] gives $p(X)={\sum }_{k=0}^m{a}_k{X}^k$, since zero padding adds only zero terms. For the zero polynomial, $p\equiv 0$ and the given evaluation vector is all zero, so the same identity holds without representing the formal object by a coefficient list. For $0\le r\le m$, define the real function $Q_r(X)={\sum }_{k=r}^m{a}_k({\prod }_{s=0}^{r-1}(k-s))X^{k-r}$, with the empty product equal to $1$; each factor $k-s$ is natural because $k\ge r>s$.

At $r=0$, $Q_0=p=p^{(0)}$ by [F2]. If $r<m$ and $p^{(r)}=Q_r$, termwise differentiation in [F3] kills the $k=r$ constant term and multiplies each term with $k>r$ by its exponent $k-r$; for each $k>r$, the resulting real coefficient is $a_k({\prod }_{s=0}^{r-1}(k-s))(k-r)=a_k{\prod }_{s=0}^r(k-s)$. Indeed the finite natural product extends by its last factor, and [F7] carries that natural identity to the product of canonical real images. The new exponent is $(k-r)-1=k-(r+1)$, so the differentiated sum is exactly $Q_{r+1}$. Hence $p^{(r+1)}=Q_{r+1}$.

Apply [F4] to the property $P(r)$ that $r\le m$ implies $p^{(r)}=Q_r$. Step 2.1 proves $P(0)$. If $P(r)$ holds and $r+1\le m$, then $r<m$ and step 2.1 proves $p^{(r+1)}=Q_{r+1}$; if $r+1>m$, $P(r+1)$ is vacuous. Thus $P(m)$ holds.

At $r=m$, the sum defining $Q_m$ contains only $k=m$ and equals $a_m{\prod }_{s=0}^{m-1}(m-s)=a_{m}m{!}_{\mathbb{R}}$: [F6] identifies the natural falling product with $m!$, and [F7] carries it to the real product in the statement. This proves the stated derivative and both special cases.

At $n=0$, the empty product is $1$, the evaluation of the one-term polynomial $(1)$, which is monic of degree zero.

Suppose $P_n(X)={\sum }_{k=0}^n{a}_k{X}^k$ with $a_n=1$, as supplied by the induction hypothesis. Multiplication by the next factor gives $P_n(X)(X-r_n)={\sum }_{k=0}^n{a}_k{X}^{k+1}-{\sum }_{k=0}^n{r}_n{a}_k{X}^k\mathrm{.}$ By the finite-sum and field laws [F2, F4], this is represented by the coefficient list $b_0=-r_n{a}_0$, $b_k=a_{k-1}-r_n{a}_k$ for $1\le k\le n$, and $b_{n+1}=a_n=1$. This list is a formal polynomial by [F1]; its last coefficient is $1$, so its degree is $n+1$ and it is monic.

Induction [F5] proves the claim for every finite list length, including the empty product case.

For $n=0$, both products are empty and equal $1$ by [F1]. Also $1^{-1}=1$, since $1\cdot 1=1$ and inverses are unique by [F3, F4]. Thus both sides equal $1$.

Assume the identity for the first $n$ terms, and append $u_n\in \mathbb{R}$ and $d_n\mathrm{\ne }0$. Put $U={\prod }_{k<n}{u}_k$ and $D={\prod }_{k<n}{d}_k$. By [F5], both $D$ and the extended denominator product $D{d}_n$ are nonzero, so $D^{-1}$ and $(D{d}_n{)}^{-1}$ exist; also $d_n^{-1}$ exists by [F3]. Associativity and commutativity give $(D{d}_n)(D^{-1}{d}_n^{-1})=(D{D}^{-1})(d_n{d}_n^{-1})=1$, so uniqueness [F4] gives $(D{d}_n{)}^{-1}=D^{-1}{d}_n^{-1}$. Using the induction hypothesis, product recursion [F1], and the quotient convention, ${\prod }_{k<n+1}\frac{u_k}{d_k}=\left({\prod }_{k<n}\frac{u_k}{d_k}\right)\frac{u_n}{d_n}=\frac{U}{D}\frac{u_n}{d_n}=\frac{U{u}_n}{D{d}_n}=\frac{{\prod }_{k<n+1}{u}_k}{{\prod }_{k<n+1}{d}_k}\mathrm{.}$ The equality $(U\mathrm{/}D)(u_n\mathrm{/}{d}_n)=(U{u}_n)\mathrm{/}(D{d}_n)$ follows from associativity and commutativity together with $(D{d}_n{)}^{-1}=D^{-1}{d}_n^{-1}$.

Induction [F2] applied to steps 1.1 and 1.2 proves the identity for every finite list length.

For $k\mathrm{\ne }j$, strict ordering of the nodes gives $x_j-x_k\mathrm{\ne }0$. The denominator product in $w_j$ is nonzero by [F6], so its inverse $w_j$ exists and is nonzero by [F5]. List the omitted-node indices in increasing order and put $P_j(X)={\prod }_{k\mathrm{\ne }j}(X-x_k)$; [F2] makes this a monic formal polynomial of degree $n$. For an arbitrary real $x$, apply [F7] to the real numerators $x-x_k$ and denominators $x_j-x_k$ in that list. It gives ${\mathrm{\ell }}_j(x)=P_j(x)\mathrm{/}{\prod }_{k\mathrm{\ne }j}(x_j-x_k)=w_j{P}_j(x)$, also when $n=0$ by the empty-product convention. Scale the coefficient list $(a_0,\dots ,a_n)$ of $P_j$ by $w_j$; the resulting vector has final coefficient $w_j\mathrm{\ne }0$. By [F3] and [F4] it represents a formal polynomial of degree $n$, and [F8] gives its evaluation $w_j{P}_j(x)={\mathrm{\ell }}_j(x)$ for every real $x$.

If $i=j$, each factor in ${\mathrm{\ell }}_j(x_i)$ is $d\mathrm{/}d=1$ for a nonzero difference $d=x_j-x_k$. Induction [F13] on the list length shows their product is $1$: the empty product is $1$, and appending a factor $1$ leaves it unchanged by [F12] and the field identity [F5]. This includes the empty list. If $i\mathrm{\ne }j$, the omitted-node list contains $x_i$: its index is $i$ when $i<j$ and $i-1$ when $i>j$. The corresponding quotient factor is $0$ because its numerator is $x_i-x_i=0$, its denominator is nonzero, and [F11] gives $0$ times its inverse equal to $0$. Splitting the finite product before and after that factor by [F10] writes ${\mathrm{\ell }}_j(x_i)$ as a prefix product times $0$ times a suffix product, which is $0$ by commutativity [F5] and [F11].

The product lemma [F2] applied to $x_0,\dots ,x_n$ gives a monic polynomial of degree $n+1$ evaluating to ${\omega }_n$, with degree and leading coefficient understood from the formal list [F4].

If $x$ differs from every node, each factor $x-x_j$ is nonzero by [F5], so the product lemma [F6] gives ${\omega }_n(x)\mathrm{\ne }0$.

For each $j$, let $(a_{j,0},\dots ,a_{j,n})$ be the coefficient vector of the degree-$n$ representative from step 1.1. Define $b_k={\sum }_{j<n+1}{y}_j{a}_{j,k}$ for $k<n+1$. For every real $x$, finite-sum scaling [F8], field distributivity, and double-sum interchange [F9] give ${\sum }_{k<n+1}{b}_k{x}^k={\sum }_{k<n+1}{\sum }_{j<n+1}{y}_j{a}_{j,k}{x}^k={\sum }_{j<n+1}{y}_j{\sum }_{k<n+1}{a}_{j,k}{x}^k={\sum }_{j<n+1}{y}_j{\mathrm{\ell }}_j(x)=I_{n}y(x)\mathrm{.}$ The vector $(b_0,\dots ,b_n)$ therefore gives, by [F3], a formal polynomial of degree at most $n$ evaluating to $I_{n}y$.

Put $M=m>0$. Since $x_{k+1}-x_k=1\mathrm{/}M>0$, the nodes increase from $-1$ to $1$, and $x_m=0$. If $x_{\ast }=x_k$, then $1=2k$; for $k=0$ the right side is $0$, while for $k\ge 1$ it is at least $2$, by [F8, F9]. Thus $x_{\ast }$ is not a node.

For $k\mathrm{\ne }m$, $\mid \frac{x_{\ast }-x_k}{x_m-x_k}\mid =\frac{\mathrm{\mid }\frac{1}{2}-k\mathrm{\mid }}{\mathrm{\mid }m-k\mathrm{\mid }}\mathrm{.}$ The denominator product is $(m{!}_{\mathbb{R}}{)}^2$, where $m{!}_{\mathbb{R}}={\prod }_{j=1}^{m}j$. In the numerator, the $k=0$ factor is $1\mathrm{/}2$ and the remaining factors are $k-1\mathrm{/}2$ for $1\le k\le 2m$, with $k=m$ omitted. Pairing the odd factors gives ${\prod }_{\begin{array}{c}0\le k\le 2m\\ k\mathrm{\ne }m\end{array}}\mathrm{\mid }\frac{1}{2}-k\mathrm{\mid }=\frac{(4m){!}_{\mathbb{R}}}{(2m-1){16}^m(2m){!}_{\mathbb{R}}}\mathrm{.}$ Using [F3, F4] to rewrite the factorial ratios yields the exact identity $\mathrm{\mid }{\mathrm{\ell }}_m(x_{\ast })\mathrm{\mid }=\frac{\left(\genfrac{}{}{0px}{}{4m}{2m}\right)\left(\genfrac{}{}{0px}{}{2m}{m}\right)}{(2m-1){16}^m}\mathrm{.}$

Apply [F6] in the commutative ring $\mathbb{R}$ [F7] with $u=v=1$. The sum of the $r$th binomial row is $2^r$. For $r=4m$ and $r=2m$, [F5] says the central term is largest; each coefficient is nonnegative by [F2, F9], so [F10] bounds the row sum above by $(r+1)$ times its central term. Consequently $\left(\genfrac{}{}{0px}{}{4m}{2m}\right)\ge \frac{{16}^m}{4m+1},\left(\genfrac{}{}{0px}{}{2m}{m}\right)\ge \frac{4^m}{2m+1}\mathrm{.}$

By [F6, F7], $4^m=(1+3{)}^m={\sum }_{k=0}^m\left(\genfrac{}{}{0px}{}{m}{k}\right)3^k\ge 81\left(\genfrac{}{}{0px}{}{m}{4}\right)\mathrm{.}$ Here every summand is nonnegative by [F2, F8, F9], and the inequality retains the $k=4$ term using [F10]. From [F3, F4], $\left(\genfrac{}{}{0px}{}{m}{4}\right)=m(m-1)(m-2)(m-3)\mathrm{/}24$. Since $m\ge 6$, each of these four factors is at least $m\mathrm{/}2$, so $\left(\genfrac{}{}{0px}{}{m}{4}\right)\ge m^4\mathrm{/}384$. Therefore $4^m\ge 81m^4\mathrm{/}384$.

Substituting step 1.3 in step 1.2 gives $\mathrm{\mid }{\mathrm{\ell }}_m(x_{\ast })\mathrm{\mid }\ge \frac{4^m}{(2m-1)(4m+1)(2m+1)}\ge \frac{4^m}{30m^3},$ because the three denominator factors are at most $2m$, $5m$ and $3m$, respectively.

Combining step 1.4 with step 2.1 yields $\mathrm{\mid }{\mathrm{\ell }}_m(x_{\ast })\mathrm{\mid }\ge 81m\mathrm{/}(384\cdot 30)=9m\mathrm{/}1280$, as claimed.

By [F2], choose a formal polynomial $P$ of degree at most $n$ (allowing the zero polynomial) whose evaluation $p(t):=P(t)$ equals the function $I_{n}y(t)$ for every real $t$. At node $x_i$, [F1, F2] give $P(x_i)=p(x_i)={\sum }_{j=0}^n{y}_j{\mathrm{\ell }}_j(x_i)=y_i$. Thus the formal polynomial $P$ is an interpolant.

Let $Q$ be any formal polynomial of degree at most $n$ (allowing zero) with $Q(x_i)=y_i$, and denote its evaluation by $q(t):=Q(t)$. Extend the actual coefficient lists of $P$ and $Q$ by zeros through index $n$ (using all-zero vectors for zero polynomials), obtaining vectors $(a_k)$ and $(b_k)$; these describe their evaluations $p$ and $q$, not padded formal objects. The vector $c_k=a_k-b_k$ defines by [F3] a formal polynomial $r$ of degree at most $n$; [F5] gives $r(t)=p(t)-q(t)$ for every real $t$. Since $p$ and $q$ agree at all nodes by step 1.1 and the choice of $q$, $r$ has the $n+1$ distinct roots $x_0,\dots ,x_n$. If $r$ were nonzero, [F4] would give at most $\mathrm{deg}r\le n$ roots, a contradiction. Hence $r$ is the zero formal polynomial; by [F3], every $a_k-b_k=0$. The canonical coefficient lists of $P$ and $Q$ are therefore identical (or both objects are zero), so $P=Q$, and consequently $p=q$ as evaluation functions.

This proves that the interpolant from step 1.1 is the unique formal polynomial of degree at most $n$ satisfying the node values.

Split the product for ${\omega }_n(x)$ before and after index $j$ using [F4]: it is $A(x-x_j)B$, where $A={\prod }_{k<j}(x-x_k)$ and $B={\prod }_{j<k\le n}(x-x_k)$; the omitted numerator product is $AB$. In the increasing omitted-index order of [F1], the product law [F4] gives ${\mathrm{\ell }}_j(x)=({\prod }_{k\mathrm{\ne }j}(x-x_k))({\prod }_{k\mathrm{\ne }j}(x_j-x_k{)}^{-1})$. The second product is $w_j$: multiplying it by ${\prod }_{k\mathrm{\ne }j}(x_j-x_k)$ gives the product of $1$'s, including the empty case, so it is that product's inverse. Thus ${\mathrm{\ell }}_j(x)=AB{w}_j={\omega }_n(x)w_j\mathrm{/}(x-x_j)$, using $x\mathrm{\ne }{x}_j$ to cancel the nonzero factor.

By [F1], $S(X):={\sum }_{j=0}^n{\mathrm{\ell }}_j(X)=I_n(1,\dots ,1)(X)$, so it has degree at most $n$ by [F2]. At each node $x_i$, [F3] gives $S(x_i)=1$. The constant polynomial $1$ is another degree-at-most-$n$ interpolant of these data; uniqueness in [F2] gives $S(X)=1$.

Summing the identities of step 1.1 over $j$ gives ${\omega }_n(x){\sum }_{j=0}^n{w}_j\mathrm{/}(x-x_j)={\sum }_{j=0}^n{\mathrm{\ell }}_j(x)=1$ by step 1.2. Since ${\omega }_n(x)\mathrm{\ne }0$ by [F3], the denominator sum equals $1\mathrm{/}{\omega }_n(x)$ and is nonzero by the field laws [F4].