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
    Thanks $f$or your answer. That was exactly my doubt. Whether I could assume that or not. But I am starting to notice that i$f$ I assumed that, then I would not be making a general proo$f$.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
    **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