SKEDSOFT

and thus we see that at depth ⌊logb n⌋, the problem size is at most a constant. From Figure 4.4, we see that

which is much the same as equation (4.6), except that n is an arbitrary integer and not restricted to be an exact power of b.We can now evaluate the summation

from (4.13) in a manner analogous to the proof of Lemma 4.3. Beginning with case 3, if af(⌈n/b⌉) ≤ cf(n) for n > b b/(b - 1), where c < 1 is a constant, then it follows that ajf(nj) ≤ cjf(n). Therefore, the sum in equation (4.14) can be evaluated just as in Lemma 4.3. For case 2 , we have. If we can show that  , then the proof for case 2 of Lemma 4.3 will go through. Observe that j = ≤ ⌊logb n⌋implies bj/n ≤ 1. The bound  implies that there exists a constant c > 0 such that for all sufficiently large nj,

since is a constant. Thus, case 2 is proved. The proof of case 1 is almost identical. The key is to prove the bound , which is similar to the corresponding proof of case 2, though the algebra is more intricate.

We have now proved the upper bounds in the master theorem for all integers n. The proof of the lower bounds is similar.