Why Do Normalized B-Splines Always Sum to One?

[mathmari]

Hey! :giggle:

Let $N_j$, $j=-k,\ldots , m-1$ the normalized B-splines of the set of nodes $x_0, \ldots , x_m$ of degree $k$.

Show that $$\sum_{j=-k}^{m-1}N_j(x)=1 \ \text{ for all } x\in [x_0, x_m]$$

A formula with divided differences is
\begin{align*}&N_j(x)=(x_{j+k+1}-x_j)B_j(x) \\& \text{ with } \ B_j=(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}] =\frac{(\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]}{x_{j+k+1}-x_j}\end{align*} where $(x)_+^k=\begin{cases}x^k & \text{ if } x\geq 0 \\ 0 & \text{ if } x<0\end{cases}$.

It holds that $B_j=(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]=f_x[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]$ with $f_x(y)=(y-x)_+^k$, so is this the function for the divided difference? :unsure:

Then we have \begin{align*}\sum_{j=-k}^{m-1}N_j(x)&=\sum_{j=-k}^{m-1}(x_{j+k+1}-x_j)B_j(x)\\ & =\sum_{j=-k}^{m-1}(x_{j+k+1}-x_j)\frac{(\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]}{x_{j+k+1}-x_j}\\ & =\sum_{j=-k}^{m-1}\left ((\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]\right ) \\ & = (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}] \\ & = (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-0[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}] \\ & =1-0 \\ & =1\end{align*}
I haven't understood the part from the 4th equality.
Why is the sum equal to the last term minus the first term? :unsure:
How do we get the zero and how do we get the one? :unsure:

 

[I like Serena]

Why is the sum equal to the last term minus the first term?

Hey mathmari!

It's called a telescoping series.
Consider $$\sum_{i=0}^{N-1} (a_{i+1}-a_i) = (a_1-a_0) + (a_2-a_1)+\ldots +(a_N - a_{N-1}) = a_N-a_0$$

How do we get the zero and how do we get the one?

What does $(\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]$ mean? :unsure:

As for the zero, I can already guess that we get something like $(x_0-x)_+^k$ and for all $x$ in $[x_0,x_m]$ we have that $x_0-x\le 0$, so that $(x_0-x)_+^k=0$.

 

[mathmari]

It's called a telescoping series.
Consider $$\sum_{i=0}^{N-1} (a_{i+1}-a_i) = (a_1-a_0) + (a_2-a_1)+\ldots +(a_N - a_{N-1}) = a_N-a_0$$

