This is a problem from "Analysis of Algorithms" by R. Sedgewick. In the context of the merge sort:
$C_N = N\cdot lg(N)$
Exercise 1.4
Develop a recurrence describing the quantity $C_{N+1} − C_N$ and use this to prove that: $C_N = \sum_{k=1}^N(\lfloor lg(k) \rfloor + 2)$
I don't understand what is meant by "Develop a recurrence ..." in this context. My thoughts:
$$C_{N+1} - C_N = (N+1) \cdot lg(N+1) - N \cdot lg(N) = N \cdot (lg(N+1) - lg(N)) + lg(N + 1) = lg( (1 + \frac{1}{N})^N) + lg(N + 1)$$
As $N$ goes to infinity take the limit: $$ \lim_{N \to \infty} (1 + \frac{1}{N})^N = e$$
Then: $$C_{N+1} - C_N = lg(N + 1) + lg(e)$$
Let's represent $C_N$ as a sum, taking into account that $C_0 = 0$: $$C_N = \sum_{k=1}^N (C_k - C_{k-1}) = \sum_{k=1}^N (lg(k) + lg(e))$$
It is clear that the floor underestimates $lg(n)$ and there are some "leftovers". So may be those leftovers plus $lg(e)$ on average would be equal to 2. How would rigorous proof look like?
Not rigorous proof: note that $0 < leftovers < 1$, log is monotone increasing so on average it would be equal to 0.5. Then 0.5 + $lg(e) = 0.5 + 1.44$ almost 2.
Seems unlikely at first glance.
This means that
$\begin{array}\\ \lfloor \ln(n) \rfloor +2 &=(n+1)\ln(n+1)-n\ln(n)\\ &=(n+1)(\ln(n)+\ln(1+1/n))-n\ln(n)\\ &=n(\ln(n)+\ln(n)+(n+1)\ln(1+1/n))-n\ln(n)\\ &=(n+1)\ln(1+1/n))+\ln(n)\\ &=(n+1)(\frac1{n}-\frac1{2n^2}+O(\frac1{n^3}))+\ln(n)\\ &=(1-\frac1{2n}+O(\frac1{n^2}))+(\frac1{n}-\frac1{2n^2}+O(\frac1{n^3}))+\ln(n)\\ &=\ln(n)+(1+\frac1{2n}+O(\frac1{n^2}))\\ \text{or}\\ \lfloor \ln(n) \rfloor &=\ln(n)-1+\frac1{2n}+O(\frac1{n^2})\\ \end{array} $
However, if $n = e^m+c$ where $m$ is large and $0 < c < 1$, then
$\begin{array}\\ \ln(n) &=\ln(e^m+c)\\ &=\ln(e^m)+\ln(1+ce^{-m})\\ &=m+ce^{-m}-tc^2/(2e^{2m})\\ \end{array} $
where $0 < t \le 1$.
Therefore $\lfloor \ln(n) \rfloor = m $ and $\ln(n)-1 =m+ce^{-m}-tc^2/(2e^{2m})-1 \lt m $ for $ce^{-m} < 1$.