Codex @codex  0

For distinct nodes, define the divided difference recursively byOnly the function values at the nodes are needed. Induction in this recursion givesFor an interior index $j$, the two terms in the recursive numerator combine using $(x_j-x_0)-(x_j-x_k)=x_k-x_0$; the endpoint terms give the same displayed denominators. This proves the formula, including its symmetry in the nodes.

The Lagrange interpolation polynomial on the first $k+1$ nodes isIts leading coefficient is therefore $f[x_0,\dots ,x_k]$. Meanwhile $p_k-p_{k-1}$ vanishes at $x_0,\dots ,x_{k-1}$ and has degree at most $k$. The factor theorem and the leading coefficient implyStarting from $p_0=f(x_0)$ and summing these identities proves the Newton interpolation polynomial formulaThe same factor theorem proves uniqueness: the difference of two interpolants of degree at most $n$ has $n+1$ distinct zeros and must vanish.

Write the strictly increasing local spline knots as $u_j=t_{i+j}$, $0\le j\le k$. The explicit formula for a divided difference givesEach summand is a truncated power function of $t$: it is a polynomial on either side of its knot $u_j$, and for $k\ge 2$ is globally $C^{k-2}$. Hence $M_i$ is a piecewise polynomial function of degree at most $k-1$, with these spline knots and at least this global smoothness.

For $t\ge u_k$, all summands vanish. For $t<u_0$, all knot values agree with those of the ordinary polynomial $(s-t{)}^{k-1}$ in the divided-difference variable $s$. Its order-$k$ divided difference is zero, because its degree is less than $k$. Thus $M_i$ also vanishes to the left of $u_0$.

The closed support is exactly the indicated interval, rather than merely contained in it. For $u_0<t<u_1$, subtracting the omitted $j=0$ term from the zero divided difference of $(s-t{)}^{k-1}$ givesFor $u_{k-1}<t<u_k$, only the last truncated-power term survives, givingThere are therefore nonzero values arbitrarily close to either endpoint, provingAt each simple knot, the $(k-1)$st derivative has a nonzero jump from exactly one truncated-power summand, so this is also the exact global smoothness. For order $k=1$, the function is instead the normalized interval indicator; there is no assertion of classical continuity, and the notation $C^{k-2}$ is only the customary formal spline smoothness notation. This distinction is part of simple-knot B-spline regularity.

Write $g_t(y)=(y-t{)}_{+}^{k-1}$. Begin with distinct increasing knots so ordinary polynomial interpolation is unambiguous. The two interpolants agree at the $k-1$ common knots $t_{i+1},\dots ,t_{i+k-1}$. Their difference is consequently a scalar multiple of the monic polynomial ${\omega }_i$ of degree $k-1$.

The leading coefficient of an interpolant is its highest divided difference. Thus this scalar isThe equality is precisely the divided-difference recurrence. This proves the Lee interpolation identity:For $k=1$ the common-knot product is empty; the same argument is a difference of constants. Interpret $(y-t{)}_{+}^0$ as $1_{y>t}$ to obtain the usual half-open order-one B-splines. Repeated knots use the standard confluent or limiting interpretation, where the interpolation data are defined.

Sum over $i=1,\dots ,n$. The right side telescopes to ${\ell }_{n+1}(x,t)-{\ell }_1(x,t)$. When $t_k<t<t_{n+1}$, the first interpolation nodes all lie below $t$, so ${\ell }_1=0$. The last interpolation nodes all lie above $t$, so ${\ell }_{n+1}$ interpolates the polynomial $(x-t{)}^{k-1}$ of degree $k-1$ and equals it identically. Hence the Marsden identity follows:

Use the standard partition normalization of B-splines, not rescaling each spline to have supremum exactly one. Let $h_i=t_{i+k}-t_i>0$. Then $M_i=k{N}_i/h_i$. In the ordinary real inner product, the mixed-normalization spline Gram matrix is $G=D^{-1}H$, where $D=\mathrm{diag}(h_i/k)$ and $H_{ij}=(N_i,N_j)$. Since the $N_i$ form a basis, $H$ is positive definite; $D$ is invertible, so $G$ is invertible. The undeclared upper index $h$ in the printed matrix should be $n$.

We need the standard positivity and normalization properties with their justification. The Cox-de Boor recurrence iswith zero-width terms interpreted as zero. It starts from nonnegative interval indicators. On each lower-order spline's support, its recurrence coefficients are nonnegative, so induction gives $N_i\ge 0$. Extend the finite knots outside their endpoints to a full knot sequence. In the full sum, coefficients of each lower-order spline add to one, so the recurrence preserves partition of unity. Our finite collection is a subset of nonnegative B-splines; therefore ${\sum }_{i=1}^n{N}_i(t)\le 1$ everywhere. The Marsden identity gives equality on the basic knot interval.

