-1
$\begingroup$

Is the above inequality true? If yes, could you please provide a proof. If not, could you please tell in which cases it is true.

(Edit: This is related to McCormick Relaxation for binary variables and not natural numbers as I mistook it for. Relaxation for for $XY<=C$, in optimization problems.)

$\endgroup$
7
  • $\begingroup$ do you count zero as a natural number $\endgroup$
    – ThePortakal
    Nov 15, 2016 at 0:49
  • 1
    $\begingroup$ $ab=(a-1+1)(b-1+1)=$ $(a-1)(b-1)+(a-1)+(b-1)+1=a+b-1+(a-1)(b-1)$. $\endgroup$
    – Andrés E. Caicedo
    Nov 15, 2016 at 0:50
  • $\begingroup$ No. Not counting zero. Answered my own question. Could you please comment on the McCormick Relaxation? $\endgroup$
    – novice
    Nov 15, 2016 at 0:50
  • $\begingroup$ @AndrésE.Caicedo Thats a+b-2 not a+b-1. Nope sorry I misread. $\endgroup$
    – novice
    Nov 15, 2016 at 0:53
  • $\begingroup$ @TheNovice No, it is as I wrote. $\endgroup$
    – Andrés E. Caicedo
    Nov 15, 2016 at 0:54

2 Answers 2

Reset to default
1
$\begingroup$

$ab - (a+b-1) =ab-a-b+1 =(a-1)(b-1) \ge 0 $ since $a \ge 1$ and $b \ge 1$.

There is equality only when at least one of the numbers is equal to $1$.

$\endgroup$
1
$\begingroup$

Sorry for the elementary question.

Let $X = 1$, $Y = 1$.

$XY = 1. $ $X+Y-1 = 1$

Now we only need to notice that $XY$ increases at a faster pace than $X+Y-1.$ So this holds for all natural numbers.

$\endgroup$
9
  • $\begingroup$ This should probably be an edit to your original question (as it expands the question--a little more about what you know--but doesn't really answer the question). $\endgroup$
    – TravisJ
    Nov 15, 2016 at 1:12
  • $\begingroup$ I thought it did answer the question about $XY >= X+Y -1$ $\endgroup$
    – novice
    Nov 15, 2016 at 1:16
  • $\begingroup$ @user251257 : Sorry I do not mean to be rude, but is my logic wrong? If not why does it not answer the question which I asked? I am just failing to see how this does not answer the question. $\endgroup$
    – novice
    Nov 15, 2016 at 1:31
  • $\begingroup$ As you increase X or Y, XY will increase more than X+Y $\endgroup$
    – novice
    Nov 15, 2016 at 1:33
  • $\begingroup$ Increase X by 1, now X=2, XY =2, X+Y -1 =2. Increase Y by one, now XY = 4, X+Y -1 = 3. The difference between the two keeps on increasing. It's an observation. I am pretty sure the proof and it's theorem of it should be quite basic. Help me by providing it please? $\endgroup$
    – novice
    Nov 15, 2016 at 1:42

Not the answer you're looking for? Browse other questions tagged .