I am trying to solve this below problem.
Consider $\mathbb{R}^n$ with the metric $d(x,y) = \left(\sum\limits_{i=1}^n \left(x_i – y_i\right)^2 \right)^{1/2}$. Prove the triangle inequality.
I first need to prove the Cauchy-Schwarz inequality, which states that for $x,y \in \mathbb{R}^n$, we have
\begin{align*}
\left(\sum\limits_{i=1}^n x_i y_i \right)^2 \leq \left(\sum\limits_{i=1}^n x_i^2 \right) \cdot \left(\sum\limits_{i=1}^n y_i^2 \right).
\end{align*}
The only way I know how to prove this is by "proceeding backwards," and arguing that every step is reversible. My attempt:
\begin{align*}
\left(\sum\limits_{i=1}^n x_i y_i \right)^2 \leq \left(\sum\limits_{i=1}^n x_i^2 \right) \cdot \left(\sum\limits_{i=1}^n y_i^2 \right) & \iff 0 \leq \left(\sum\limits_{i=1}^n x_i^2 \right) \cdot \left(\sum\limits_{i=1}^n y_i^2 \right) – \left(\sum\limits_{i=1}^n x_i y_i \right)^2 \\
& \iff 0 \leq 2 \left(\sum\limits_{i=1}^n x_i^2 \right) \cdot \left(\sum\limits_{i=1}^n y_i^2 \right) – 2\left(\sum\limits_{i=1}^n x_i y_i \right)^2 \\
& \iff 0 \leq 2 \sum\limits_{i=1}^n x_i^2 \sum\limits_{i=1}^n y_i^2 – 2 \sum\limits_{i=1}^n x_i y_i \sum\limits_{i=1}^n x_i y_i \\
& \iff 0 \leq \sum\limits_{i=1}^n x_i^2 \sum\limits_{j=1}^n y_i^2 + \sum\limits_{j=1}^n x_j^2 \sum\limits_{i=1}^n y_i^2 – 2 \sum\limits_{i=1}^n x_i y_i \sum\limits_{i=1}^n x_i y_i \\
& \iff 0 \geq \sum\limits_{i=1}^n \sum\limits_{j=1}^n \left(x_i y_j + x_j y_i \right)^2
\end{align*}
As the final line is true since a sum of non-negative terms is negative, our starting statement is also true.
The steps of the proof are a bit obscure to me. I know we're working toward the final statement, ultimately, and the way to. build that is to break apart the sum in the third line and notice that the actual index we use doesn't matter, so I need only index $x$ with $i$ and $j$ and $y$ with $i$ and $j$. If anyone knows how to make this proof more intuitive or more elegant, I'd appreciate.
Onto the triangle inequality:
I need to show that for $x,y,z \in \mathbb{R}^n$, we have:
$$d(x,y) \leq d(x,z) + d(z,y) \text{ or } \left(\sum\limits_{i=1}^n (x_i – y_i)^2 \right)^{1/2} \leq \left(\sum\limits_{i=1}^n (x_i – z_i)^2 \right)^{1/2} + \left(\sum\limits_{i=1}^n (z_i – y_i)^2 \right)^{1/2}.$$
We start with the square of both sides above and again derive a true statement:
\begin{align*}
\sum\limits_{i=1}^n (x_i – y_i)^2 & \leq \sum\limits_{i=1}^n \left(x_i^2 – 2x_i y_i + y_i^2\right) \\
& = \sum\limits_{i=1}^n x_i^2 – 2 \sum\limits_{i=1}^n x_i y_i + \sum\limits_{i=1}^n y_i^2
\end{align*}
I need to work $z_i$ in here somewhere, and I assume what I need to do is add and subtract $z_i$ for each $i$ somewhere. An alternative is to start with the full statement, square both sides, and derive a true statement.
Any hints on how to proceed would be appreciated.
Best Answer
\begin{align*} \sum\limits_{i=1}^n (x_i - y_i)^2 &= \sum\limits_{i=1}^n (x_i - z_i + z_i - y_i)^2\\ &= \sum\limits_{i=1}^n (x_i - z_i)^2 + \sum\limits_{i=1}^n (z_i - y_i)^2 + 2\sum\limits_{i=1}^n (x_i - z_i)(z_i - y_i)\\ &\le \sum\limits_{i=1}^n (x_i - z_i)^2 + \sum\limits_{i=1}^n (z_i - y_i)^2 + 2\left(\sum\limits_{i=1}^n (x_i - z_i)^{2}\right)^\frac12\left(\sum\limits_{i=1}^n (z_i - y_i)^{2}\right)^\frac12\\ &= \left(\left(\sum\limits_{i=1}^n (x_i - z_i)^{2}\right)^\frac12 + \left(\sum\limits_{i=1}^n (z_i - y_i)^{2}\right)^\frac12\right)^2 \end{align*}