Proof. Let \(I=[a,b]\). Since \(f\) is continuous on the closed bounded interval \(I\), it is uniformly continuous there, so there exists \(\delta > 0\) such that \(|f(x) - f(y)| < \varepsilon \) whenever \(x, y\in I\) and \(|x - y| < \delta \). Choose \(m\in \mathbb {N}\) so large that \(h = \frac {b - a}{m} < \delta \), and divide \(I\) into the \(m\) disjoint intervals \[I_1 = [a, a+h], \qquad I_k = \bigl (a + (k-1)h,\; a + kh\bigr ] \quad (k = 2, \dots , m),\] each of length \(h\). Define \(S_{\varepsilon }(x) = f(a + kh)\) for \(x\in I_k\). Then \(S_{\varepsilon }\) is a step function. If \(x\in I_k\), then \(|x - (a+kh)|\leq h < \delta \), so \[|f(x) - S_{\varepsilon }(x)| = |f(x) - f(a + kh)| < \varepsilon .\] Since every \(x\in I\) lies in some \(I_k\), this holds for all \(x\in I\). □

Proof. Let \(I=[a,b]\) and choose \(\delta \), \(m\), \(h\) and the intervals \(I_k\) as in the previous proof. On each \(\overline {I_k} = [a + (k - 1)h, a + kh]\) let \(g_{\varepsilon }\) be the linear function joining the points \(\bigl (a + (k - 1)h, f(a + (k - 1)h)\bigr )\) and \(\bigl (a + kh, f(a + kh)\bigr )\). Adjacent pieces agree at their common end point, so \(g_{\varepsilon }\) is a continuous piecewise linear function on \(I\).

Let \(x\in I_k\). Since \(g_{\varepsilon }\) is linear on \(\overline {I_k}\), its value \(g_{\varepsilon }(x)\) lies between the two end values \(f(a + (k - 1)h)\) and \(f(a + kh)\). Each of these is within \(\varepsilon \) of \(f(x)\), because both end points are within \(h<\delta \) of \(x\). A number lying between two numbers that are each within \(\varepsilon \) of \(f(x)\) is itself within \(\varepsilon \) of \(f(x)\). Hence \(|f(x) - g_{\varepsilon }(x)| < \varepsilon \) for all \(x\in I\). □

Proof. First suppose \(I = [0,1]\). For \(n\in \mathbb {N}\) and \(0\leq k\leq n\) write \(p_{n,k}(x) = \binom {n}{k}x^k(1-x)^{n-k}\), and define the Bernstein polynomial \[B_n(x) = \sum _{k=0}^n f\!\left (\frac {k}{n}\right ) p_{n,k}(x).\] By the binomial theorem, \(\sum _{k=0}^n p_{n,k}(x) = (x + (1-x))^n = 1\). Differentiating \((x+y)^n = \sum _k\binom {n}{k}x^ky^{n-k}\) once and twice with respect to \(x\), multiplying by \(x\) and \(x^2\), and then putting \(y = 1-x\), gives \[\sum _{k=0}^n k\,p_{n,k}(x) = nx, \qquad \sum _{k=0}^n k(k-1)\,p_{n,k}(x) = n(n-1)x^2 .\] Combining the three identities, \[\sum _{k=0}^n (k - nx)^2 p_{n,k}(x) = n(n-1)x^2 + nx - 2nx\cdot nx + n^2x^2 = nx(1-x) \leq \frac {n}{4}.\]

Now let \(\varepsilon >0\). Since \(f\) is continuous on \([0,1]\), it is bounded, say \(|f|\leq M\), and uniformly continuous, so there is a \(\delta >0\) with \(|f(x) - f(y)|<\frac {\varepsilon }{2}\) whenever \(|x - y|<\delta \). Fix \(x\in [0,1]\). Using \(\sum _k p_{n,k}(x) = 1\), \[|f(x) - B_n(x)| \leq \sum _{k=0}^n \left |f(x) - f\!\left (\frac {k}{n}\right )\right | p_{n,k}(x).\] Split the sum according to whether \(\left |\frac {k}{n} - x\right | < \delta \). The terms with \(\left |\frac {k}{n} - x\right | < \delta \) contribute less than \(\frac {\varepsilon }{2}\sum _k p_{n,k}(x) = \frac {\varepsilon }{2}\). In the remaining terms \(|f(x) - f(\frac {k}{n})|\leq 2M\) and \(1\leq \frac {(k-nx)^2}{n^2\delta ^2}\), so they contribute at most \[2M\sum _{k=0}^n \frac {(k-nx)^2}{n^2\delta ^2}\,p_{n,k}(x) \leq \frac {2M}{n^2\delta ^2}\cdot \frac {n}{4} = \frac {M}{2n\delta ^2}.\] Choose \(n > \frac {M}{\varepsilon \delta ^2}\). Then \(\frac {M}{2n\delta ^2}<\frac {\varepsilon }{2}\), so \(|f(x) - B_n(x)|<\varepsilon \), and since \(n\) does not depend on \(x\), this holds for all \(x\in [0,1]\). Take \(P_\varepsilon = B_n\).

For a general interval \([a,b]\), apply this to the continuous function \(\varphi (t) = f(a + (b-a)t)\) on \([0,1]\), obtaining a polynomial \(Q\) with \(|\varphi (t) - Q(t)|<\varepsilon \) on \([0,1]\). Then \(P_\varepsilon (x) = Q\!\left (\frac {x-a}{b-a}\right )\) is a polynomial and \(|f(x) - P_\varepsilon (x)|<\varepsilon \) for all \(x\in [a,b]\). □

Solution. Using the identities in the proof of the Weierstrass Approximation Theorem, \begin {align*} B_n(x) &= \sum _{k=0}^n\frac {k^2}{n^2}p_{n,k}(x) = \frac {1}{n^2}\Bigl (\sum _k k(k-1)p_{n,k}(x) + \sum _k k\,p_{n,k}(x)\Bigr )\\ &= \frac {n(n-1)x^2 + nx}{n^2} = x^2 + \frac {x(1-x)}{n}. \end {align*}

Hence \(0\leq B_n(x) - x^2 = \frac {x(1-x)}{n}\leq \frac {1}{4n}\), with equality at \(x = \frac {1}{2}\). The error is less than \(0.01\) for all \(x\) exactly when \(\frac {1}{4n}<0.01\), that is, \(n>25\). This shows the general estimate in the proof is crude but of the right kind: the error decreases like \(\frac {1}{n}\).

Solution. Since \(|x^2 - y^2|\leq 2|x-y|\) on \([0,1]\), any \(\delta \leq 0.05\) works in the proofs of this section. With \(h = \frac {1}{m}<0.05\), say \(m = 21\), the step function \(S(x) = f\left (\frac {k}{21}\right )\) on \(I_k\) satisfies \(|f - S|<0.1\).

The piecewise linear interpolant does much better than the proof suggests. On \([t, t+h]\) the chord of \(x^2\) lies above the graph by \((x-t)(t+h-x)\leq \frac {h^2}{4}\). So \(|f - g|\leq \frac {h^2}{4}\), and \(h = \frac {1}{2}\) (two pieces) already gives error at most \(\frac {1}{16}<0.1\).