Recurrent Relation Problem

I am having trouble finishing this problem for finding a recurrent relation. The problem is:

$T(n)=8T(n/2) + n^3$, $T(1)=1$ ; find $T(n)$

So I am using iteration to generate a general formula for the equation and have managed to get to the following point after performing three iterations:

$8^3T(n/2^3) + n^3 + n^3+ n^3$

I make this out to be:

$8^kT(n/2^k) + n^3(1+1+1+.... 1^k-1)$

From here I struggle and do not quite know how to proceed to find the answer. If anyone can help me it would be much appreciated.

Solution 1:

Hint:

Make a change of variable:

$$n=2^m \\ T(n)=a(m)$$

This means that:

$$\frac{n}{2}=2^{m-1}$$

Then you should substitute it into the initial equation:

$$\begin{array}( T(n) & = & 8 T \left(\frac{n}{2} \right) &+&n^3 \\ \downarrow & ~ & ~\downarrow & ~ & \downarrow \\ a(m) & = & 8 a \left(m-1 \right) &+&2^{3m} \end{array}$$

Now you get a linear recurrence:

$$a(m)=8 a(m-1)+8^{m}$$

Do you know how to solve it?

Further hint:

Consider another sequence:

$$a(m)=8^{m} b(m)$$