# Proving $(a+b)\log_2(a+b) \ge a\log_2 a +b\log_2 b +2a$ for positive integers $b \ge a$

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.

• Hint: check equality at $b=a$, then take derivatives of both sides with respect to $b$. May 22, 2021 at 4:40
• 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? May 22, 2021 at 4:46
• Yes, because this approach actually proves that the inequality holds for all real numbers $b\ge a$; the special case of integers $b$ follows. May 22, 2021 at 17:27

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$$.

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.

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