I came across this inequality in a graph theory book, couldn't figure how to prove it.


$n$ and $k$ are both positive integers. (Amount of vertices and minimum degree if that matters.)

  • 1
    $\begingroup$ Are you familiar with the inequality $(1 + \tfrac1x)^{x} < e$? $\endgroup$ – Mees de Vries Oct 5 '18 at 9:57
  • $\begingroup$ No but if the proof involves it I would gladly learn it. $\endgroup$ – Fuseques Oct 5 '18 at 9:59
  • $\begingroup$ Correction: that inequality holds for positive $x$, and the reverse inequality for negative $x$. Now apply the inequality to $-n/(k+1)$... do you see how to go form there? $\endgroup$ – Mees de Vries Oct 5 '18 at 10:18
  • $\begingroup$ hmmmm no sorry... $\endgroup$ – Fuseques Oct 5 '18 at 10:43
  • $\begingroup$ Are you familiar with the inequality $1+x \leq e^x$? This is true for any $x \in \mathbb{R}$, and the equality holds if and only if $x = 0$. Geometrically, this follows from the fact that $e^x$ is strictly convex and $y=x+1$ is the tangent line at $x = 0$ $\endgroup$ – Sangchul Lee Oct 5 '18 at 11:03

Starting from the well know inequality $\log(1+x)<x$ for $x\neq 0$ (proof, proof), we get \begin{align} \ln\left(1-\frac{k+1}{n}\right)&<-\frac{k+1}n\\ \frac n{k+1}\ln\left(1-\frac{k+1}{n}\right)&<-1\\ \frac{n\ln(k+1)}{k+1}\ln\left(1-\frac{k+1}{n}\right)&<-\ln(k+1)\\ \ln\left(1-\frac{k+1}{n}\right)^{n\ln(k+1)/(k+1)}&<-\ln(k+1)\\ \left(1-\frac{k+1}{n}\right)^{n\ln(k+1)/(k+1)}&<e^{-\ln(k+1)}\\ n\left(1-\frac{k+1}{n}\right)^{n\ln(k+1)/(k+1)}&<ne^{-\ln(k+1)}\\ \end{align}

  • $\begingroup$ Can you please explain how you derived the 4th line from the 3rd? is there some rule that if $$ab < c$$ then $$b^a < c$$? seems not right, so probably something else? $\endgroup$ – Fuseques Oct 6 '18 at 5:27
  • $\begingroup$ $a\ln (b)=\ln (b^a) $ $\endgroup$ – Fabio Lucchini Oct 6 '18 at 5:29
  • $\begingroup$ oh right, thank you! $\endgroup$ – Fuseques Oct 6 '18 at 5:49

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.