Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To prove an algorithm's correctness, I need to show that

$|x|+|x+\Delta h+\Delta s| \geq |x + \Delta s|+|x+\Delta h|$

when $\Delta h > 0$ and $\Delta s > 0$. Mathematica simplifies this to True, but I don't see how. The only tools I know are the triangle inequality and arithmetic/geometric mean inequality.

How can I prove this inequality?

share|improve this question
    
Have you tried to suppose that $|x|+|x+\Delta h+\Delta s| < |x+\Delta s| + |x+\Delta h |$ and see if this leads to a contradiction? –  Marra Feb 22 '13 at 23:47

2 Answers 2

up vote 2 down vote accepted

In general, any function of the form $|x+a|$ has slope $-1$ to the left of $-a$ and $+1$ to the right of $-a$. This means that $|x+a|+|x+b|$ has slope $-2$ or $0$ or $2$, depending on where $x$ is in relation to $-a$ and $-b$. Now take $a,b$ to be $0,\Delta h+\Delta s$ and $\Delta h,\Delta s$, respectively, and figure out where the corners of the graphs are. (In short, just compute both functions explicitly as piecewise defined by lines, and compare!)

share|improve this answer

to support martin's comments,I put a graph here.enter image description here

we can explore further.

when a<0,and b>0,let a=-p,p>0, then let u=x-p,the left=|u+p|+|u+b|, and right=|u|+|u+p+b|,so right >left.

when a<0,b<0, then let a=-p,b=-q, p>0.q>0, let u=x-p-q, then left=|u+p+q|+|u|,right=|u+q|+|u+q|,so left>right .

so we can say when a*b>=0, it is true that left>=right; when a*b<0, it is <.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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