Solution to quiz 2-I (section D version)

Suppose n = 3^k;
Q(n) = 8Q(n/3) + n^2
     = 8Q(3^(k-1)) + (3^k)^2
     = 8Q(3^(k-1)) + 9^k
     = 8[8Q(3^(k-2)) + 9^(k-1)] + 9^k
     = 8^2*Q(3^(k-2)) + 8*9^(k-1) + 9^k
     = ........

Q(3^k) = 8^k + Sigma(i=0 to i=(k-1))8^i*9^(k-i)
     = 8^k + 9^(k+1) - 9*8^k
k = log3(n)
==> Q(n) = 8^(log3(n)) + 9^(log3(n)+1) - 9*8^(log3(n))