We have that
\begin{align*} \sum_{j=-k}^{m-1}&\left ((\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]\right )\\ & =(\cdot -x)_+^k[x_{-k+1}x_{-k+2}\ldots x_{1}]-(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]+(\cdot -x)_+^k[x_{-k+2}x_{-k+3}\ldots x_{2}]-(\cdot -x)_+^k[x_{-k+1}x_{-k+2}x_{-k+3}\ldots x_{1}] +\ldots \\ & +\ldots
(\cdot -x)_+^k[x_{m-1}x_{m}\ldots x_{m+k-1}]-(\cdot -x)_+^k[x_{m-2}x_{m-1}x_{m}\ldots x_{m+k-2}]
+(\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-(\cdot -x)_+^k[x_{m-1}x_{m}x_{m+1}\ldots x_{m+k-1}] \\ & = (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]\end{align*}

(Malthe)

What does $(\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]$ mean? :unsure:

As for the zero, I can already guess that we get something like $(x_0-x)_+^k$ and for all $x$ in $[x_0,x_m]$ we have that $x_0-x\le 0$, so that $(x_0-x)_+^k=0$.

Since we have that $
B_j=(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]=f_x[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]
$ with $
f_x(y)=(y-x)_+^k
$ it must be the difference you are referring to.

So do we have that $$(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]=([x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]-x)_+^k$$ or how do we write this? I understand what you say that it is zero because it is negative, but why is the other one equal to $1$ ?

:unsure:

 

[I like Serena]

So do we have that $$(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]=([x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]-x)_+^k$$ or how do we write this?

That does not look right to me.
It does not make sense that we would subtract $x$ from a product of $x_i$'s. The "dimensions" don't match.
So I think something else is intended. Something where we process the $x_i$ one by one or something like that.
Once we know what it is, we can probably understand how it evaluates to $1$.

 

[mathmari]

That does not look right to me.
It does not make sense that we would subtract $x$ from a product of $x_i$'s. The "dimensions" don't match.
So I think something else is intended. Something where we process the $x_i$ one by one or something like that.
Once we know what it is, we can probably understand how it evaluates to $1$.

Here in Wikipedia it says that it is the n-th divided difference, but I haven't really understood that. :unsure:

 

[I like Serena]

Here in Wikipedia it says that it is the n-th divided difference, but I haven't really understood that. :unsure:

The mean value theorem for divided differences says:

For any $n + 1$ pairwise distinct points $x_0$, ..., $x_n$ in the domain of an $n$-times differentiable function $f$ there exists an interior point​

$$\xi \in (\min\{x_0,\dots,x_n\},\max\{x_0,\dots,x_n\})$$​

where the $n$th derivative of $f$ equals $n!$ times the $n$th divided difference at these points:​

$$f[x_0,\dots,x_n] = \frac{f^{(n)}(\xi)}{n!}.$$​

In our case we have $x\in[x_0,x_m]$ and:
\[ (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}] =\frac{\left((\cdot -x)_+^k\right)^{(k)}(\xi)}{k!} =\begin{cases}\frac{\left((\cdot -x)^k\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x>0\\ \frac{\left(0\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x< 0 \end{cases} =\begin{cases}1 &\text{if }\xi-x>0\\ 0 &\text{if }\xi-x< 0 \end{cases} \]
Since $\xi$ must be between $x_{m},x_{m+1},\ldots, x_{m+k}$, it follows that $\xi-x>0$.

For the zero case, $\xi$ must be betweeen $x_{-k},\ldots,x_0$, so $\xi-x<0$.

 

[mathmari]

In our case we have $x\in[x_0,x_m]$ and:
\[ (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}] =\frac{\left((\cdot -x)_+^k\right)^{(k)}(\xi)}{k!} =\begin{cases}\frac{\left((\cdot -x)^k\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x>0\\ \frac{\left(0\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x< 0 \end{cases} =\begin{cases}1 &\text{if }\xi-x>0\\ 0 &\text{if }\xi-x< 0 \end{cases} \]
Since $\xi$ must be between $x_{m},x_{m+1},\ldots, x_{m+k}$, it follows that $\xi-x>0$.

For the zero case, $\xi$ must be betweeen $x_{-k},\ldots,x_0$, so $\xi-x<0$.

I haven't really understood how we get the $1$ in the case $\xi-x>0$ :unsure:

 

[I like Serena]

I haven't really understood how we get the $1$ in the case $\xi-x>0$

Consider the function $f: \cdot \mapsto (\cdot - x)^k$.
Note that this is not a function of $x$. Instead it's a function of the unspecified $\cdot$.
So we have for instance $f(y) = (y-x)^k$, which is a function of $y$ and we treat $x$ as a constant.

If we take the derivative of $f$, we get $f'(y)=k(y-x)^{k-1}$.
Repeat for a total of $k$ times, and we get $f^{(k)}(y)=k! (y-x)^0=k!$.
Now we substitute $\xi$ for $y$, but there is no $y$ anymore, so nothing happens.

We actually have $(y-x)_+^k$ in the formula, which we evaluate for $y-x>0$, so our result is for the case that $\xi -x>0$.
Finally we divide $f^{(k)}(\xi)=k!$ by $k!$ to arrive at $1$.

 

[mathmari]

Consider the function $f: \cdot \mapsto (\cdot - x)^k$.
Note that this is not a function of $x$. Instead it's a function of the unspecified $\cdot$.
So we have for instance $f(y) = (y-x)^k$, which is a function of $y$ and we treat $x$ as a constant.

If we take the derivative of $f$, we get $f'(y)=k(y-x)^{k-1}$.
Repeat for a total of $k$ times, and we get $f^{(k)}(y)=k! (y-x)^0=k!$.
Now we substitute $\xi$ for $y$, but there is no $y$ anymore, so nothing happens.

We actually have $(y-x)_+^k$ in the formula, which we evaluate for $y-x>0$, so our result is for the case that $\xi -x>0$.
Finally we divide $f^{(k)}(\xi)=k!$ by $k!$ to arrive at $1$.

Now it is clear to me! Thanks for explaining! (Sun)