2
$\begingroup$

On the 6th page of the paper "On Induced Subgraphs of the Cube" (PDF link via usdc.edu) (precisely: the last line of Lemma 4.1) the author uses an inequality: $$(a+b)\log_2(a+b) \ge a\log_2 a +b\log_2 b +2a $$ where $b \ge a$ is known.

I'm not sure how that holds. Can someone explain this calculation to me?

Additional information: $a$ and $b$ are number of vertices of graph (respectively $|V_1|$ and $|V_2|$ in the paper) so they are both positive integers.

$\endgroup$
3
  • 1
    $\begingroup$ Hint: check equality at $b=a$, then take derivatives of both sides with respect to $b$. $\endgroup$ May 22, 2021 at 4:40
  • $\begingroup$ Ah yes, so that means the LHS increases more rapidly than the RHS as a function of $b$ and the inequality holds. Just to make sure things are alright, is it okay to treat $b$ as a continuous variable in this case? $\endgroup$ May 22, 2021 at 4:46
  • $\begingroup$ Yes, because this approach actually proves that the inequality holds for all real numbers $b\ge a$; the special case of integers $b$ follows. $\endgroup$ May 22, 2021 at 17:27

2 Answers 2

4
$\begingroup$

With the substitution $b=ka$, $k \ge 1$, the inequality becomes $$ (k+1)a \left(\log_2 (k+1) + \log_2 a \right) \ge a \log_2 a + k a \left( \log_2 k + \log_2 a \right) + 2a $$ which reduces to $$ (k+1) \log_2(k+1) \ge k \log_2 k + 2 $$ or $$ \frac{(k+1)^{k+1}}{k^k} \ge 4 \, . $$ The last inequality is true for $k\ge 1$ because $$ \frac{(k+1)^{k+1}}{k^k} = (k+1) \left( 1 + \frac 1k \right)^k \ge 2 \cdot 2 = 4 $$ (using the binomial formula or Bernoulli's inequality for the second factor).

The fact that $a$ and $b$ are integers is not needed for the estimate, only that $b \ge a > 0$.

$\endgroup$
-1
$\begingroup$

This is true for naturals (The cited paper is on graph theory.), as the result of the command of Mathematica

NMinimize[{(a + b)*Log[2, a + b] - a*Log[2, a] - b*Log[2, b] - 2 a, 
b >= a &&{a, b} \[Element] PositiveIntegers}}, {a, b}]

$\{3.552713678800501\cdot 10^{-15},\{a\to 4,b\to 4\}\}$

shows.

$\endgroup$
1
  • $\begingroup$ +1 Because this result is wrong and it demonstrates that one cannot use a CAS' result for a proof blindly without deeper investigation. $\endgroup$
    – miracle173
    May 22, 2021 at 16:41

You must log in to answer this question.

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