Not understanding the steps in Simplifying a Series

Question

I am hoping someone can explain why the second step has a $$o(\lg^k{n})$$ and then in the next step how the Riemann sum is simplified and the change of sign.

$$ B = \sum_{j=0}^{\log_b{n}-1}\lg^k\frac{n}{b^j} = \sum_{j=0}^{\log_b{n}-1}\Big(\lg^k{n} - o(\lg^k{n})\Big) = \log_b{n}\lg^k{n} + \log_b{n} \cdot o(\lg^k{n}) = \Theta(\log_b{n}\lg^k{n}) = \Theta(\lg^{k+1}{n}) \\ $$

Thank you,

Answer 1

I'll play around and see what happens.

$\begin{array}\\ B &= \sum_{j=0}^{\log_b{n}-1}\lg^k\frac{n}{b^j}\\ &= \sum_{j=0}^{\log_b{n}-1}\left(\lg\frac{n}{b^j}\right)^k\\ &= \sum_{j=0}^{\log_b{n}-1}\left(\lg(n)-j\lg(b)\right)^k\\ &= \sum_{j=0}^{\log_b{n}-1}\lg^k(n)\left(1-\frac{j\lg(b)}{\lg(n)}\right)^k\\ &= \lg^k(n)\sum_{j=0}^{\log_b{n}-1}\left(1-\frac{j}{\log_b(n)}\right)^k\\ &= \lg^k(n)\sum_{j=0}^{\log_b{n}-1}\left(1-c(j)\right)^k \qquad\text{where }0 \le c(j) < 1\\ &= \lg^k(n)\sum_{j=0}^{\log_b{n}-1}\left(d(j)\right)^k \qquad\text{where }0 \lt d(j) \le 1\\ &= \lg^k(n)\sum_{j=0}^{\log_b{n}-1}e(j) \qquad\text{where }0 \lt e(j) \le 1\\ \end{array} $

Therefore $B < \log_b(n)\lg^k(n) = O(\lg^{k+1}(n)) $ where the constant in the big-oh depends on the base implied by $\lg$ (probably 2).

To get an approximation for the sum, let $v = \log_b(n)$. Then

$\begin{array}\\ \sum_{j=0}^{\log_b{n}-1}\left(1-\frac{j}{\log_b(n)}\right)^k &=\sum_{j=0}^{v-1}\left(1-\frac{j}{v}\right)^k\\ &\approx v\int_0^1 (1-x)^k dx \qquad\text{since }\left(1-\frac{j}{v}\right)^k \approx v\int_{j/v}^{(j+1)/v} (1-x)^kdx\\ &= v\int_0^1 x^k dx\\ &=\frac{v}{k+1}\\ &=\frac{\log_b(n)}{k+1}\\ \end{array} $

so, since $\log_b(n) =\frac{\lg(n)}{\lg(b)} $, $B \approx \lg^k(n)\frac{\log_b(n)}{k+1} = \lg^{k+1}(n)\frac{1}{\lg(b)(k+1)} =\Theta(\lg^{k+1}(n)) $.

Answer 2

We are not given any constraint on $b$, but for simplicity assume $b>0$ since otherwise $\log_b$ is a bit difficult to define. I also assume that $o()$ relates to $n\to\infty$.

The term $\log^k n/b^j =(\log n-j\log b)^k$. This has a lead term $\log^k n$ and lower order terms in powers of $\log n$, such as $\log^{k-1} n$, with $j\log b$ being a constant for each $j$. This is what justifies the $o(\log^k n)$.

It's the next step which seems dubious to me. We take a sum of $\log_b n$ separate $o(\log^k n)$'s and say that's $\log_b n\cdot o(\log^k n)$. In other words, we have infinitely many functions $f_j(n)$, and each is in $o(\log^k n)$, i.e., each satisfies $\lim_{n\to\infty} |f_j(n)|/\log^k n=0$, and we want to infer then that $\sum_{j=0}^{\log_b n} f_j(n) = \log_b n\cdot o(\log^k n)$, i.e., $\lim_{n\to\infty} |\sum_{j=0}^{\log_b n} f_j(n)|/(\log_b n\log^k n)=0$. Without more information on the $f_j$'s, that's not a good inference.

