Why is Simple Inequality True?

[nonequilibrium]

Can anybody tell me why

$$\sum_{j=1}^p |x_j-y_j| \leq \left( \sum_{j=1}^p 1\right)^{1/2} \left( \sum_{j=1}^p |x_j-y_j|^2 \right)^{1/2}$$

is true?

Thank you!

 

[rasmhop]

This is a special case of the Cauchy–Schwarz inequality which in the finite-dimensional real case state:
$$\sum_{i=1}^n a_i b_i \leq \left( \sum_{i=1}^n a_i^2 \right)^{1/2} \left( \sum_{i=1}^n b_i^2 \right)^{1/2}$$
For all real numbers a_i, b_i.

 

[nonequilibrium]

Oh, thank you very much :)

Just as a little side-Q: Since this is a special case, as you say, are there also some more insightful proofs? Or is it too abstract for that?

 

[rasmhop]

There are plenty of ways to show it.

For simplicity let $z_n = |x_n-y_n|$ (no need to keep track of both x_j and y_j).

Method 1 (means):
The generalized mean inequality says that:
$$M_p(a_1,a_2,\ldots,a_n) = \left(\frac{a_1^p + a_2^p + \cdots + a_n^p}{n}\right)^{1/p}$$
Is increasing as a function of p if a_1, ..., a_n are non-negative numbers. In particular:

$$M_1(z_j) =\frac{\sum_{j=1}^p z_j }{p} \leq \left(\frac{\sum_{j=1}^p z_j^2}{p}\right)^{1/2} = M_2(z_j)$$
(this is often referred to as the AM-QM inequality since M_1 is called the Arithmetic Mean and M_2 is called the Quadratic Mean).
[EDIT: Note also that the AM-QM inequality is practically the same as yours so if you want more proofs just search for proofs of the AM-QM inequality]Method 2 (rearrangement and fiddling with indices):
Assume without loss of generality $z_1 \leq z_2 \leq \cdots \leq z_p$ (otherwise just rearrange the sequence). You wish to show:
$$\left(\sum_{j=1}^p z_j \right)^2 \leq p \left( \sum_{j=1}^p z_j^2 \right)$$
We can extend the sequence z_n to all integer indices by letting $z_{np+k} = z_k$ for all integers n and k (in other words we just extend it by letting z_{p+1} = z_1, z_{p+2} = z_2, ...).

You have
$$\left(\sum_{j=1}^p z_j \right)^2 = \sum_{i=1}^p \sum_{j=1}^{p} z_i z_j = \sum_{i=1}^p \sum_{j=1}^{p} z_jz_{j+i}$$

By the rearrangement inequality:
$$\sum_{j=1}^{p} z_jz_{j+i} \leq \sum_{j=1}^{p} z_j^2$$
So:
$$\sum_{i=1}^p \sum_{j=1}^{p} z_jz_{j+i} \leq \sum_{i=1}^p\sum_{j=1}^{p} z_j^2 = p\sum_{j=1}^{p} z_j^2$$I also guess there is a way to reason geometrically since:
$$\left(\sum_{j=1}^p z_j^2\right)^{1/2}$$
is the length of the vector (z_1,z_2,...,z_j).

 

[nonequilibrium]

My apologies for not having replied sooner! I have read this much earlier, but just remembered I had forgotten to reply!

Thank you very much, it's rare to get such a helpful post, was exactly what I was looking for :)