Solving recurrence relation when cost of all combining steps is constrained I have a recurrence relation $T(n) = \left( \sum_{i=1}^{k} T(d_i n) \right) + f(n)$, where each $ 0 &lt; d_i &lt; 1$, $f(x) &gt; 0$ for all $\, x &gt; 0$ and $f(xy)=f(x) \cdot f(y)$ for $x,y\geq 0$.

I am asked to give an asymptotically tight bound on $T(n)$ if $\sum_{i=1}^{k} f(d_i) &lt; 1$ and if $\sum_{i=1}^k f(d_i) = 1$ using the substitution method, and I am told not to worry about the base case. I am following the substitution method from CLRS section 4.3 and  basically means guess an upper bound, and then prove by induction.

I tried several guesses when $\sum f(d_i n) &lt; 1$, but I get stuck regardless of my choice. If $T(n) = O(f(n))$, it must be true that 
\begin{align*}
T(n)&amp;\leq c f(d_1n) + c f(d_2 n) + \dots + cf(d_k n) + f(n)\\
&amp;= c(f(d_1 n) + f(d_2 n) + \dots f(d_k n)) + f(n) \\
&amp;&lt; c + f(n) &amp; \text{Since} \sum f(d_i n) &lt; 1
\end{align*}
Which is false, unless $c &lt; 0$, which can't be the case.

If $T(n) = \lg f(n) $ then it must be true that

\begin{align*}
T(n) &amp;\leq c \lg (f(d_1 n)) + c \lg(f(d_2 n)) + \dots + c \lg(f(d_k n)) + f(n) \\
&amp;=c [\lg f(d_1) + \lg f(n) + \lg f(d_2) + \lg f(n) + \dots + \lg f(d_k) + \lg f(n)] + f(n) \\
&amp;=c \left( \left(\sum_{i=1}^{k} \lg f(d_i)\right) + k \lg f(n) \right) + f(n).
\end{align*}
Not sure how to proceed here. When I tried $T(n) = O\left(f(n)^2\right)$, I got

\begin{align*}
T(n) &amp;\leq c \left( \sum_{i=1}^n f(d_i n)^2 \right) + f(n) \\
&amp;&lt; c + f(n) &amp; \text{ since } \sum f(d_i n ) &lt; 1 \implies \sum f(d_i n)^2 &lt; 1  \\
&amp;\leq c f(n)^2
\end{align*}
which doesn't seem too tight, but I'm not sure. Any comments or pointers on how to proceed? I presume it involves incorporating the constraints on $\sum f(d_i)$ in some other way, but right now I am not seeing how to do so.
Form a recursion tree. The root represents $T(n)$, and has weight $f(n)$. It has $k$ children, the edges are labelled $f(d_1),\ldots,f(d_k)$, and the children itself have weights $f(d_1)f(n),\ldots,f(d_k)f(n)$; they correspond to $T(d_1n),\ldots,T(d_kn)$. Each child has its own $k$ children, and so on, only we delete nodes corresponding to $T(m)$ for $m &lt; 1$. Note that the weight of each node is $f(n)$ times the weights of all edges from the node to the root. The total running time, assuming a base case around $1$, is the sum of all weights in the tree.

When $\sum_{i=1}^k f(d_i) &lt; 1$, we can compute the total weight of the infinite tree (without the pruning described above) as
$$
f(n) \sum_{t=0}^\infty (f(d_1) + \cdots + f(d_k))^t = \Theta(f(n));
$$
here $(f(d_1) + \cdots + f(d_k))^t f(n)$ is the total weight at level $t$. Thus in this case we have $T(n) = \Theta(f(n))$.

When $\sum_{i=1}^k f(d_i) = 1$, each full level contributes $f(n)$, and each partial level (where some nodes were pruned) contributes at most $f(n)$. There are $\Omega(\log n)$ full levels and $O(f(n))$ full or partial levels, and we conclude that $T(n) = \Theta(f(n)\log n)$.