# Proof that $\ln(n^2)(\ln(n) - 1) < n$ for all $n\in\mathbb{N}$

I would like to know which proof strategy to use when proving the next inequality: $\ln(n^2)(\ln(n) - 1) < n,\quad\forall n \in \mathbb{N}$. I have been trying to use this two proved inequalities $\dfrac{n}{n+1} < \ln(n+1) < n$ ,but it did not give me solution.

-
Hint: $log(n^2)(log(n)-1) \le 2 log(n)^2$. – Dan Brumleve Sep 10 '11 at 9:08
@Dan,I think that it is wrong approach – pedja Sep 10 '11 at 9:32
pedja, try $n \ge 14$. Can you show inductively that the inequality continues to be satified? Then check the finite cases. – Dan Brumleve Sep 10 '11 at 9:41
@pedja, please DO NOT CHANGE (substantially) THE QUESTION, it invalidates correct answers to the question as was asked. If you want to ask a different question, you can leave this one as is and go ask a different question. – Did Sep 11 '11 at 8:50
@pedja Also, I do not think that the [algebra] tag means what you take it to mean. The [algebra-precalculus] tag seems more appropriate (even though most solutions till now seem to employ calculus in some form). – Srivatsan Sep 11 '11 at 8:57

Define a function $u$ on $x>0$ by $u(x)=x-\log(x^2)(\log(x)-1)=x-2\log(x)^2+2\log(x)$. The goal is to prove that $u(n)>0$ for every positive integer $n$, let us prove the stronger statement that $u(x)\ge1$ for every real number $x\ge1$.

To do so, first note that $u'(x)=v(x)/x$ with $v(x)=x-4\log(x)+2$ and that $v'(x)=1-4/x$, hence $v$ is decreasing on $(1,4)$ and increasing on $(4,+\infty)$.

Since $v(4)=6-8\log(2)=.4548>0$, $v>0$ everywhere and $u$ is increasing. In particular, $u(x)\ge u(1)=1$ for every $x\ge1$.

Finally, for every positive integer $n$, $$\log(n^2)(\log(n)-1)\le n-1<n.$$

-
,I was looking for more "algebraic" proof but this looks nice also....I will wait bit more before accepting answer – pedja Sep 10 '11 at 13:10

Make the substituting $x = \log n$, so $x \geq 0$. The inequality now reads $$2x(x-1) < \exp(x).$$ All we have to do know is to take the Taylor expansion of $\exp(x)$ and stop at the right place. For example, $$1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} < \exp(x),$$ and it so happens that when $x \geq 0$, $$2x(x-1) < 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24}.$$ This can be verified formally using e.g. Sturm sequences (or by finding explicitly all the roots using the quartic formula).

-
,using quartic formula is not so elegant solution but may give positive result... – pedja Sep 11 '11 at 5:07
quartic formula – pedja Sep 11 '11 at 5:36

Here's a simple approach. Verify the inequality for the base cases $n=1$ and $n=2$; we will assume $n \geq 3$ from now on. Let us now make the substitution $x = \ln n$ (where $x \geq \ln 3 > 1$), and rewrite the inequality as $e^x \geq 2x(x-1)$.

Using the famous inequality $e^{t} \geq t+1$, we get $$e^{x- \frac{3}{2}} \geq x- \frac{1}{2}.$$ for all real $x$. Integrating between the limits $0$ and $x > 0$, we get: $$e^{x- \frac{3}{2}} - e^{-\frac{3}{2}} \geq \frac{1}{2}(x^2-x).$$ Rearranging this slightly (and dropping one term), we get $$e^x \geq \frac{e^{3/2}}{4} \cdot 2x(x-1),$$ which implies the claim since $\frac{e^{3/2}}{4} \geq 1.1 > 1$. (Note that the final step is valid only if $2x(x-1)$ is positive, but this is the true since $x \geq 1$.)

-
It is funny that the numerical evaluation your solution relies on, namely that $\log(2)<\frac34$, is exactly the one needed in my solution, although the rest of our proofs seem to use different arguments. – Did Sep 11 '11 at 7:18
@Didier That's true, I didn't see that till now. :-) There should be some explanation I guess... – Srivatsan Sep 11 '11 at 7:25
@SrivatsanNarayanan,Brilliant but not strictly algebraic since integration is involved – pedja Sep 11 '11 at 8:01
@pedja I do not know what Didier thinks, but my answer is: it depends. Since you did not (!) object to my first inequality $e^t \geq t+1$, if you are ok with using it, I can actually believe that there is an algebraic proof that uses only that inequality. Otherwise I cannot imagine any way... – Srivatsan Sep 11 '11 at 8:13
@pedja, I usually try to avoid thinking, it gives me headaches... More seriously, I wanted to draw your attention to the fact that the logarithm is not a priori an algebraic object (whatever that means), hence that your motto of a purely algebraic proof was odd, mathematically speaking. (As regards MO etiquette, you did not mention this requirement in the question itself and you gave no motivation for it). – Did Sep 11 '11 at 8:21