How do I solve this recurrence equation using the characteristics method?

Question

Solve the following recurrence equation using the characteristics equation where n is a power of 2:

$$T(n) = 7T\left(\frac{n}{2}\right) + 18\left(\frac{n}{2}\right)^2, T(1) = 0, n>1$$

I thought of converting it into a linear recurrence, which I almost managed to do:

$$2^k=n$$ $$T(2^k)=7T(2^{k-1})+18(2^{k-1})^2$$ $$T(m) = T(2^k)$$ $$T(m) = 7T(m-1) + 18(2^{m-1})^2$$

But this is definitely wrong because of the last term. Any workaround?

Answer 1

Expanding on my comment:

• let $n=2^k$ and define $a_k=T(2^k)$ then the recurrence becomes

$$T\left(2^k\right) = 7\, T\left(2^{k-1}\right) + 18 \cdot \left(2^{k-1}\right)^2\;\;\iff\;\; a_k = 7\,a_{k-1} + 18\cdot 2^{2k-2} \tag{1}$$

• divide $(1)$ by $2^{2k-2}=2^{2(k-1)}$ and define $b_k=\dfrac{a_k}{2^{2k}}$ then

$$ {\color{blue}{4}} \, \frac{a_k}{2^{2k-2} \cdot \color{blue}{4}} = 7\,\frac{a_{k-1}}{2^{2(k-1)}} + 18 \;\;\iff\;\; 4\,b_k = 7 b_{k-1} + 18 \tag{2} $$

Relation $(2)$ is a linear recurrence with constant coefficients, which can be solved with the usual methods. Or directly, writing it as $4\left(b_k + 6\right) = 7\left(b_{k-1}+6\right)$ shows that $c_k = b_k + 6$ is a geometric progression, so $\,c_k = c_0 \left(\frac{7}{4}\right)^k\,$, $\,b_k=c_k - 6\,$, $\,a_k = 2^{2k}b_k\,$, $T(n)=a_{\log_2 n}\,$.