Can the norm of a convex combination of vectors be greater than the norm of their sum?

Question

Can the norm of a convex combination of vectors be greater than the norm of their sum?

Or is it always the case that:

$|| \sum_i w_i x_i || \leq \sum_i w_i \;|| \sum_i x_i || $

(for positive $w_i$)

(with the standard L2-norm).

Proof or counterexample would be great. I'm also curious if it holds for other norms.

Answer 1

This is correct for any norm. Note that for any norm the inequality $$\left\|\sum \limits_{i = 1}^n \lambda_i x_i\right\| \le \sum \limits_{i = 1}^n |\lambda_i| \left\|x_i\right\|$$

holds for any linear combination. This is easy to prove via induction, using the triangle inequality and absolute homogeneity of the norm.

In your case the $w_i$ are all nonnegative, so $|w_i| = w_i$ and the equality in your question holds true.