Can't solve a recurrence 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. 
 A: 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.
A: 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)$$
A: $$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$$
