6

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?

tba
  • 1,136
  • 1
  • 10
  • 20
  • 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 Answers2

2

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!)

Greg Martin
  • 78,820
1

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 ab>=0, it is true that left>=right; when ab<0, it is <.

chenbai
  • 7,581