7

Prove the following theorem:

Let $V$ be a linear space and $D$ a convex set. Let $x_1,\ldots,x_k$ be $k$ points in $D$. Let $a_1,\ldots,a_k$ be non-negative scalars such that $\sum\limits_{i=1}^n a_i=1$. Then the so called convex combination $\sum\limits_{i=1}^k a_ix_i$ is an element of $D$.

I tried looking up the definition of convex sets which is that if you draw a line between two points in the set that the entire line should line within the set and that this should hold for all points in the set. For the rest, since I am entirely new to proofs like these, I dont have a clue how to proceed. Can someone please help me? It would be highly appreciated.

Community
  • 1
dreamer
  • 3,379

2 Answers2

12

Well, first note that if we only have two points $x_1$ and $x_2$, then all that's being said is whenever $a + b = 1$ the point $a*x_1 + b*x_2$ is in $D$. This is very clear though, because $b = 1-a$ and so the point in question is $a*x_1 + (1-a)*x_2$, which is a point on the line between $x_1$ and $x_2$.

Generally speaking, if we have points $x_1, ..., x_k$, and $\sum_{i=1}^k a_i = 1$, then you can write $a_1 + ... + a_{k-1} = 1 - a_k$ to get that

$\sum_{i=1}^k a_i x_i = a_k x_k + (1-a_k)\sum_{i=1}^{k-1} \frac{a_i}{1 - a_k} x_k $

The points $x_k$ and $\sum_{i=1}^{k-1} \frac{a_i}{1 - a_k} x_k$ may by induction be assumed to be points in $D$, so this forms the induction step of the proof.

Eric Haengel
  • 5,054
  • Thanks a lot. Your explanation is very clear and understandable. Could you show me how you can complete the induction proof? – dreamer Feb 18 '13 at 18:32
  • The first two sentences form the $k=2$ case, the induction base case (I guess I ignored the k=1 case as trivial). The remainder of what I wrote forms the proof that if the statement is true for $k-1$ then it is also true for $k$. I believe that these two pieces together form a complete induction proof. – Eric Haengel Feb 18 '13 at 18:39
  • Ok. Thank you very much :) – dreamer Feb 18 '13 at 18:43
4

You can proceed by induction on $k$, the case $k=1$ being trivial. If $k>1$, let $u=\sum_{i=1}^{k-1}a_i=1-a_{k}$. If $u=0$, then $\sum_{i=1}^k a_ix_i = x_k\in D$. Otherwise let $b_i=\frac{a_i}u$ and observe that $y:=\sum_{i=1}^{k-1}b_ix_i\in D$ by induction assumption because $\sum_{i=1}^{k-1}b_i=1$ and all $b_i\ge 0$. Then $$\sum_{i=1}^k a_ix_i = x_k+u(y-x_k)$$ is a point on the line segment from $x_k$ to $y$, hence in $D$.

Hagen von Eitzen
  • 374,180