Recurrence Relation: $B(n) = 5\cdot B(n/3) + c(n^2)$ I'm working on deriving this recurrence relation in the form $O(n^d)$ for some value of d:
$B(n) = 5\cdot B(\frac{n}{3}) + cn^2$
The initial condition is:
$B(1) = c$
I'm having trouble incorporating the n^2 into my derivation. This is what I have so far: 
We set $n = 3^k$
$5^k(1 + \frac{5}{3} + (\frac{5}{3})^2 + ... + (\frac{5}{3})^k$
Which leads to $3^k\cdot (\frac{10}{3})^k$ -> $5^k = 5^{log_3n}$ -> $log_{3}n = k$
Not sure how to derive the final running time to be $O(n^d)$. Any help would be appreciated! 
 A: $$
B(3^{\log_3 n})-5B(3^{\log_3 \frac n3})=c n^2
$$
now calling $B'(u) = B(3^u)$ with $u = \log_3 n$ we have
$$
B'(u)-5B'(u-1) = c 9^u
$$
this is a linear recurrence with solution
$$
B'(u) = B'(u)_h + B'_p(u)\\
B'_h(u)-5B'_h(u-1) = 0\\
B'_p(u)-5B'_p(u-1) = c 9^u
$$
with $B'_h(u) = C_0 5^{u-1}$ Now making $B'_p(u) = C_0(u)5^{u-1}$ and substituting into the particular we get the recurrence
$$
C_0(u)-C_0(u-1) = c 9^u5^{u-1}
$$
with solution
$$
C_0(u) = c\left(\frac{45}{4}\left(\frac 95\right)^u-1\right)
$$
then
$$
B'(u) = C_0 5^{u-1} + c\left(\frac{45}{4}\left(\frac 95\right)^u-1\right)5^{u-1}
$$
hence
$$
B(n) = \frac{1}{20}\left((4C_0-45c)5^{\log_3 n}+45 c n^2\right)
$$
and after incorporating the initial conditions we have
$$
B(n) = \frac c4\left(9n^2-5^{\log_3 (3n)}\right)
$$
A: \begin{equation}
\begin{split}
B(n) &= 5B(\frac{n}{3}) + cn^2 \\
&= 5(5B(\frac{n}{3^2}) + c(\frac{n}{3})^2) + cn^2 \\
&= 5^2B(\frac{n}{3^2}) + c[5(\frac{n}{3})^2 + n^2] \\
&= 5^2(5B(\frac{n}{3^3}) + c(\frac{n}{3^2})^2) + c[5(\frac{n}{3})^2 + n^2] \\
&= 5^3B(\frac{n}{3^3}) + c[5^2(\frac{n}{3^2})^2 +5(\frac{n}{3})^2 + n^2] \\
&= \vdots \\
&= 5^kB(\frac{n}{3^k}) + c[5^{k-1}(\frac{n}{3^{k-1}})^2 + \ldots +5(\frac{n}{3})^2 + n^2]\\
&= 5^kB(\frac{n}{3^k}) + cn^2 \sum_{i=0}^{k-1} 5^i(\frac{1}{3^i})^2 \\
&= 5^kB(\frac{n}{3^k}) + cn^2 \sum_{i=0}^{k-1} (\frac{5}{3^2})^i \\
&= 5^kB(\frac{n}{3^k}) + cn^2  \frac{1-(\frac{5}{9})^k}{1- \frac{5}{9}}
\end{split}
\end{equation}
But $B(1) = c$ hence for  $k=\log_3 n$
$$B(n) = 5^{\log_3 n}c + \frac{9}{4} cn^2  (1-(\frac{5}{9})^{\log_3 n})$$
It seems that the dominating term is $O(n^2)$.
