2
$\begingroup$

I'm trying to solve the following summation:

$ n \sum_{i=0}^{\log_3 (n-1)} \log_3 \frac{n}{3^i} $

The last part is $\log (\frac{n}{3^i})$. I can't by the life of me figure this out. I know that it should equal this:

$ \sum_{i=0}^{\log_3n-1} n\log n - \sum_{i=0}^{\log_3n-1} n \log_3 3^i $

2 Answers 2

1

So using the law of logarithms, as you have already determined:

$n\sum_{i=0}^{\log_{3}(n-1)}{\log_{3}{\frac{n}{3^{i}}}}=n\left(\sum_{i=0}^{\log_{3}{(n-1)}}{\log_{3}(n)-\sum_{i=0}^{\log_{3}(n-1)}}i \log_{3}{3}\right)$

However, we have $\log_{3}{3}=1$, so the second term can simply be evaluated: $\sum_{i=0}^{\log_{3}(n-1)}i\log_{3}{3}=\sum_{i=0}^{\log_{3}(n-1)}i=\frac{\log_{3}(n-1)\times(\log_{3}(n-1)+1)}{2}$

The first term can be evaluated by noticing that $\log_{3}(n)$ is a constant, independent of $i$, and therefore can be rewritten:

$\sum_{i=0}^{\log_{3}(n-1)}\log_{3}(n)=\log_{3}(n)\sum_{i=0}^{\log(n-1)}1=\log_{3}(n)\times(\log_{3}(n-1)+1)$

Therefore the entire series can be rewritten:

$n\sum_{i=0}^{\log_{3}(n-1)}\log_{3}{\frac{n}{3^{i}}}=n\left(\log_{3}(n)\log_{3}(n-1)+\log_{3}(n)-\frac{\log_{3}(n-1)(\log_{3}(n-1)+1)}{2}\right)$

0

Hint:

$\log(n/3^{i})=\log(n)-i\log(3)$

Now you have an arithmetic series.