Justifying a claim in the proof of the master theorem

Question

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)<c(n/b^j)^{\log_b{a}-\epsilon}$$

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!

Answer 1

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). $$