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.

I am reading Atkinson's "An Introduction to Numerical Analysis". I am trying to verify a limit on page 198 involving the Bernstein polynomial approximating $f(x) = x^2$.

The statement in the book is $\lim \limits_{n\to\infty} n \left( p_n(x) - f(x)\right) = x(1-x)$, where $p_n(x)$ is the Bernstein Polynomial and $f(x) = x^2$.

My work: $$ p_n(x) = \sum_{k=0}^n \dbinom{n}{k} f \left( \frac{k}{n}\right) x^k (1-x)^{n-k} $$

$$ p_n(x) = \sum_{k=0}^n \dbinom{n}{k} \left( \frac{k}{n}\right)^2 x^k (1-x)^{n-k}$$

$$ n\left(p_n(x) - f(x)\right) = \left(\sum_{k=0}^n \frac{(n-1)! k }{(n-k)! (k-1)!} x^k (1-x)^{n-k}\right) - nx^2$$

$$ n\left(p_n(x) - f(x)\right) = x(1-x)^{n-1} + (n-1)(2)x^2 (1-x)^{n-2} + \ldots + n (x^n) (1-x) - nx^2$$

Now, if I take the limit as $n$ goes to infinity, I run into the difficulty of the power of $x$ terms. Can I get some hints on how to proceed?

Thank you in advance for your help.

share|improve this question
2  
Use $k^2=k(k-1)+k$ and the relationships $k\binom{n}{k}=n\binom{n-1}{k-1}$ and $k(k-1)\binom nk=n(n-1)\binom{n-2}{k-2}$. –  Davide Giraudo Oct 29 '11 at 23:10

2 Answers 2

up vote 5 down vote accepted

Our approach is to cast the computation in terms of the binomial random variable $X \sim \mathrm{Bin}(n, x)$. For the moment, assume that $0 \leq x \leq 1$; we will remove this restriction shortly. We have $\newcommand{\E}{\mathop{\mathbf E}} \newcommand{\Var}{\mathop{\mathbf {Var}}}$ $$ \begin{eqnarray*} p_n(x) &=& \frac{1}{n^2} \sum_{k=0}^n k^2 \cdot \binom n k x^k (1-x)^{n-k} \\ &=& \frac{ \E [X^2] }{n^2} \\ &=& \frac{(\E X)^2 + \Var X}{n^2} \\ &=& \frac{(nx)^2 + nx(1-x)}{n^2} \\ &=& x^2 + \frac{x(1-x)}{n}. \end{eqnarray*} $$ Since the polynomials $p_n(x)$ and $x^2 + \frac{1}{n}x(1-x)$ agree on infinitely many points (the whole of the interval $[0,1]$), they are identical. That is, $p_n(x) = x^2 + \frac1n x(1-x)$ holds for all $x$, from which the result follows trivially. In fact, for the particular case of $f(x) = x^2$, the sequence $n(p_n(x) - f(x))$ happens to be the constant sequence $x(1-x)$. $\quad \Box$

This ingenious probabilistic approach towards the Weierstrass approximation theorem was introduced by Sergei Bernstein (hence the name Bernstein polynomial). I learnt it from The Probabilistic Method of Alon and Spencer.

EDIT: My first proof worked only for $0 \leq x \leq 1$. The remaining cases are now handled by a simple observation.

share|improve this answer
    
Hi, thank you. I recognized the binomial random variable when the Bernstein Polynomial was introduced, but did not realize it could be used to answer this particular question. –  jrand Oct 30 '11 at 13:23
    
@jrand I edited the answer a little. The previous proof worked only for $x \in [0,1]$; this restriction is no longer necessary. –  Srivatsan Oct 31 '11 at 1:51

To me, the probabilistic proof explained by @Srivatsan is the most interesting one. However, a purely algebraic proof is available, based on @Davide's hint. One begins with two easy facts: $$ {n\choose k}k=n{n-1\choose k-1},\qquad {n\choose k}k(k-1)=n(n-1){n-2\choose k-2}. $$ Since $k^2=k(k-1)+k$, this yields the decomposition $$ n^2p_n(x)=\sum\limits_{k=0}^n{n\choose k}k^2x^k(1-x)^{n-k}=u_n(x)+v_n(x), $$ with $$ u_n(x)=\sum\limits_{k=2}^n{n\choose k}k(k-1)x^k(1-x)^{n-k},\quad v_n(x)=\sum\limits_{k=1}^n{n\choose k}kx^k(1-x)^{n-k}. $$ The two easy facts above allow to compute $u_n(x)$ and $v_n(x)$. One gets $$ u_n(x)=\sum\limits_{k=2}^nn(n-1){n-2\choose k-2}x^2x^{k-2}(1-x)^{(n-2)-(k-2)}, $$ hence $$ u_n(x)=n(n-1)x^2\sum\limits_{k=0}^{n-2}{n-2\choose k}x^{k}(1-x)^{(n-2)-k}=n(n-1)x^2, $$ and $$ v_n(x)=\sum\limits_{k=1}^nn{n-1\choose k-1}xx^{k-1}(1-x)^{(n-1)-(k-1)}, $$ hence $$ v_n(x)=nx\sum\limits_{k=0}^{n-1}{n-1\choose k}x^{k}(1-x)^{(n-1)-k}=nx. $$ One used twice the third easy fact that, for every $m\geqslant0$, $$ \sum\limits_{k=0}^m{m\choose k}x^{k}(1-x)^{m-k}=(x+(1-x))^m=1. $$ Finally, $$ np_n(x)=(n-1)x^2+x=nf(x)+x(1-x). $$

share|improve this answer
    
+1 for the (systematic) algebraic approach. –  Srivatsan Oct 30 '11 at 3:08
    
@Didier Piau: Hi, thank you. I tried your technique and it worked. –  jrand Oct 30 '11 at 13:24

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.