In the book "An introduction to the Analysis of Algorithms" by R. Sedgewick and P. Flajolet, There is this exercise
Exercise 1.4 Develop a recurrence describing the quantity $C_{N+1} − C_{N}$ and use this to prove that $$C_N=\sum_{1\le k<N}(\lfloor\lg k\rfloor+2)$$
Where $C_N$ describes the recurrence relation of the number of compares performed by mergesort$$C_N=C_{\lfloor N/2\rfloor}+C_{\lceil N/2\rceil}+N$$
From the question I guessed that I should show that $$C_{N+1}-C_N = \lfloor\lg N\rfloor + 2$$ for all N. I have a problem generalizing to all $N$.
Here is what I got so far.
By assuming that $N = 2^n$ for some $n$, we can first quickly see that $$\lfloor (N+1)/2\rfloor=\lceil N/2\rceil =2^{n-1}$$ This directly helps us when using the recurrence relation for $C_N$ and $C_{N+1}$ and subtracting: $$\begin{align}C_{N+1}-C_N&=C_{\lfloor (N+1)/2\rfloor}+C_{\lceil (N+1)/2\rceil}-C_{\lfloor N/2\rfloor}-C_{\lceil N/2\rceil} + 1\\ &=C_{\lceil (N+1)/2\rceil}-C_{\lfloor N/2\rfloor} +1\\ &=C_{ 2^{n-1}+1}-C_{2^{n-1}}+1\\ (\text{keep applying})&= C_{ 2^{n-2}+1}-C_{2^{n-2}}+2 \\ &=...\\ &=C_{ 2^{n-n}+1}-C_{2^{n-n}}+n\\ &=C_2+n\end{align}$$
from the recurrence relation we can easily see that $C_2=2$, and since $n=\lg N$ we get $$C_{N+1}-C_N=\lg N + 2$$
This is valid only for $N$ being a power of $2$. I tried generalizing using induction somehow, but honestly I am stuck. Any help would be appreciated.
When $N$ is even we have $\lfloor(N+1)/2\rfloor=\lfloor N/2\rfloor$, so $C_{N+1}-C_{N}=C_{\lceil (N+1)/2\rceil}-C_{\lceil N/2\rceil} + 1$, or $$C_{2n+1}-C_{2n}=C_{n+1}-C_{n} + 1.$$ Similarly, when $N$ is odd $\lceil(N+1)/2\rceil=\lceil N/2\rceil$, so $$C_{2n+2}-C_{2n+1}=C_{n+1}-C_{n} + 1.$$ Now we can apply induction: if $N$ is even $$C_{N+1}-C_{N}=C_{2n+1}-C_{2n} = C_{n+1}-C_n + 1 = \lfloor \lg n\rfloor + 2 + 1 = \lfloor \lg n + 1\rfloor + 2 = \lfloor \lg(2n)\rfloor + 2=\lfloor \lg N\rfloor + 2,$$ and if $N$ is odd $$C_{N+1}-C_{N}=C_{2n+2}-C_{2n + 1} = C_{n+1}-C_n + 1 = \lfloor \lg n\rfloor + 2 + 1 = \lfloor \lg n + 1\rfloor + 2 = \lfloor \lg(2n)\rfloor + 2=\lfloor \lg(2n+1)\rfloor + 2=\lfloor \lg N\rfloor + 2.$$ Now, why is $\lfloor \lg(2n)\rfloor = \lfloor\lg(2n+1)\rfloor$? This is because if $\lfloor\lg(2n+1)\rfloor$ were larger, there would be a power of 2, which is greater than $2n$, but not greater than $2n+1$.