Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  LostInMath Sep 29 '11 at 14:05
    
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. –  Fernandez Sep 29 '11 at 14:46

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  Fernandez Sep 29 '11 at 14:50
    
...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? –  Fernandez Sep 29 '11 at 14:54
    
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. –  cardinal Sep 29 '11 at 15:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.