Chapter 8.3, Problem 29E

In Exercises 29-33, assume that f is an increasing function satisfying the recurrence relation $f\left(n\right)=af\left(n/b\right)+c{n}^d$, where $a\ge 1$ , b is an integer greater than 1, and c and dare positive real numbers. These exercises supply a proof of Theorem 2.

29. Show that if $a=b^d$ and $\omega$ is a power of b, then $f\left(n\right)=f\left(1\right)n^d+c{n}^d{\log }_{b}n$ .