Understanding Master Method's Case 2
Suppose that $T(n) = aT(n/b) + n^{\log_b a}$ and $T(1) = 1$. Now consider some $n$ which is a power of $b$, say $n = b^k$. The formula gives
$$
\begin{align*}
T(n) &amp;= aT(n/b) + n^{\log_b a} \\ &amp;=
a^2T(n/b^2) + a(n/b)^{\log_b a} + n^{\log_b a} \\ &amp;=
a^3T(n/b^3) + a^2(n/b^2)^{\log_b a} + a(n/b)^{\log_b a} + n^{\log_b a} \\ &amp;=
\cdots \\ &amp;=
a^kT(n/b^k) + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &amp;=
a^k + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &amp;=
a^k(n/b^k)^{\log_b a} + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a}.
\end{align*}
$$
There are $k+1 = \log_b n + 1$ terms in the final formula. Miraculously, all of them are equal to $n^{\log_b a}$! (Work that out on your own.)