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: https://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.
 A: 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}
A: Let $c_0, \ldots, c_n$ be given numbers, and define the polynomial function
$$
\phi(t) = \sum_{i=0}^n c_i B^n_i(t)
$$
where $B^n_i(t)$ is the $i$-th Bernstein polynomial of degree $n$. You can think of $\phi$ as a real-valued Bezier curve, if that helps. It is well known (and easy to show by direct calculation) that
$$
\phi'(t) = n\sum_{i=0}^{n-1} \Delta c_i B^{n-1}_i(t)
$$
where $\Delta c_i$ denotes the forward difference $c_{i+1} - c_i$. Arguing inductively, we can generalise this to get a formula (also well known) for the $r$-th derivative
for $r = 1,2,\ldots,n$ :
$$
\phi^{(r)}(t) = \frac{n!}{(n-r)!}\sum_{i=0}^{n-r} \Delta^{r} c_i B^{n-r}_i(t)
$$
If we apply this to the case where $f$ is some given function, and $c_i = f\left(\frac{i}{n}\right)$, then we have $\phi = \mathfrak{B}_f$.  If $f$ is a polynomial of degree $m$, where $m < n$, then we have $\Delta^{r} c_i = 0$ for $r > m$. Therefore, using the formula above, we see that the $r$-th derivative $\phi^{(r)}$ is zero for $r>m$, which means that $\phi$ (i.e. $\mathfrak{B}_f$) must have degree $m$.
This result appears as an exercise in section 2.1 of the book "Bezier and B-Spline Techniques" by Prautzsch, Boehm and Paluszny. 
