Proofs
This appendix proves the lemmas, propositions, theorems and corollaries stated in the chapters, in the order they appear. Throughout, \(b_{i,n}\) is the Bernstein polynomial of Bernstein polynomials and \(B\) the Bézier curve of Bézier curve, of degree \(n\) with control points \(P_0, \ldots, P_n\). Where a result is also proved in the literature, the chapter names the source; the proofs here are written out so that the manual does not depend on a particular edition of a book.
The Bernstein basis and evaluation
Proof
First identity. We distinguish the position of \(j\). - If \(j < 0\) or \(j > n\), all three coefficients vanish, since \(j > n\) implies \(j - 1 > n - 1\). - If \(j = 0\), the left side is \(1 + 0 = 1 = \binom{n}{0}\). - If \(j = n\), it is \(0 + 1 = 1 = \binom{n}{n}\). - If \(1 \le j \le n - 1\), put the terms over the common denominator \(j! (n - j)!\):
Second identity. If \(i < 1\) or \(i > n\) both sides vanish: for \(i = 0\) the left side has the factor \(i = 0\) and \(\binom{n-1}{-1} = 0\); for \(i < 0\) and \(i > n\) every coefficient is zero. If \(1 \le i \le n\),
Proof
The space \(\Pi_n\) of real polynomials of degree at most \(n\) has dimension \(n + 1\), with basis \(1, t, \ldots, t^n\). The \(n + 1\) polynomials \(b_{0,n}, \ldots, b_{n,n}\) lie in \(\Pi_n\), so it suffices to show that they are linearly independent. Let \(\sum_{i=0}^n c_i b_{i,n}(t) = 0\) for all \(t\). For \(t \in (0, 1)\) divide by \((1 - t)^n > 0\) and put \(u = t / (1 - t) \in (0, \infty)\):
A polynomial in \(u\) with infinitely many roots is the zero polynomial, so \(c_i \binom{n}{i} = 0\) for every \(i\). Since \(\binom{n}{i} \ne 0\), all \(c_i = 0\).
Proof
For \(t \in [0, 1]\) both \(t\) and \(1 - t\) are non-negative, hence so is every \(b_{i,n}(t)\). By the binomial theorem,
Proof
With the convention \(0^0 = 1\), \(b_{i,n}(0) = \binom{n}{i} 0^i\) equals \(1\) for \(i = 0\) and \(0\) for \(i \ge 1\). Likewise \(b_{i,n}(1) = \binom{n}{i} 0^{n-i}\) equals \(1\) for \(i = n\) and \(0\) for \(i < n\). Hence \(B(0) = \sum_i b_{i,n}(0) P_i = P_0\) and \(B(1) = \sum_i b_{i,n}(1) P_i = P_n\).
Proof
By Partition of unity, \(B(t) = \sum_i \lambda_i P_i\) with \(\lambda_i = b_{i,n}(t) \ge 0\) and \(\sum_i \lambda_i = 1\). A convex combination of points lies in their convex hull by definition.
Proof
By linearity of \(M\) and Partition of unity, which gives \(\sum_i b_{i,n}(t) = 1\),
Proof
By induction on \(r\). For \(r = 0\), \(P_i^{(0)} = P_i = b_{0,0}(t) P_i\). Assume the claim holds for \(r - 1\), for every admissible \(i\). For \(0 \le i \le n - r\) both \(i\) and \(i + 1\) are admissible for \(r - 1\), so
where the second sum was re-indexed by \(j + 1 \to j\), and the convention \(b_{-1,r-1} = b_{r,r-1} = 0\) covers the two ends. For \(0 \le j \le r\) the bracket is
by Binomial identities. For \(r = n\) and \(i = 0\) the claim reads \(P_0^{(n)} = B(t)\).
Proof
Multiply \(b_{i,n}(t)\) by \(1 = (1 - t) + t\):
Since \(\binom{n+1}{i} = (n + 1) / (n + 1 - i) \cdot \binom{n}{i}\) and \(\binom{n+1}{i+1} = (n + 1) / (i + 1) \cdot \binom{n}{i}\) for \(0 \le i \le n\),
The first term is therefore \((n + 1 - i) / (n + 1)\) times \(b_{i,n+1}(t)\) and the second \((i + 1) / (n + 1)\) times \(b_{i+1,n+1}(t)\).
Proof
where \(k = i\) in the first sum and \(k = i + 1\) in the second. The first sum may be extended to \(k = n + 1\), since its coefficient vanishes there, and the second to \(k = 0\), for the same reason. Collecting the coefficient of \(b_{k,n+1}(t)\) gives \(Q_k\).
Derivatives, reversal and subdivision
Proof
Derivative of the Bernstein polynomials
We treat the possible values of \(i\) in turn. - If \(i < 0\) or \(i > n\), then \(b_{i,n} = 0\) and both terms on the right vanish. - If \(i = 0\), \(b_{0,n}(t) = (1 - t)^n\) has derivative \(-n (1 - t)^{n-1} = n [b_{-1,n-1}(t) - b_{0,n-1}(t)]\). - If \(i = n\), \(b_{n,n}(t) = t^n\) has derivative \(n t^{n-1} = n [b_{n-1,n-1}(t) - b_{n,n-1}(t)]\). - If \(1 \le i \le n - 1\), the product rule gives
By Binomial identities, \(i \binom{n}{i} = n \binom{n-1}{i-1}\), and, applying it to \(n - i\) and using \(\binom{n}{n-i} = \binom{n}{i}\), \((n - i) \binom{n}{i} = n \binom{n-1}{i}\). The two terms are therefore \(n b_{i-1,n-1}(t)\) and \(n b_{i,n-1}(t)\).
Proof
By linearity and Derivative of the Bernstein polynomials,
In the first sum the term \(i = 0\) vanishes; substituting \(k = i - 1\) gives \(\sum_{k=0}^{n-1} b_{k,n-1}(t) P_{k+1}\). In the second the term \(i = n\) vanishes. Hence
Proof
By Hodograph, \(B'\) is the Bézier curve of degree \(n - 1\) with control points \(D_k = n(P_{k+1} - P_k)\), \(k = 0, \ldots, n - 1\). By Endpoints applied to it, \(B'(0) = D_0\) and \(B'(1) = D_{n-1}\).
Proof
For \(0 \le i \le n\), since \(\binom{n}{i} = \binom{n}{n-i}\),
For other \(i\) both sides are zero.
Proof
Re-index with \(j = n - i\) and use Symmetry:
Proof
Left part. Since \(1 - c s = (1 - s) + s (1 - c)\), the binomial theorem gives
Substitute \(j = i + k\), so that \(0 \le i \le j \le n\) and \(n - i - k = n - j\). Both \(\binom{n}{i} \binom{n-i}{j-i}\) and \(\binom{n}{j} \binom{j}{i}\) equal \(n! / (i! (j-i)! (n-j)!)\), hence
The last step uses de Casteljau with \(r = j\) and \(i = 0\): \(P_0^{(j)} = \sum_{i=0}^j b_{i,j}(c) P_i\). This is the claim for the \(L_j\).
Right part. Let \(\overline{B}\) be the curve with control points \(\overline{P}_i = P_{n-i}\), so that \(\overline{B}(u) = B(1 - u)\) by Reversal, and put \(\overline{c} = 1 - c\). The left part applied to \(\overline{B}\) gives
where, by Symmetry and the substitution \(l = j - i\),
The next-to-last equality is de Casteljau with \(r = j\) and \(i = n - j\), an admissible index since \(n - j \le n - r\). Therefore, using Symmetry once more,
Proof
Write \(a = t_0\) and \(e = t_1\), so \(0 \le a < e \le 1\). By Subdivision with \(c = e\), the left part is the Bézier curve \(u |\to B(e u)\) with control points \(L_0, \ldots, L_n\). Apply Subdivision to it with \(c' = a / e \in [0, 1)\) and keep the right part: