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)=Oleft(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 cinmathbb{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 csum_{i=0}^{log_{b}(n)-1}a^i(n/b^i)^{log_b{a}-epsilon}

$$

Which implies that $g(n)=Oleft(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!