1
$\begingroup$

Assume that $K\subseteq \mathbb{R}^n$ is convex and $x_1,...,x_k\in K$. Show that any convex combination of $x_1,...,x_k$ is contained in $K$.

Relevant definitions:

Definition of Convexity: A set $k\subseteq\mathbb{R}$ is convex if for all $x,y\in k$, the line segment between $x$ and $y$ is entirely contained in $k$.

Definition of convex combination: A convex combination of $x_1,...,x_k\in\mathbb{R}^n$ is $$x=\lambda_1x_1+\lambda_2x_2+...+\lambda_kx_k$$ such that $0\leq\lambda_i\leq1$ and $\lambda_1+\lambda_2+...+\lambda_k=1$

My Attempt:

We can solve this by induction on $k$.

Base Case: By the definition of convexity, we know that the statement is true for $k=2$.

Induction Hypothesis: Assume that the statement holds for some value $l$. i.e. For $x_1,...,x_l\in K$, and $\lambda_1,...,\lambda_l\geq0$ with $\lambda_1+...+\lambda_l=1$, we have $\lambda_1x_1+...+\lambda_lx_l\in K$.

Induction Step: Let $x_1,...x_l,x_{l+1}\in K$ and $\lambda_1,...,\lambda_l,\lambda_{l+1}\geq0$ with $\lambda_1+...+\lambda_l+\lambda_{l+1}=1$. Now, assume that $\lambda_1\neq 1$. Then $$y=\lambda_1x_1+(1-\lambda_1)(\mu_2x_2+...+\mu_lx_l+\mu_{l+1}x_{l+1})$$ where $\mu_i=\frac{\lambda_i}{1-\lambda_1}\geq0$. Then $$\mu_2+...+\mu_{l+1}=\frac{\lambda_2+...+\lambda_{l+1}}{1-\lambda_1}=1$$ Since $K$ is convex and $x_2,...x_{l+1}\in K$, we have that $\mu_2+,...\mu_{l+1}x_{l+1}\in K$. Then since $x_1\in K$, we have that $y\in K$

I don't think I did this correctly because I couldn't find where I needed to apply the induction hypothesis. Any pointers would be very helpful. Thanks.

$\endgroup$
2
$\begingroup$

You did use the induction hypothesis to conclude that $\sum_{i=2}^{l+1} \mu_i x_i \in K$.

There are $l$ elements and you have just shown that $\mu_2 + \ldots + \mu_{l+1}=1$ and they are nonnegative and hence you can use the induction hypothesis.

Remark: To see it even clearer, rather than treating the first element separatedly, treat the last element separately instead.

$\endgroup$
1
  • $\begingroup$ Thanks for the remark. That makes it so much easier to see. $\endgroup$ May 16 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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