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

$\endgroup$
5
  • 7
    $\begingroup$ I think your inequality is wrong. $|1|+|-2|$ is not <= than $|-1+2|$. $\endgroup$
    – ivan
    Sep 14, 2012 at 6:18
  • $\begingroup$ The domain given is the natural numbers. $\endgroup$
    – Tarnation
    Sep 14, 2012 at 6:18
  • 2
    $\begingroup$ No. It says $n$ is natural. Otherwise this is an equality. $\endgroup$
    – ivan
    Sep 14, 2012 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, 2012 at 6:21
  • 1
    $\begingroup$ I believe you have the inquality wrong and that is should be $\geq$ and not $\leq$ $\endgroup$
    – Belgi
    Sep 14, 2012 at 6:26

2 Answers 2

14
$\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
  • 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$ Sep 15, 2012 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, 2012 at 18:29
3
$\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

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.