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 $$