Solving a recurrence relation when $n$ is a power of $7$

Question

I'm working through some recurrence relation examples and am struggling with this question that assumes inputs of $n$ are powers of $7$.

Essentially we have

$T(n) = T({\lfloor}n/7{\rfloor}) + \log_{3}(n)$

$T(1) = 0$

Using the bottom up method I have found the following

$T(7) = T(1) + \log_{3}(7) = \log_{3}(7)$

$T(49) = T(7) + \log_{3}(49) = \log_{3}(7) + \log_{3}(49)$

$T(343) = T(49) + \log_{3}(343) = \log_{3}(7) + \log_{3}(49) + log_{3}(343)$

I'm struggling to turn this into an equation though. I can see that essentially we have

$T(n) = \log_{3}(7^1) + \log_{3}(7^2) + ... + \log_{3}(7^k)$ where $7^k = n$.

How would I transform that logic into an equation?

Factor out the exponents by $\log_a(b^k)=k\log_a(b)$. Then use $\sum\limits_{i=1}^{k} i=\frac{k(k+1)}{2}$. — Alexey Burdin, Aug 21 '20 at 05:17

score 1 · Accepted Answer · answered Aug 21 '20 at 06:14

It seems more helpful to consider the function

$f(0) = 1$

$f(n + 1) = f(n) + \log_3(7^{n + 1}) = f(n) + (n + 1) \log_3(7)$

Here, we have $f(n) = T(7^n)$.

Then it is immediate that $f(n) = 1 + \sum\limits_{i = 1}^n n \log_3(7) = 1 + \log_3(7) \sum\limits_{i= 1}^n n$. Using the identity $\sum\limits_{i = 1}^n n = \frac{n (n + 1)}{2}$, we have

$f(n) = 1 + \frac{n(n+1) \log_3(7)}{2}$

hence

$T(n) = 1 + \frac{\log_7(n) (\log_7(n) + 1) \log_3(7)}{2} = 1 + \frac{\log_3(n) (\log_7(n) + 1)}{2}$ whenever $n$ is a power of 7.

I think you mean i not n when evaluating the sum :) – Henry Lee Aug 21 '20 at 10:54 — Henry Lee, Aug 21 '20 at 10:54

Solving a recurrence relation when $n$ is a power of $7$

1 Answers1