# lg(n/n-1) inequality

I'm trying to solve an exercise from Introduction to Algorithms of Cormen - exrecise 4.3-3 on 3rd edition, which is 4.1-2 on 2nd edition.

Found a solution, which makes sense, but I don't understand one thing in it.

They write:

$$c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{1}{c'}\right)-c'\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)\right) \geq$$ $$\geq c'n\left(\lg{n}-2+\frac{1}{c'}-\frac{\lg(n-1)-1}{n}\right)$$

How did they transform the first line to the second line?

I tried to insert the right term expression into the left term parentheses, but got something else:

$$c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{1}{c'}\right)-c'\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)\right) \geq$$

$$\geq c'n\left(\lg{n}-\frac{\lg{n}}{n}+\frac{1}{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{\lg\left(\frac{n}{n-1}\right)}{n}+\frac{1}{c'}\right)=$$

$$= c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{\lg\left(\frac{n}{n-1}\right)-\lg{n}+1}{n}+\frac{1}{c'}\right)=$$

$$= c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right)$$

What am I missing here?

Can we say that $0<\frac{n}{n-1}<1$ and therefore $\lg(\frac{n}{n-1})<0$ ? And thus continue:

$$\geq c'n\left(\lg{n}-1-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right)$$

Here I can claim that

$$\lg(n-1)<n+1 \Rightarrow \frac{\lg(n-1)-1}{n}<1$$

If only I could have said $$\frac{\lg(n-1)-1}{n}>0$$

(of course, I cannot say that...) But if I could - then I'm almost finished - return to our inequality:

$$\geq c'n\left(\lg{n}-2+\frac{1}{c'}\right) \geq c'n\lg{n}$$

But, sadly, I've missed something over the lines.

Where am I wrong? How did the author of the solution that I have found did the transition?

# EDIT

On another thought, I can prove that $$\frac{\lg(n-1)-1}{n}>0$$

For big enough $n$, it's true that $\lg(n-1)>1$, therefore $\frac{\lg(n-1)-1}{n}>0$

So, everything fits in.

Now my questions are: 1. Am I correct? 2. I still don't understand how to reach the suggested solution I've mentioned at the beginning of my answer.

# EDIT 2

Well, when I read @fleablood 's answer, I realized that I made a stupid mistake. I should have written: $$1<\frac n{n-1} \le 2 \Rightarrow 0<\lg\left(\frac n{n-1}\right)\le1$$

And therefore, the transition from $$= c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right)$$

should be to

$$\geq c'n\left(\lg{n}-2-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right)$$

And that settles all my questions.

==== Now that I think of it I feel dumb ====

The key is $1 < \frac {n}{n-1} \le 2$ (equality holding if $n=2$) so

$0 < \log_2 \frac {n}{n-1}=\lg \frac {n}{n-1} \le 1$.

So $\lg{n}-1-\lg\left(\frac{n}{n-1} \right)\ge \lg{n} - 2$ and $\lg{n}-1-\lg(\frac{n}{n-1}) < \lg{n}-1$

so....

$c'n(\lg{n}-1-\lg(\frac{n}{n-1})+\frac{1}{c'})-c'(\lg{n}-1-\lg(\frac{n}{n-1})> c'n(\lg{n}-2+\frac{1}{c'})-c'(\lg{n}-1)$

(assuming $c'$ and $n$ are positive. I'm not sure why they didn't opt for a strict inequality.)

$c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{1}{c'}\right)-c'\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)\right) =$

$c'n\left(\lg{n}-2+\frac{1}{c'}\right)-c'\left(\lg{n}-1\right)+c'n-c'n\lg\left(\frac{n}{n-1}\right) +c'\lg\left(\frac{n}{n-1}\right)=$

$c'n\left(\lg{n}-2+\frac{1}{c'}-\frac{\lg(n-1)-1}{n}\right)+c'n-c'n\lg\left(\frac{n}{n-1}\right) +c'\lg\left(\frac{n}{n-1}\right)$

So (presuming $c', n > 0$ this is a matter of showing

$c'n-c'n\lg\left(\frac{n}{n-1}\right) +c'\lg\left(\frac{n}{n-1}\right)\ge 0$

[EDIT: D'oh. all values are positive so it is more than sufficient to prove $0 < \lg(\frac n{n-1}) \le 1$. Which it is if $1 < \frac n{n-1}=1+\frac 1{n-1} <$ base of $\lg$. Which is the case if base of $\lg \ge 2$. Presumably $\lg =\log_2$. My mistake was assuming NOTHING about the base until the very end putting off what should have been obvious from the start. Only at the end it became much more complicated.]

or $n + \lg(\frac n{n-1}) \ge n\lg(\frac n{n-1})$.

or $\lg (b^n\frac n{n-1}) \ge \lg ((\frac n{n-1})^n)$

or $b^n \ge (\frac n{n-1})^{n-1}$

Is $\lg = \log_2$?

If so... $1<\frac n{n-1} \le 2$ and $2^n \ge (\frac n{n-1})^n > (\frac n{n-1})^{n-1}$.

There's probably a more obvious way of "visually" seeing this ... but I'm missing it.

• Well, now you've convinced me that they didn't made a mistake in the solution... But I find it hard to believe that they hid all this in that innocent-looking transition :( – Zvika Jun 21 '18 at 20:55
• There's probably something I'm overlooking. What I did is easy but it's not do-it-in-your-head easy. – fleablood Jun 21 '18 at 21:53
• Maybe it is.... If we assume $0 \le \lg n{n-1} < 1$ is do-it-in-your-head-easy (because $1 < \frac n{n-1} < 2$ is do-it-in-your-head-easy) then .... oh, for eff sake.... – fleablood Jun 21 '18 at 21:57
• Great. Just note that you have a small typo in your last comment. Missing a \frac – Zvika Jun 22 '18 at 6:18
• yeah... well, comments aren't editable. – fleablood Jun 22 '18 at 6:22