For example, we can have $f_j(n)=g_jh(n)\log_b n\log^k n$, where $g_j$ is arbitrary and $h(n)\log_b n\to0$. We can have $g_j=e^j$ for example, and $h=1/(\log_b n)^2$. Then $$\left(\sum_{j=0}^{\log_b n} f_j(n)\right)/\log^k n = h(n)\log_b n\sum_{j=0}^{\log_b n} e^j= {1\over \log_b n}{e^{\log_b n}-1\over e-1}$$ This doesn't go to zero.

I think the proof needs a do-over.

Answer 3

This series comes up when proving a generalised Case 2 of the Master Theorem, Exercise 4.6-2 in CLRS "Introduction to Algorithms". I will assume $b>1$ and $k\geq 0$ as these are presupposed by the theorem. Note both $b$ and $k$ are constants. Specifically the generalised Case 2 states that if $T(n)=aT(n/b)+f(n)$ where $f(n)=\Theta(n^{\log_b(a)}\lg^k(n))$ where $a\geq 1$, $b>1$, $k\geq 0$ and $f(n)$ is asymptotically positive then $T(n)=\Theta(n^{\log_b(a)}\lg^{k+1}(n))$.

You can show using a recursion tree that;

$$T(n)=\Theta(n^{\log_b(a)})+\sum_{j=0}^{\log_b(n)-1} a^j f(n/b^j)$$

(See Ch 4.6 of CLRS Intro to Algorithms for details)

Then you use the fact that

$$f(n)=\Theta(n^{\log_b(a)}\lg^k(n))$$

to substitute;

$$f(n/b^j)=\Theta((n/b^j)^{\log_b(a)}\lg^k(n/b^j))$$

and you wind up at the series given in this question.

If you can show the series is $\Theta(\lg^{k+1}(n))$ then the generalised version of the Master Theorem Case 2 follows.

Here is how I proved that the series is $\Theta(\lg^{k+1}(n))$

$\begin{aligned} \sum_{j=0}^{\log_b(n)-1} \lg^k(n/b^j) \leq \sum_{j=0}^{\log_b(n)-1} \lg^k(n) = \log_b(n) \lg^k(n) = O(\lg^{k+1}(n)) \end{aligned}$

Then we want to lower bound the series.

$\begin{aligned} \sum_{j=0}^{\log_b(n)-1} \lg^k(n/b^j) \geq \sum_{j=0}^{ \lceil \log_b(n)/2 \rceil } \lg^k(n/b^j) \end{aligned}$

Observe that

$j \leq \lceil \log_b(n)/2 \rceil $

implies

$\begin{aligned} b^j & \leq b^{\lceil \log_b(n)/2 \rceil } \\ & \leq b^{\log_b(n)/2+1} \\ & =b\sqrt{n} \\ & \leq n^{1/2+\epsilon} \end{aligned}$

where the last step holds for sufficiently large n.

Therefore

$n/b^j \geq n/(n^{1/2+\epsilon})=n^{1/2-\epsilon}$

which implies

$\lg(n/b^j) \geq \lg(n^{1/2-\epsilon})=(\frac{1}{2}-\epsilon)\lg(n)$

and then we have

$\lg^k(n/b^j) \geq (\frac{1}{2}-\epsilon)^k \lg^k(n)$

and then we have

$\begin{aligned}\sum_{j=0}^{\log_b(n)-1} \lg^k(n/b^j) & \geq \sum_{j=0}^{\lceil \log_b(n)/2 \rceil } \lg^k(n/b^j) \\ & \geq \sum_{j=0}^{\lceil \log_b(n)/2 \rceil } \left (\frac{1}{2}-\epsilon \right )^k \lg^k(n) \\ &= \left (\frac{1}{2}-\epsilon \right )^k (\lceil \log_b(n)/2 \rceil +1) \lg^k(n) \\ & \geq \left (\frac{1}{2}-\epsilon \right )^k \cdot \left (\frac{1}{2} \right) \cdot \log_b(n) \lg^k(n) \\ & = \left (\frac{1}{2} \right ) \left (\frac{1}{2}-\epsilon \right )^k \lg(b) \lg(n) \lg^k(n) \\ & = \left (\frac{1}{2} \right ) \left (\frac{1}{2}-\epsilon \right )^k \lg(b) \lg^{k+1}(n) \\ &= \Omega(\lg^{k+1}(n))\end{aligned}$

Therefore

$\sum_{j=0}^{\log_b(n)-1} \lg^k(n/b^j) = \Theta (\lg^{k+1}(n))$