Chapter 8.3, Problem 34E

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.

Find $f\left(n\right)$ when $n=4^k$ , where f satisfies the recurrence relation $f\left(n\right)=5f\left(n/4\right)+6n$, with $f\left(1\right)=1$ .