2
$\begingroup$

Let $C \subset \mathbb{R}^n$ be a convex set. Additionally, $x_1, x_2,\dots, x_k \in C$ and $\theta_1,\theta_2,\dots,\theta_k \in \mathbb{R}, \theta_i \ge 0, \sum\theta_i = 1$. I have to proof that $\theta_1x_1+\theta_2x_2+\dots+\theta_kx_k \in C$. I decided to prove it by induction.

If I add a new term to the previous combination, I'll have $\theta_1x_1+\theta_2x_2+\dots+\theta_kx_k+\theta_{k+1}x_{k+1}$. Then, if I make $\theta_{k+1} = 0$, it is true that the latter combination belongs to $C$. By induction, and knowing that this is true for $k=2$, it will hold for any value of $k$.

I have always had trouble with proofs, so I am not sure when I arrive to such a trivial conclusion. Could anybody please help and tell me if this is a valid proof?

Thanks in advance.

  • 0
    I don't follow. In the induction step you have $\theta_1,\ldots,\theta_{k+1}\in\mathbb{R},\theta_i\geq 0,\sum_{i=1}^{k+1}\theta_i=1$. __If__ $\theta_{k+1}=0$, then by induction it is true that $\sum_{i=1}^{k+1}\theta_i x_i=\sum_{i=1}^k\theta_i x_i\in C$, but I don't see why you can assume that $\theta_{k+1}=0$.2011-09-29
  • 0
    Thanks for your answer. That was exactly my doubt. Whether I could assume that or not. But I am starting to notice that if I assumed that, then I would not be making a general proof.2011-09-29

1 Answers 1

2

This is not a valid proof, but you are on the right track. Induction will work, if you structure things right.

Here is a hint:

Fact 1: $\theta_1 + \cdots + \theta_k = 1 - \theta_{k+1} \geq 0,\;$ and

Fact 2: You can actually assume without loss of generality that $1 - \theta_{k+1} > 0\,$ (why?), and so,

$$ \theta_1 x_1 + \cdots + \theta_k x_k + \theta_{k+1} x_{k+1} = (1 - \theta_{k+1}) y + \theta_{k+1} x_{k+1} \> , $$ where $$ y = \frac{\theta_1 x_1 + \cdots + \theta_k x_k}{\theta_1 + \cdots + \theta_k} \>. $$

Under the right induction hypothesis, what do you know about $y$ and why is it true? Now, use this and what you know about convexity for two points to conclude.

  • 0
    First of all, thank you for answering with another question. I want to learn this kind of things right, and I think that is the way to go. In **Fact 2**, you asked me why we could assume strict positiveness. I think that making that quantity equal to zero, that will imply that every other theta would be zero, transforming all the expression in a single appearance of the point x_{k+1} which we already know is in C.2011-09-29
  • 0
    ...then, after the transformation and appearance of the 'y' point, I think the following: if the first k terms are a convex combination in C, then the sum of thetas equals one, and 'y' is a point in C. Then, the convex combination of 'y' and the point x_{k+1} is also in C. As we already know it holds for k=2, then we have proved it by induction. Am I right, @cardinal? Or still missing something?2011-09-29
  • 0
    **Yes**. Essentially. By dividing by $\theta_1 + \cdots + \theta_k$ when constructing $y$, then $y$ **is** a convex combination of points in $C$. So, by the induction hypothesis, $y \in C$. The rest of what you said is then correct.2011-09-29