Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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}

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.