Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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|cite|improve this answer

Your Answer


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.