# Find the tight bound for the recurrence relation $T(n) = T(\frac{n}{3}) + 6^n$

$$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$ ?

• You messed up substitution on step $k=2$. It should yield $T(n)=\sum_{i=0}^{\log_3 n}6^{n/3^i}$ instead. The terms drop off so fast in value that I see no reasonable way to sum them compactly. Basically we have $T(n)\sim 6^n$ - only the first term matters.
– A.S.
Commented Nov 17, 2015 at 3:35

$$6^n > n^{\log_3 2}$$
• Apologies, can you give me more hints? Looking at the master theorem, I will need to find an upper bound for $6^n$. I realized that the upper bound would be an exponential upper bound. I don't see how the master theorem works in this case Commented Nov 16, 2015 at 19:11
• Case $3$, where $f(n) \in \Omega(n^{\log_b a+ \epsilon})$, with $\epsilon > 0$. In our case $f(n) = 6^n, b = 3, a= 1$ and I took the liberty of setting $\epsilon = 1$. Commented Nov 16, 2015 at 19:13