# How to prove an implication about an upper bound mentioned in the proof of master theorem?

How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"? For given constant b and j, the implication in green makes sense. If the upper bound of j was fixed, the equation 4.23 follows directly. However, when n increases, the upper bound of j also increases, though is slower. It is where I find difficult to prove there always exists a value m > 0 such that for all n >= m, equation 4.23 is true.

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! – dkaeae Aug 16 at 12:56

The statement $$f = O(h)$$ just states that there exists a constant $$C>0$$ such that $$f(N) \leq Ch(N)$$ for all $$N$$ (some variants have this hold only for large enough $$N$$, but in most cases there is no difference). In your case, $$f(N) \leq CN^{\log_b a-\epsilon}$$ for all $$N$$. This holds for $$N = n/b^j$$ in particular, and implies that $$g(n) \leq C \sum_{j=0}^{\log_b n-1} a^j (n/b_j)^{\log_b a-\epsilon}.$$
As for the two different definitions of big O: suppose that $$f(N) \leq CN^{\log_b a-\epsilon}$$ holds only for $$N \geq N_0$$, and let $$M = \max(C,f(1),\ldots,f(N_0))$$. Then $$f(N) \leq MN^{\log_b a-\epsilon}$$.
• In the last paragraph I explain why $N_0$ isn’t necessary in this case. – Yuval Filmus Aug 16 at 3:08