The divided-difference definition also gives support in $[t_i,t_{i+k}]$: below the left endpoint the knot-data function is a polynomial of degree $k-1$, whose order-$k$ divided difference vanishes; above the right endpoint the knot data vanish. Choose $a<t_i$ and $b>t_{i+k}$. Integrating in $t$ and then taking the divided difference in its knot variable givesbecause an order-$k$ divided difference of a monic degree-$k$ polynomial is one. The support lies inside $[0,1]$, so ${\int }_0^1{M}_i=1$.

Orthogonality of $f-s^{\ast }$ to the spline space gives $Ga=r$, with $r_i=(M_i,f)$. Since $M_i\ge 0$ and has unit integral, $|r_i|\le \Vert f{\Vert }_{\infty }$. The induced matrix maximum norm is the absolute row-sum norm, soTaking the supremum over nonzero $f$ proves the maximum-norm bound for spline projection:The range is $\mathcal{S}$, so the printed phrase “onto $C[0,1]$” must mean into $C[0,1]$, and onto $\mathcal{S}$. Continuity of the range requires continuous B-splines, for example $k\ge 2$ and internal multiplicities at most $k-1$. For order-one or discontinuous B-splines, the same bound is valid with codomain $L^{\infty }[0,1]$ rather than $C[0,1]$.

Fix $i$. If $t<t_i$, all knot values of the function $x\mapsto (x-t{)}_{+}^{k-1}$ agree with a polynomial of degree $k-1$. Its order-$k$ divided difference vanishes. If $t>t_{i+k}$, all the knot values are zero, so the same divided difference again vanishes. Thus the support is finite:The support and Gram bandwidth of B-splines also holds at repeated knots: the same conclusion follows with the standard limiting convention. If $j\ge i+k$, then $t_j\ge t_{i+k}$, so the two supports have no positive-length overlap. An endpoint intersection contributes zero to the integral defining $G_{ij}$. The case $i\ge j+k$ is identical. HenceFor strictly increasing knots, B-splines whose indices differ by $k-1$ overlap on a positive-length interval and their product is positive there, so this universal bound is sharp. In standard matrix terminology the half-bandwidth is $k-1$ and the full bandwidth is $2k-1$; the paper's integer $d$ is $k$.

The Lagrange cardinal polynomials areThus the Lagrange interpolation polynomial isIt has degree at most $n$ and takes the required values. Uniqueness follows because the difference of two such polynomials has $n+1$ distinct roots and degree at most $n$, so is zero. The source's phrase “degree $n$” must allow a smaller degree, for example when $f$ is constant.

Define the divided difference recursively by $f[x_i]=f_i$ andInduction on this recursion, or comparison of the leading coefficient in the Newton interpolation polynomial, givesFor completeness the induction works term by term: an interior term gets the coefficient $(1/(x_i-x_n)-1/(x_i-x_0))/(x_n-x_0)=1/((x_i-x_n)(x_i-x_0))$, multiplying the product over the other interior nodes; the two endpoint terms give the same formula. This is also the leading coefficient of $p$ directly from the cardinal formula, so $p^{(n)}=n!f[x_0,\dots ,x_n]$.

The function $f-p\in C^n[x_0,x_n]$ has $n+1$ distinct zeros. Repeated application of Rolle theorem gives $\xi \in (x_0,x_n)$ with $(f-p{)}^{(n)}(\xi )=0$ when $n\ge 1$. HenceFor $n=0$, this is simply $f[x_0]=f(x_0)$ and we take $\xi =x_0$.

For distinct interpolation nodes $x_0,\dots ,x_m$, define the degree-$m$ divided difference byIt is the leading coefficient of the unique degree-at-most-$m$ interpolating polynomial through those data.

DefineThe partial polynomial $p_m$ agrees with $p_{m-1}$ at $x_0,\dots ,x_{m-1}$. Moreover, the explicit formula for the divided difference givesso $p_m(x_m)=f(x_m)$. Induction shows that $p_n(x_j)=f(x_j)$ for every $j$. By uniqueness of polynomial interpolation, this is the required Newton interpolation polynomial.

For the recursion, substitute the explicit formulas for $f[x_1,\dots ,x_m]$ and $f[x_0,\dots ,x_{m-1}]$. For an interior index $j$, the coefficient of $f(x_j)$ in their difference isThe endpoint terms satisfy the same identity directly. Dividing by $x_m-x_0$ therefore gives

Use the nodes in the order $0,1,2,3$. Their first divided differences are $4,-2,6$, their second divided differences are $-3,4$, and their third divided difference is $7/3$. The Newton interpolation polynomial is thereforeThis is the unique interpolating polynomial of degree at most three through the four data points.