Justifying a claim in the proof of the master theorem
Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C&gt;0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the maximum value of $f(n)/n^{\log_b a - \epsilon}$ over all positive integers $n &lt; N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq \max(M,C) n^{\log_b a - \epsilon}$ holds for all integer $n \geq 1$. Therefore
$$
g(n) = \sum_{j=0}^{\log_b n-1} a^j f(n/b^j) \leq \max(M,C) \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} = O\left( \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} \right).
$$