3
$\begingroup$

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.

  • 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}$.2011-10-29

2 Answers 2

7

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.

  • 0
    @jrand I edited the answer a little. The previous proof worked only for $x \in [0,1]$; this restriction is no longer necessary.2011-10-31
5

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

  • 0
    @Didier Piau: Hi, thank you. I tried your technique and it worked.2011-10-30