# proof of $\|y-\sum_{i=1}^n a_ix_i\|\leq \sum_{i=1}^n a_i\|y-x_i\|$

How to prove $\|y-\sum_{i=1}^n a_ix_i\|\leq \sum_{i=1}^n a_i\|y-x_i\|$? $\ \ \ \ \sum_i a_i = 1$, $0\leq a_i \leq 1$ and $y,x_i\in \mathbb{R}^m, \ \ \forall i$

It seems simple however I have no idea to prove it formally?

Pf:
Suppose $n=2$

\begin{aligned} y-(a_1x_1+a_2x_2) &= a_1y+a_2y-a_1x_1-a_2x_2-(a_1+a_2)y+y\\ &= a_1(y-x_1)+a_2(y-x_2)-(a_1+a_2)y+y\\& \end{aligned}

So take norm on both sides:

\begin{aligned} \|y-(a_1x_1+a_2x_2)\| &= \|a_1(y-x_1)+a_2(y-x_2)-(a_1+a_2)y+y\|\\& \end{aligned}

By triangle inequality:

\begin{aligned} \|y-(a_1x_1+a_2x_2)\| &\leq \|a_1(y-x_1)\|+\|a_2(y-x_2)\|+\|(a_1+a_2)y+y\|\\& \end{aligned}

Then how to deal with the tail term?

Here I want to show $\|y-(a_1x_1+a_2x_2)\| \leq \|a_1(y-x_1)\|+\|a_2(y-x_2)\|$

• Don't you want to show the $\underline{norm}$ of the left side is less than or equal to the right side? Commented Dec 24, 2015 at 21:34
• @user84413 If the one with norm holds then get rid of the norm of LHS, which will hold. Or any other better way? Commented Dec 24, 2015 at 21:36
• As stated, the problem doesn't seem correct, since the left side is a vector in $R^m$ and the right side is a number. Furthermore, the statement seems false if all $a_i=0$. (Maybe you want to assume that their sum is 1.) Commented Dec 24, 2015 at 21:39
• I fix it. It should be correct now. Commented Dec 24, 2015 at 21:42
• $\{a_i\}$ should be stochastic like Commented Dec 24, 2015 at 21:48

You have $\|y-\sum_{i=1}^{n}a_ix_i\|=\|\sum_{i=1}^n(a_iy-a_ix_i)\|=\|\sum_{i=1}^n a_i(y-x_i)\|\le\sum_{i=1}^n a_i\|y-x_i\|$