In all proofs of master theorem I've found so far (Cormen et al., also here http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec19-master/mm-proof.pdf), there is essentially a following series of implication used:
$ f(n) = O(n^{log_ba - \epsilon}) \Rightarrow^* a^jf(n/b^j) = a^jO((\frac{n}{b^j})^{log_ba - \epsilon}) \Rightarrow^{**} \sum_{j=0}^{log_bn-1}a^jf(n/b^j) = \sum_{j=0}^{log_bn-1}a^jO((\frac{n}{b^j})^{log_ba - \epsilon}) $
My understanding is that the implication (*), which is pretty easy to prove for fixed j, is used for each summand, thus giving (**).
While intuitively feasible, I don't see how second implication immediately follows, though. The reason for my doubt is that j depends on n in context of summation. E.g., if we try to apply (*) for max j, we have
$ a^{log_bn-1}f(b) = a^{log_bn-1}O(b^{log_ba - \epsilon}) $
which, while obvious for b>0, let alone b>1, is not technically a statement of form on right side of (*), i.e. $a^jf(n/b^j) = a^jO((\frac{n}{b^j})^{log_ba - \epsilon})$, because to get that you need to substitute a constant j with an expression containing free variable n.
Can you help with that confusion?
Upd, relevant: another problem I have with (**), which seems to be closely related, is as follows:
Let's say we have (with nonnegative functions)
$f_1(n) = O(\phi_1(n)) \iff \exists n_1, c_1: \forall n\geq n_1, f_1(n) \leq c_1\phi_1(n)$
$f_2(n) = O(\phi_2(n)) \iff \exists n_2, c_2: \forall n\geq n_2, f_2(n) \leq c_2\phi_2(n)$
It immediately follows that $\tilde{f}(n)=f_1(n) + f_2(n) = O(\phi_1(n) + \phi_2(n))$, because you can take $\tilde{c}=max(c_1, c_2), \tilde{n}=max(n_1,n_2)$. This argument, obviously, trivially extends to arbitrary sum of functions with predefined number of summands.
But as soon as we try to use this the way it is used in (**), it loses ground, because now the number of summands starts to depend on n itself, which used to be a free variable in previous argument.
To clarify: I can prove (**) by explicitly using $f(n) \leq c\cdot(n^{log_ba-\epsilon}) \forall n $, which is trivial to show, but that is not quite the stated proof.
Actually, $$a^{\log_bn-1}f(b) = a^{\log_bn-1}O(b^{\log_ba - \epsilon})$$ is a statement of the form $$a^jf(n/b^j) = a^jO((\frac{n}{b^j})^{\log_ba - \epsilon}).$$ If you follow Cormen et al’s discussion of the “Master Theorem”, you’ll notice that they break up the proof into smaller segments. Your question touches upon the first part of the proof where they assume that $n$ is an exact power of $b>1$. In other words, $n=b^M$ where $M$ is a positive integer equal to $\log_b n$. So, you can write the right side of your $(*)$ as $$a^jf(b^{M-j}) = a^jO(({b^{M-j}})^{\log_ba - \epsilon}).$$ We then see that your application of $(*)$ for the last term in the summation corresponds to this equation with $j=M-1=\log_b n - 1.$