$$T(1) = 2$$ $$T(n) = T(\frac{n}{3}) + 6^n \text{ For n > 1}$$
I tried using the substitution method to find it's closed form but I even from there, I could not figure out how to find its bound. My working:
$k = 1$ $$T(n) = T(\frac{n}{3}) + 6^n $$ $k = 2$ $$T(n) = T(\frac{n}{9}) + (6^{\frac{n}{3}})+(6^n) $$ $k = 3$ $$T(n) = T(\frac{n}{27})+ (6^{\frac{n}{9}}) + (6^{\frac{n}{3}})+(6^n) $$ $k = 4$ $$T(n) = T(\frac{n}{81}) + (6^{\frac{n}{27}}) + (6^{\frac{n}{9}}) + (6^{\frac{n}{3}})+(6^n) $$
From the pattern, I can guess that it has the following recurrence
$$T(n) = T(\frac{n}{3^k}) + (k)(6^n) $$
Solving for $k$ we have
$1 = \frac{n}{3^k}$
$3^k = n$
$\log{_3}{n} = k$
Substituting all the k we have
$T(n) = 2 + 6^n\log{_3}{n}$
I'm stuck over here. Can master theorem apply for this case? Is there an upperbound for $k^n$ ?
Hint:
$$6^n > n^{\log_3 2}$$
Can you take another look at the Master theorem cases ?