Proof of Mergesort $N$ elements with $N \log N + O(N)$ comparisons In the book "An introduction to the Analysis of Algorithms", written by Robert Sedgewick and Philippe Flajolet during the proof of the

Theorem 1.1: (Mergesort) To sort an array of N elements, Mergesort uses $N \log N + O(N)$ comparions.

It contains the following part:

To get an indication for the nature of the solution to this recurrence, we consider the case when N is a power of 2:


$C_{2^n} = 2C_{2^n-1} + 2^n$ for $n \geq 1$ with $C_1 = 0$.


Dividing both sides of this equation by $2^n$, we find that
$$
\frac{C_{2^n}}{2^n} = \frac{C_{2^n-1}}{2^{n-1}} + 1 = \frac{C_{2^n-2}}{2^{n-2}} + 2 = \frac{C_{2^n-3}}{2^{n-3}} + 3 = ... = \frac{C_{2^0}}{2^0} + n = n.
$$

I can't understand the trick behind incrementing the right side of the term (+1, then +2, then +3).
Why does the change of the left side lead to the increment on the right side?
Any help is kindly appreciated.

You basically use the fact $C_{2^n}=2C_{2^{n-1}}+2^n$ for all $n\geq 1$ recursively (I think you meant $2^{n-1}$ as index and not $2^n-1$). Dividing everything by $2^n$ yields
\begin{align}
\frac{C_{2^n}}{2^n} &= \frac{2C_{2^{n-1}}+2^n}{2^n} = \frac{2C_{2^{n-1}}}{2^n} + \frac{2^n}{2^n} = \frac{C_{2^{n-1}}}{2^{n-1}}+ 1 \\
&=\frac{2C_{2^{n-2}}+2^{n-1}}{2^{n-1}}+ 1  =\frac{2C_{2^{n-2}}}{2^{n-1}}+ 1+1 =\frac{C_{2^{n-2}}}{2^{n-2}}+ 2
\end{align}
I hope you see the recursive pattern now. If you go on until the exponent in the index has been reduced to $0$ you get:
$$
\frac{C_{2^0}}{2^0} + n = \frac{0}{1} + n = n
$$
