Proof by Induction: extended 'triangle' inequality

[ku1005]

i realise the following Q is prob really easy, but I just dont understand how to read it/ attack the Q

"Assuming that the triangle inequality: |a+b|<=|a|+|b| holds for any two numbers a and b, show that

|x1 + x2+......+ Xn| <= |x1| + |x2|+ ....+ |xn|

for any n numbers"

i dotn understand whether x1 and x2 and x3...to xn must be integers, or if they can be any numbers in no sequence, which if this is the case how would you find a starting point to prove this via induction??, because if this were the case, how can you be sure that all numbers that follow you random choice also obey???

thanks heaps!!!

 

[Trebor]

Firstly, you want to make sure that the inequality holds for n=1. Then assume that the inequality:

|x1 + x2+......+ Xn| <= |x1| + |x2|+ ....+ |xn|

holds for n=k.

You now need to prove it holds for n=k+1. To do this, add \(\displaystyle |x_{n+1}|\) to both sides of the inequality. By using the triangle inequality, you can replace the left hand side of the inequality. And you have proved it for n>=1.

I hope you can follow that. If your still stuck, show some of your own working, and I'll guide you through the next steps. It doesn't matter whether the numbers are in a sequence or not. The inequality will still hold.

 

[ku1005]

thanks....i understand that you must proove it for n = 1 an then assume for k= n it is true and then proove k+1 = n is also true.

the part i dont understand is if you substitute n = 1, what numbers are we concerned with ???


ie heres how i see it

let S(n) = the statement so

if n=1

|x1|<=|x1| which is obviously true

therfore assume n= k is true

where :

req to prove n = k+1 is true hence"

S(k)= |x1 + x2+.....+xk| <= |x1| + |x2| +.....+|xk|

S(k+1)= |x1 + x2 + ....+ x(k) + x(k+1)|

SUB known so:

where this is the stage im stuk at??? cheers for helping!

 

[Trebor]

Assume the statement is true for \(\displaystyle n=k\):
\(\displaystyle |x_1+x_2+x_3+...+x_k|<=|x_1|+|x_2|+|x_3|+...|x_k|\)

Now add \(\displaystyle |x_{k+1}|\) to both sides of this inequality:
\(\displaystyle |x_1+...+x_k|+|x_{k+1}|<=|x_1|+...+|x_k|+|x_{k+1}|\)

Using the triangle inequality:
\(\displaystyle |x_1+...+x_k+x_{k+1}|<=|x_1+...+x_k|+|x_{k+1}|\)

Therefore:
\(\displaystyle |x_1+...+x_k+x_{k+1}|<=|x_1|+...+|x_k|+|x_{k+1}|\)

And since it is true for \(\displaystyle n=1\), it is true for all positive integers \(\displaystyle n\).