Can't solve a recurrence

Question

I am trying to solve the following recurrence:

$$T(n) = 9T(n/3)+n^2$$

If I use the master method, I get $n^2\log{n}$

But, I am trying to solve it using substitution. When I try solving it this way, however, I run into trouble. After I roll out the substitution for a few times, I get the following formula:

$$T(n) = 9^kT(n/3^k)+n^2\sum_{i=1}^k3^{j-1}$$

I've tried to simplify the summation several ways, but I don't think I am understanding what the next step should be. When I simplify the problem, I keep getting the wrong answer. I know I should eventually set $k$ to be equal to some logarithm so I an reach the base case for T, but right now my main issue it figuring out how to simplify the summation. I am quite bad at simplifying summations, so any detailed steps are greatly appreciated.

Answer 1

Your summation is wrong. It should be

$$T(n) = 9^k T(n / 3^k)+ \sum_{i=1}^k n^2$$

This is because $(n / 3^k)^2 = n^2 / 9^k$ so you get cancellations.

Answer 2

$$T(n)-9T(n/3)=n^2$$ $$9^kT(n)-9^{k+1}T(n/3)=9^kn^2$$ $$9^kT(n/3^k)-9^{k+1}T(n/3^{k+1})=n^2$$ $$\sum_{k=0}^{\lfloor{\log_3(n)}\rfloor}9^kT(n/3^k)-9^{k+1}T(n/3^{k+1})=n^2(\lfloor{\log_3(n)}\rfloor+1)$$ $$T(n)-9T(n/3)+9T(n/3)-9^2T(n/3^2)+....-9^{\lfloor{\log_3(n)}\rfloor}T(n/3^{\lfloor{\log_3(n)}\rfloor})=n^2(\lfloor{\log_3(n)}\rfloor+1)$$ $$T(n)=n^2(\lfloor{\log_3(n)}\rfloor+1)+9^{\lfloor{\log_3(n)}\rfloor}T(n/3^{\lfloor{\log_3(n)}\rfloor})$$ $$=n^2\log_3(n)+O(n^2T(n/3^{\lfloor{\log_3(n)}\rfloor}))$$ $$=n^2\log_3(n)+O(n^2T(c))$$ $$\text{Where } 0<c<3$$

Answer 3

The summation seems particularly "nice" if $n$ is a power of $3$, so lets assume $n=3^k$, then $$T(3^k)=3^2T(3^{k-1})+3^{2k}$$ and $$T(3^{k-1})=3^2T(3^{k-2})+3^{2k-2}$$ So by susbstitution: $$T(3^k)=3^2(3^2T(3^{k-2})+3^{2k-2})+3^{2k}=3^4T(3^{k-2})+2*3^{2k}$$ Now, $$T(3^{k-2})=3^2T(3^{k-3})+3^{2k-4}$$So $$T(3^k)=3^4(3^2T(3^{k-3})+3^{2k-4})+2*3^{2k}=3^6T(3^{k-3})+3*3^{2k}$$ In general $$T(3^k)=3^{2a}T(3^{k-a})+a*3^{2k}$$ for any natrual $a$ (can be easily verified via induction), so if we set $a=k$, we get $$T(3^k)=3^{2k}T(1)+k*3^{2k}$$ Now by backwards substituting $k=\log_3(n)$, we get that $$T(n)=n^2T(1)+n^2\log_3(n)$$