General Proof for the triangle inequality
I am trying to prove: $P(n): |x_1| + \cdots + |x_n| \leq |x_1 + \cdots +x_n|$ for all natural numbers $n$. The $x_i$ are real numbers.
Base: Let $n =1$: we have $|x_1| \leq |x_1|$ which is clearly true
Step: Let $k$ exist in the integers such that $k \geq 1$ and assume $P(k)$ is true.
This is where I am lost. I do not see how to leverage the induction hypothesis.
Here is my latest approach:
Can you do the following in the induction step: Let $Y$ = |$x_1$ +...+$x_n$| and Let $Z$ = |$x_1$| +...+ |$x_n$| Then we have: |$Y$ + $x_n+1$| $\leq$ $Z$ + |$x_n+1$|. $Y$ $\leq$ $Z$ from the induction step, and then from the base case this is just another triangle inequality. End of proof.
$\endgroup$ 52 Answers
$\begingroup$As @ivan indicates, the inequality is reversed - it should be
$$ |x_1 + x_2 + \dots + x_n| \leq |x_1| + |x_2| + \dots + |x_n| $$
As the base case for induction, you need to show (or assert? can you take the "basic" triangle inequality for granted?)
$$ |x_1 + x_2| \leq |x_1| + |x_2|. $$
Hint:
One way to do this is to show $(|a + b|)^2 \leq (|a| + |b|)^2$ by expanding the LHS and using $ab \leq |a||b|$.
Then, for induction, assume
$$ |x_1 + x_2 + \dots + x_n| \leq |x_1| + |x_2| + \dots + |x_n| $$
and show
$$ |x_1 + x_2 + \dots + x_n + x_{n+1}| \leq |x_1| + |x_2| + \dots + |x_n| + |x_{n+1}|$$
using the induction hypothesis and the base case.
$\endgroup$ 2 $\begingroup$It is ok for $|x_1 + x_2| \le |x_1| + |x_2|$ (I)
$|x_1 + x_2 +\cdots+ x_k| \le |x_1| + |x_2|+\cdots+ |x_k|$ (Hypothesis)(II)
For $n = k+1$ :
a) 1st. Apply The triangle inequality for $2$ different "numbers"$(x_1 + x_2 +\cdots+ x_k)$ and $x_{k+1}$ because it is ok by (I)
b)2nd Apply the induction Hypothesis (II)
$|x_1+x_2+\cdots+ x_k +x_{k+1}| \le |x_1 + x_2 +\cdots+x_k|+|x_{k+1}| \le |x_1|+|x_2|+\cdots+|x_k|+|x_{k+1}|$
$\endgroup$ 0
