# Convex Set Proof

Let $\{p_1, \ldots, p_k\}$ be a set of $k$ elements in the set $\mathbb R^n$.

Let $\displaystyle C = \left\{ \sum_{i=1}^k a_i p_i: \sum_{i=1}^k a_i = 1 \mbox{ and }a_1, \ldots, a_k \geq 0\right\}$.

How can I show that $C$ is a convex set?

Thanks!

-

A set $C$ is convex if and only if the line segment joining two points in $C$ lies completely within $C$. Now let $x=\sum_{i=1}^ka_ip_i$ and $y=\sum_{i=1}^kb_ip_i$ be two points in $C$. This means that $\sum a_i = \sum b_i =1$ and $a_i\geq 0$, $b_i \geq 0$. The line segment joining $x$ and $y$ is the set of points of the form $tx+(1-t)y$, where $t \in [0,1]$. Hence a point between $x$ and $y$ is
$$\sum_i{(ta_i+(1-t)b_i)p_i}.$$
Now $\sum_i (ta_i+(1-t)b_i) = t + (1-t) = 1$. Also, $ta_i+(1-t)b_i \geq ta_i \geq 0$. This shows that the point $tx+(1-t)y$ satisfies the two conditions required to lie in $C$, for every $t \in [0,1]$.
Hint: Given two points $b = \sum_i b_i p_i$ and $c = \sum_i c_i p_i$ in $C$ and $0 \le t \le 1$, how would you represent $t b + (1-t) c$?