Prove Convex hull is Convex

Question

Let $S\subset R^n$. Prove that the convex hull of $S$ is a convex set.

By definition of convex hull we know

$$S=\{x=\lambda_1x_1+\cdots+\lambda_mx_m\mid \lambda_1,\ldots,\lambda_m\geq0,\lambda_1+\cdots+\lambda_m=1, \text{ and } x_1,\ldots,x_m\in S \} $$

Using Proof by Induction $m=1$ is trivial and $m=2$ is the definition of a convex set. To prove $m+1$ is true I force factored a $\lambda$ to result in...

Let $\lambda = \lambda_1+\cdots+\lambda_m = 1-\lambda_{m+1}$ then

$$\lambda \left(\frac{\lambda_1}{\lambda}x_1+\cdots+\frac{\lambda_m}{\lambda}x_m \right) + (1-\lambda)x_{m+1}.$$

This is a convex combination. I believe this would finish proving that the convex hull of $S$ is a convex set.

Can this be proved without using Proof by Induction?

Answer 1

If $s_1, s_2 \in \operatorname{co} S$, then there are (a finite number of) $\lambda_k(1), \lambda_k(2)$ and $x_k \in S$ such that $s_i = \sum_k \lambda_k(i) x_k$ with $\lambda_k(i) \ge 0$ and $\sum_k \lambda_k(i) = 1$.

Now choose $t \in [0,1]$ and pick $s = ts_1 + (1-t) s_2$, then $s = \sum_k (t \lambda_k(1)+ (1-t) \lambda_k(2)) x_k$ and we can see that $t \lambda_k(1)+ (1-t) \lambda_k(2) \ge 0$ and we can quickly check that $\sum_k (t \lambda_k(1)+ (1-t) \lambda_k(2)) = 1$. Hence $s \in \operatorname{co} S$.

Answer 2

Here is proof without induction.

Let $T$ be the convex hull of some arbitrary set $S \subset R^n$.

Let $x, y \in T$. Then by definition (of convex hull)

$$ x = \sum_{i=1}^k \alpha_i x_i, \, x_i \in S, \, \alpha_i \geq 0, \sum_i \alpha_i = 1 $$ and $$ y = \sum_{j=1}^l \beta_j y_j, \, y_j \in S, \, \beta_j \geq 0, \sum_j \beta_j = 1 $$

Without loss of generality, let us assume that $k \geq l$ and let us extend $y$ expression to $$ y = \sum_{j=1}^l \beta_j y_j + \sum_{j=l+1}^k \beta_j y_j $$ where $\beta_j = 0$ for $l < j \leq k$ and $y_j$ are arbitrarily chosen from $S$ for $l < j \leq k$. (if $k=l$, then no additional terms will be added to the expression of $y$).

We did this to ensure that both convex combinations have the same number of terms ($k$).

Now, choose $\theta \in [0,1]$ and consider the point $z = \theta x + (1-\theta) y$.

We have $$ z = \sum_{i=1}^k \theta \alpha_i x_i + \sum_{j=1}^k (1 - \theta) \beta_j y_j $$

This indeed is a convex combination of $2k$ points in $S$ with $x_i \in S$ and $y_j \in S$ since $$ \sum_{i=1}^k \theta \alpha_i + \sum_{j=1}^k (1 - \theta) \beta_j = \theta \sum_{i=1}^k \alpha_i + (1 - \theta) \sum_{j=1}^k \beta_j = \theta + (1 - \theta) = 1. $$

Thus, $z$ being a convex combination of points in $S$ belongs to $T$.

We have shown that for $x, y \in T$, $z$ belongs to $T$. Hence $T$ is convex.