Chapter 8.3, Problem 36E

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=2^k$ , where f satisfies the recurrence relation $f\left(n\right)=8f\left(n/2\right)+n^2$ with $f\left(1\right)=1$ .