Proof of Convex Combinations: Small Cases, Splitting Off the Last Point, Dropping a Zero Weight, Joining Two Combinations, and Membership in Convex Sets

Throughout, sums of points are formed in the commutative ring $\mathbb{R}^{n}$ as in Convex Sets in $\mathbb{R}^n$: Standing Notation (iii), a scalar multiple $cx$ being the product with the constant function $c$ (Rules for Pointwise Operations on Real-Valued Maps: a Commutative Ring, Scalar Multiples and Evaluation (iv)), so the rules for finite sums in a commutative ring apply to sums of points as well as to sums of reals; membership in $\Delta_{N}$ is unfolded by Convex Weights, the Standard Simplex, and Convex Combinations in $\mathbb{R}^n$ (i).

Proof of (i). For $t\in\mathbb{R}^{1}$ the recursion Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms (i) gives $\sum_{k=1}^{1}t_{k}=t_{1}$, so $t\in\Delta_{1}$ if and only if $t_{1}\ge0$ and $t_{1}=1$, that is, if and only if $t_{1}=1$. For such $t$, again by Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms (i),

$$\sum_{k=1}^{1}t_{k}x_{k}=t_{1}x_{1}=1x_{1}=x_{1}.$$

Proof of (ii). For $t\in\mathbb{R}^{2}$, Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms (i) gives

$$\sum_{k=1}^{2}t_{k}=t_{1}+t_{2},\qquad\sum_{k=1}^{2}t_{k}x_{k}=t_{1}x_{1}+t_{2}x_{2}.$$

Hence $t\in\Delta_{2}$ if and only if $t_{1},t_{2}\ge0$ and $t_{1}+t_{2}=1$, which holds if and only if $t=(1-s,s)$ with $s=t_{2}\in[0,1]$; substituting into the second sum gives the displayed formula.

Proof of (iii). By Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms (i),

$$1=\sum_{k=1}^{N+1}t_{k}=\sum_{k=1}^{N}t_{k}+t_{N+1},$$

so $\sum_{k=1}^{N}t_{k}=1-t_{N+1}$. A finite sum of nonnegative reals is nonnegative and bounds each of its terms (Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (vi)); hence $1-t_{N+1}\ge0$, and together with $t_{N+1}\ge0$ this gives $0\le t_{N+1}\le1$.

If $t_{N+1}=1$, then $0\le t_{k}\le\sum_{k'=1}^{N}t_{k'}=0$ for every $k\in[N]$, so every term $t_{k}x_{k}$ with $k\le N$ is $0$ and $\sum_{k=1}^{N}t_{k}x_{k}=0$ (Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (iv)). By Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms (i) we then have $z=0+1x_{N+1}=x_{N+1}$.

If $t_{N+1}<1$, then $s=1-t_{N+1}>0$, so the weights $\tau_{k}=t_{k}/s$ are nonnegative, and by Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (i)

$$\sum_{k=1}^{N}\tau_{k}=s^{-1}\sum_{k=1}^{N}t_{k}=1;$$

thus $\tau\in\Delta_{N}$. Writing $t_{k}=s\tau_{k}$ for $k\le N$, Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms (i) and Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (i), now applied in $\mathbb{R}^{n}$, give

$$z=\sum_{k=1}^{N}s\tau_{k}x_{k}+t_{N+1}x_{N+1}=s\,y+t_{N+1}x_{N+1},$$

which is the display, since $s=1-t_{N+1}$.

Proof of (iv). Apply Iterated Operations over an Interval: Extracting One Term and Reversing the Order (i), with the extracted index $j$ and the bijection $g_{j}$, twice: once to the reals $t_{k}$, and once to the points $t_{k}x_{k}$ (the addition of $\mathbb{R}^{n}$ is associative and commutative, with neutral element $0$). This gives

$$\sum_{k=1}^{N+1}t_{k}=\sum_{k=1}^{N}t_{g_{j}(k)}+t_{j},\qquad\sum_{k=1}^{N+1}t_{k}x_{k}=\sum_{k=1}^{N}t_{g_{j}(k)}x_{g_{j}(k)}+t_{j}x_{j}.$$

Since $t_{j}=0$ and $0x_{j}=0$, the first sum over $[N]$ equals $1$ and the second equals the original combination. The weights $t_{g_{j}(k)}$ are nonnegative, so they form a point of $\Delta_{N}$.

Proof of (v). The points $w_{k}$ and the weights $t_{k}$ are well defined, since by Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space (i) every $k\in[N+P]$ either lies in $[N]$ or has the form $N+j$ for exactly one $j\in[P]$. By the same splitting of indices, every $t_{k}$ is nonnegative, being $(1-\lambda)\tau_{k}$ or $\lambda\sigma_{j}$ with nonnegative factors. Splitting the sums over $[N+P]$ at $N$ by Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms (iii), for the associative addition of $\mathbb{R}$ and of $\mathbb{R}^{n}$ respectively, gives

$$\sum_{k=1}^{N+P}t_{k}=\sum_{k=1}^{N}(1-\lambda)\tau_{k}+\sum_{j=1}^{P}\lambda\sigma_{j},\qquad\sum_{k=1}^{N+P}t_{k}w_{k}=\sum_{k=1}^{N}(1-\lambda)\tau_{k}x_{k}+\sum_{j=1}^{P}\lambda\sigma_{j}x'_{j}.$$

By Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (i), the first is $(1-\lambda)\cdot1+\lambda\cdot1=1$, so $t\in\Delta_{N+P}$, and the second is the left side of the display.

Proof of (vi). We argue by induction on $N\in\mathbb{N}$, for the property that $\sum_{k=1}^{N}t_{k}x_{k}\in C$ for all $x_{1},\dots,x_{N}\in C$ and all $t\in\Delta_{N}$. For $N=1$ the combination is $x_{1}\in C$, by (i). Suppose the property holds for $N$, and let $z=\sum_{k=1}^{N+1}t_{k}x_{k}$ with $x_{1},\dots,x_{N+1}\in C$ and $t\in\Delta_{N+1}$. By (iii), either $z=x_{N+1}\in C$, or

$$z=(1-\lambda)y+\lambda x_{N+1},\qquad\lambda=t_{N+1}\in[0,1),$$

where $y$ is a convex combination of $x_{1},\dots,x_{N}$ and therefore lies in $C$ by the induction hypothesis. In the second case $z$ lies in the segment $[y,x_{N+1}]$ (Segments and Convex Subsets of $\mathbb{R}^n$ (i)), and this segment is contained in $C$ because $C$ is convex (Segments and Convex Subsets of $\mathbb{R}^n$ (ii)).