Proof verification of the Triangle Inequality for $k$ vectors?

Question

One of my homework problems was to prove an extension of the Triangle Inequality to $k$ vectors through induction, and I produced a five step proof that I think is correct, but I'm unsure that step $3$ can be made without loss of generality. The proof is as follows:

Assuming the Triangle Inequality, prove with induction that $|| \vec{x}_1 + \dots + \vec{x}_k || \le || \vec{x}_1|| + \dots + ||\vec{x}_k||$

$(1) \quad$ Holds for $k=1$ trivially, holds for $k=2$ by Triangle Inequality

$\qquad$ The inductive base case

$(2) \quad$ Assume $\vec{x}_1 + \dots + \vec{x}_k = \vec{y}$.

$(3) \quad || \vec{x}_1 + \dots + \vec{x}_k || \le || \vec{x}_1|| + \dots + ||\vec{x}_k||$

$\qquad ||\vec{x}_1 + \dots + \vec{x}_{k+1} || \le || \vec{x}_1|| + \dots + ||\vec{x}_{k+1}||$

$\qquad$ Subtract these two inequalities.

$\qquad ||\vec{x}_1 + \dots + \vec{x}_{k+1} || - || \vec{x}_1 + \dots + \vec{x}_k || \le ||\vec{x}_{k+1}||$

$(4) \quad ||\vec{y} + \vec{x}_{k+1}|| - ||\vec{y}|| \le ||\vec{x}_{k+1}||$

$\qquad$ Substitute

$(5) \quad ||\vec{y} + \vec{x}_{k+1}|| \le ||\vec{y}|| + ||\vec{x}_{k+1}||$

$\qquad$ Rearrange

True by Triangle Inequality, concluding the proof.

Can step $(3)$ be made without loss of generality? The rest of the proof looks correct to me.

Answer 1

Your step $3$ is not correct since it uses the fact that

$$\qquad ||\vec{x_1} + \dots + \vec{x_{k+1}} || \le || \vec{x_1}|| + \dots + ||\vec{x_{k+1}}||$$ and $$\qquad ||\vec{x_1} + \dots + \vec{x_{k+1}} || \le || \vec{x_1}|| + \dots + ||\vec{x_{k+1}}||$$

are true and then deduce an expression which is valid by triangle inequality. But your actual job was to prove the triangle inequality itself. So you have circular reasoning.

Better approach to this problem:

Assume that the inequality is valid for $k$ vectors.

So we have that $$\qquad ||\vec{x_1} + \dots + \vec{x_{k}} || \le || \vec{x_1}|| + \dots + ||\vec{x_{k}}||$$

For $k+1$ vectors, we can state that $$\qquad ||\vec{x_1} + \dots + \vec{x_{k+1}}||$$ $$\le ||\vec{x_1} + \dots + \vec{x_{k}}|| + ||\vec{x_{k+1}}||$$ $$\le || \vec{x_1}|| + \dots + ||\vec{x_{k}}|| + ||\vec{x_{k+1}}||$$

So it is true for $k+1$ vectors.

The result is true by induction.

Hope this helps.

Answer 2

$||v_1+v_2+...+ v_k + v_{k+1}|| = ||y + v_{k+1}|| < ||y|| + ||v_{k+1}|| < ||v_1|| + ||v_2|| ...+ ||v_k|| + ||v_{k+1}||$.