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.)
====old answer ====
$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.