# Proof of the master thorem case with floors and b = 2

This question is related to my previous one.

Let the following recurrence relation be given: $$T(n)=aT(\lfloor n/b \rfloor)+f(n)$$ where $$a\geq 1, b > 1$$ and $$f(n) = \Theta(n^{\log_ba})$$. Then $$T(n) = n^{\log_ba} + \sum_{j=0}^{\lfloor \log_b n \rfloor - 1} a^{j}f(n_j) = n^{\log_ba} + g(n)$$. It should be proved that $$g(n) = \Omega(n^{\log_ba}logn)$$.

It's seems not to be a difficult problem as there is the proof of the similar one (for the upper bound and a presence of the ceiling operation in recursive calls) in the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein. But I found it becomes more difficult to deal with if $$b=2$$:

$$n_j = \begin{cases} n, & \text{if j = 0} \\ \lfloor n_{j-1}/b \rfloor, & \text{if j > 0} \end{cases}$$

$$n_j \geq n/b^{j} - \sum_{i=0}^{j-1}1/b^{i} \geq n/b^{j} - \sum_{i=0}^{\infty}1/b^{i} = n/b^{j} - b/(b-1)$$

By condtition, there is such constant $$c$$ that

$$g(n) \geq$$

$$c \sum_{j=0}^{\lfloor \log_b n \rfloor - 1}a^{j}(\frac{n}{b^{j}} - \frac{b}{b-1})^{log_ba} =$$

$$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{j}}{n}\frac{b}{b-1})^{log_ba} \geq$$ //where $$\frac{b^{j}}{n} \le 1$$

$$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor -1 }}{n}\frac{b}{b-1})^{log_ba} =$$

$$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor }}{n}\frac{1}{b-1})^{log_ba} \geq$$

$$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{1}{b-1})^{log_ba}$$

Note iff $$b = 2$$ than $$(1-\frac{1}{b-1})^{log_ba} = 0$$ and can not be denoted as an allowable constant in terms of $$\Omega$$ (it must be a positive one).

I tried to prove that particular case in another way, if $$n_j \geq \frac{n}{2^{j}} - (2 - \frac{1}{2^{j-1}})$$ (it is the sum of the geometric progression without the limit) but finally failed because of the same issue.

In fact, let $$b=1.5$$, we will have $$(1-\frac{1}{b-1})<0$$, in which case $$(1-\frac{1}{b-1})^{\log_ba}$$ does not even make much sense!
$$1-\frac{b^{j}}{n}\frac{b}{b-1} \geq 1-\frac{b^{\lfloor \log_bn \rfloor -1 }}{n}\frac{b}{b-1}$$
Can we find $$\Theta(\log n)$$ times when the left side is greater than, for example, $$\frac12$$? That should be enough to generate the factor $$\log n$$ needed.
Let us solve the following equation for the index $$j$$. $$1-\frac{b^{j}}{n}\frac{b}{b-1} \gt \frac12$$ We get $$j \lt \log_b\left(\frac{n(b-1)}{2b}\right)=\log_bn-\log_b\frac{2b}{b-1}=\frac{\log n}{\log b}-c_0$$ where constant $$c_0=\log_b\frac{2b}{b-1}$$.