4
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ I think your inequality is wrong. $|1|+|-2|$ is not <= than $|-1+2|$. $\endgroup$ – ivan Sep 14 '12 at 6:18
  • $\begingroup$ The domain given is the natural numbers. $\endgroup$ – Tarnation Sep 14 '12 at 6:18
  • 2
    $\begingroup$ No. It says $n$ is natural. Otherwise this is an equality. $\endgroup$ – ivan Sep 14 '12 at 6:21
  • $\begingroup$ The domain of the index of $x$ is $\mathbb{N}$. It is not clear what the $x_k$ belong to? In any case, I would agree with @ivan's first comment. $\endgroup$ – copper.hat Sep 14 '12 at 6:21
  • $\begingroup$ I believe you have the inquality wrong and that is should be $\geq$ and not $\leq$ $\endgroup$ – Belgi Sep 14 '12 at 6:26
11
$\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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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$ – CodeKingPlusPlus Sep 15 '12 at 19:00
  • 2
    $\begingroup$ Right idea, though you should have $Y = x_1 + \dots + x_n$, (otherwise, when you write $|Y + x_{n+1}|$, you're referring to $||x_1 + \dots + x_n| + x_{n+1}|$. You'll have $|Y| \leq Z$ by the induction hypothesis. $\endgroup$ – BaronVT Sep 17 '12 at 18:29
0
$\begingroup$

It is ok for $|x_1 + x_2| < |x_1| + |x_2|$ (I)

$|x_1 + x_2 +\cdots+ x_k| < |x_1| + |x_2|+...+ |x_k|$ (Hipothesis)(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 Hipothesis (II)

$|x_1+x_2+\cdots+ x_k +x_{k+1}| < |x_1 + x_2 +\cdots+x_k|+|x_{k+1}| < |x_1|+|x_2|+..+|x_k|+|x_{k+1}|$

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ You may want to use \le (a.k.a. $\le$), though. $\endgroup$ – user228113 May 17 '15 at 12:12
  • $\begingroup$ Thanks Sassatelli, I used < because I had no idea how to write ≤ . $\endgroup$ – Mario May 18 '15 at 2:33

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.