# Prove Convex hull is Convex

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?

• You only have proved that $\sum_i \lambda_i x_i\in S$ if $S$ is convex. You should take $u,v$ from the convex hull of $S$ and look what happens to $(1-\lambda) u + \lambda v$ Apr 18, 2017 at 17:55
• I am not sure what it means to take $u$ from the convex hull of $S$? would that imply setting $u=\lambda_1u_1+...+\lambda_mu_m$ ?@user251257 Apr 18, 2017 at 18:15
• yes, and the same to $v$. Notice that both sums may have different number of summands (which is not that important) Apr 18, 2017 at 18:24

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

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.