# How come the Bernstein operator creates a polynomial of the same degree as its input function?

This is a copy of the following question on the Computer Science Stack Exchange: http://cs.stackexchange.com/questions/11655/how-come-the-bernstein-operator-creates-a-polynomial-of-the-same-degree-as-its-i

The original answer left me a bit puzzled, so I tried finding a way myself.

I read that the Bernstein operator

$$\mathfrak{B}_f(t) = \sum_{i=0}^n f\left(\frac{i}{n}\right) \; B^n_i(t)$$

applied to a polynomial $f(x)$ of degree $m \leq n$ with the Bernstein polynomial

$$B^n_i(t) = \binom{n}{i} \; t^i \; (1-t)^{n-i}$$

returns a new polynomial also of degree $m$. In other words, the Bernstein operator does not increase its degree when applied to $f$.

How is this possible? Since we're only sampling $f$ at a certain interval, wouldn't the original degree of $f$ become irrelevant? How can the degree of the result be smaller than $n$, since we will have at least one $t^n$ in the expression resulting from one of the Bernstein polynomials?

I've done some more research, and I've been able to change the expression as such:

$$f(x) = \sum_{j=0}^m c_j \cdot x^j$$ $$\mathfrak{B}_f(t) = \sum_{j=0}^m c_j \left[ \sum_{i=0}^m \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} + \sum_{i=0}^{n-m} \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} \right]$$

Now all that is left to do is to show that

$$\sum_{j=0}^m \sum_{i=0}^m \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} \neq 0$$

and

$$\sum_{j=0}^m \sum_{i=0}^{n-m} \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} = 0$$

However, I am afraid my math skills end here. I have no idea how to proceed.

-

You can do it with a lot of tedious manipulation.

Let $f(x) = x^m$, $m\le n$, and $\phi = {\cal B}(f)$. Then (expanding the $x^i(1-x)^{n-i}$ terms as well): \begin{eqnarray} \phi(x) &=& \frac{1}{n^m} \sum_{i=0}^n \sum_{j=0}^{n-i} i^m \binom{n}{i} \binom{n-i}{j} x^i (-x)^j \\ &=& \frac{1}{n^m} \sum_{(i,j) \in {\cal I}} i^m \binom{n}{i} \binom{n-i}{j} (-1)^j x^{i+j} \end{eqnarray} where ${\cal I} = \{ (i,j) | i=0,...,n, \ \ j=0,...,i \}$. Noting that we can write ${\cal I} = \{ (l,k-l) | k=0,...,n, \ \ l=0,...,k \}$, we have

\begin{eqnarray} \phi(x) = \frac{1}{n^m} \sum_{k=0}^n \sum_{l=0}^k l^m \binom{n}{l} \binom{n-l}{k-l} (-1)^{k-l} x^k \end{eqnarray} Now notice that $\binom{n}{l} \binom{n-l}{k-l} = \binom{n}{k} \binom{k}{l}$, which gives (along with the fact that $(-1)^{-l} = (-1)^l$):

\begin{eqnarray} \phi(x) &=& \frac{1}{n^m} \sum_{k=0}^n \sum_{l=0}^k l^m \binom{n}{k} \binom{k}{l} (-1)^{k-l} x^k \\ &=& \frac{1}{n^m} \sum_{k=0}^n \binom{n}{k} (-1)^k x^k \ \left( \sum_{l=0}^k l^m \binom{k}{l} (-1)^{l} \right) \end{eqnarray} Let $\beta_k = \sum_{l=0}^k l^m \binom{k}{l} (-1)^{l}$. We want to show that $\beta_k = 0$ for $k>m$.

(This is the main 'trick' in the proof.) Choose $k>m$, let $p(x) = (x-1)^k$ and define the linear operator $(Lf)(x) = x \frac{df(x)}{dx}$. Omitting the tedious details, we have that the polynomial $x-1$ divides $L^m p$ (ie, the operator $L$ applied $m$ times to $p$), and hence $(L^m p) (1) = 0$. Furthermore note that $L^m (t \mapsto t^l)(x) = l^m x^l$, which gives \begin{eqnarray} (L^m p) (1) &=& 0 \\ &=& L^m(t \mapsto (t-1)^k)(1) \\ &=& L^m \left(t \mapsto \sum_{l=0}^k \binom{k}{l} (-1)^{k-l} t^l \right)(1)\\ &=& \sum_{l=0}^k \binom{k}{l} (-1)^{k-l} L^m( t \mapsto t^l )(1) \\ &=& \sum_{l=0}^k \binom{k}{l} (-1)^{k-l} l^m \\ &=& (-1)^k \sum_{l=0}^k \binom{k}{l} (-1)^{l} l^m \\ & = & (-1)^k \beta_k \end{eqnarray}

-
Thanks, this really helped me. Thanks a lot for the extensive and detailed answer. I'll upvote it once I get enough rep – robrene May 1 '13 at 10:46
You are welcome, glad to be able to help; don't worry about upvoting! – copper.hat May 1 '13 at 13:59