# Justifying a claim in the proof of the master theorem

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.

My argument is as follows:

Claim: $$g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$$.

$$g(n)=\sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i)$$

Now by the definition of big O, we have that $$\exists c\in\mathbb{R}, N'\in \mathbb{R }$$ such that $$\forall n/b^j>N'$$, we have that $$f(n/b^j)

This implies that $$\forall n>N'b^{\log_bn-1}$$

$$g(n)= \sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i) \leq \sum_{i=0}^{\log_{b}(n)-1}a^ic(n/b^i)^{\log_b{a}-\epsilon} \leq c\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}$$

Which implies that $$g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$$ with $$M=c$$ and $$N=N'b^{\log_bn-1}$$.

Have I found the correct $$c$$ and $$N$$ to prove this claim for the upper bound of $$g(n)$$ and is this proof valid? Thanks!

• For red: just substitute $n$ with $\frac{n}{b^j}$. – zkutch Feb 20 at 19:04
• @zkutch Wouldn't I also have to substitute it in the LHS g(n) as well? – s_kirkiles Feb 20 at 19:05
• No. It is used only for $f$ in right hand. – zkutch Feb 20 at 19:06
• But the inequality only holds past some N. Isnt that assuming it holds for all n? @zkutch – s_kirkiles Feb 20 at 19:42
• – s_kirkiles Feb 20 at 20:37

Suppose that $$f(n) = O(n^{\log_b a - \epsilon})$$. According to the definition, there exist constants $$N,C>0$$ such that $$f(n) \leq Cn^{\log_b a - \epsilon}$$ for all $$n \geq N$$. Let $$M$$ be the maximum value of $$f(n)/n^{\log_b a - \epsilon}$$ over all positive integers $$n < N$$. The maximum exists since there are only finitely many such $$n$$. Then $$f(n) \leq \max(M,C) n^{\log_b a - \epsilon}$$ holds for all integer $$n \geq 1$$. Therefore $$g(n) = \sum_{j=0}^{\log_b n-1} a^j f(n/b^j) \leq \max(M,C) \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} = O\left( \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} \right).$$