0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ No in step (3) you're succumbing to circular reasoning. You've just assumed what you need to prove. $\endgroup$ – K.Power Jan 25 '16 at 17:14
  • 1
    $\begingroup$ And in any case, you can't subtract inequalities. For example, $3 \leq 5$ and $2 \leq 5$ but $(3 - 2) \nleq (5 - 5)$. $\endgroup$ – levap Jan 25 '16 at 17:17
  • $\begingroup$ You should also use a different variable to $k$ in your hypothesis step, as you need to assume that it's true for some fixed arbitrary integer $n \geq 1$. $\endgroup$ – K.Power Jan 25 '16 at 17:18
  • $\begingroup$ I didn't even read that far but quite right. The best you can do is subtract the same element from both sides of the inequality. $\endgroup$ – K.Power Jan 25 '16 at 17:19
  • $\begingroup$ Could I follow the same vein of thought and correct the proof? $\endgroup$ – Rob Bland Jan 25 '16 at 17:20
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$||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}||$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.