0
$\begingroup$

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.

$\endgroup$
2
  • 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$ Feb 18, 2019 at 14:10
  • $\begingroup$ Thank you for the explanation! @FedorPetrov $\endgroup$ Feb 19, 2019 at 17:14

1 Answer 1

1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Thank you so much for your detailed explanation of proof. I really appreciate it! $\endgroup$ Feb 19, 2019 at 17:15
  • $\begingroup$ You are welcome! $\endgroup$ Feb 19, 2019 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.