I'm encountering this inequality for dimensionality reduction problem. The simplified form looks as follows:

Consider positive integers $a_1$, $a_2$, $b_1$ and $b_2$ where $a_1>b_1$ and $a_2>b_2$. Prove that

$$ \frac{a_1a_2-b_1b_2}{a_1a_2-1}\geq\frac{(a_1-b_1)(a_2-b_2)}{(a_1-1)(a_2-1)} $$

The inequality seems very trivial and easy but I am struggling to prove it. While I could prove for the special cases where (1) $a_1=a_2=a$, which reduces to

$$ (a-1)[(b_1+b_2-2)a-(2b_1b_2-b_1-b_2)]\geq0 $$

$$ \iff a\geq max(b_1,b_2)\geq\frac{b_1(b_2-1)+b_2(b_1-1)}{(b_2-1)+(b_1-1)}, $$

and (2) $b_1=b_2=b$, which reduces to

$$ (a_1a_2+b)(a_1+a_2)\geq a_1a_2(2b+2), $$

I cannot verify the general case where $a_1\neq a_2$ and $b_1 \neq b_2$. If someone could help to provide guidance, reference to similar inequalities in the literature, or any idea to the solution, I would be very thankful.

  • 2
    $\begingroup$ It is linear in $b_1$, so it suffices to consider $b_1=1$ and $b_1=a_1-1$. The same for $b_2$. $\endgroup$ – Fedor Petrov Feb 18 '19 at 14:10
  • $\begingroup$ Thank you for the explanation! @FedorPetrov $\endgroup$ – Piccadilly Dough Feb 19 '19 at 17:14

We need to prove that $$(a_1a_2-b_1b_2)(a_1-1)(a_2-1)\geq(a_1-b_1)(a_2-b_2)(a_1a_2-1),$$ which is a linear inequality of $b_1$ and of $b_2$ and since $$1\leq b_1\leq a_1-1$$ and $$1\leq b_2\leq a_2-1,$$ it's enough to prove our inequality for $b_1\in\{1,a_1-1\}$ and $b_2\in\{1,a_2-1\},$

where $a_1\geq2$ and $a_2\geq2$.

  1. $b_1=b_2=1.$

We obtain an identity;

  1. $b_1=1$, $b_2=a_2-1$.

We need to prove that $$(a_1a_2-a_2+1)(a_2-1)\geq a_1a_2-1$$ or $$a_2(a_2-2)(a_1-1)\geq0,$$ which is obvious;

  1. $b_1=a_1-1$ and $b_2=1$.

This case a similar to the previous case;

  1. $b_1=a_1-1$ and $b_2=a_2-1$.

We need to prove that $$(a_1+a_2-1)(a_1-1)(a_2-1)\geq a_2a_2-1$$ or $$(a_1+a_2-2)(a_1a_2-a_1-a_2)\geq0$$ or $$(a_1+a_2-2)((a_1-1)(a_2-1)-1)\geq0.$$ Done!

  • $\begingroup$ Thank you so much for your detailed explanation of proof. I really appreciate it! $\endgroup$ – Piccadilly Dough Feb 19 '19 at 17:15
  • $\begingroup$ You are welcome! $\endgroup$ – Michael Rozenberg Feb 19 '19 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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