# Limit Question with Bernstein Polynomial approximating $f(x) = x^2$

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.

-
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

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.

-
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).$$

-
+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