If $T(n) = \sum_i T(\lfloor r_i n \rfloor) $ for $n \ge 1$, then $T(n)/n \to 0$ Let $(r_i)_{i=1}^m$ be a sequence
of positive reals such that
$\sum_i r_i < 1$
and let $t$ be a positive real.
Consider the sequence $T(n)$
defined by $T(0) = t$,
$T(n) = \sum_i T(\lfloor r_i n \rfloor) $
for $n \ge 1$.
Show that
$T(n) = o(n)$,
that is,
$\lim_{n \to \infty} \dfrac{T(n)}{n}
= 0
$.
Note:
This is a variation on 
If $T(n) = un + \sum_i T(\lfloor r_i n \rfloor) $, show that $T(n) = \Theta(n)$.
It is gotten by setting $u=0$ there.
I am close to a solution,
and hope to have one in a few days.
If I find one,
I will post it.
Note:
It is easy to prove that
$T(n) = O(n)$.
The problem is showing that
$T(n)/n \to 0$.
 A: Here is what I have 
been able to come up with.
I will show that $T(n)/n$ can be made arbitrarily small, 
although the number of steps 
seems to be exponential 
in the reciprocal of the bound.
More specifically,
for a real $0 < c < 1$,
there are 
explicitly computable constants 
$A$ and $B$
which both depend on the recurrence
and $B$ also depending on
initial values of $T(n)$
such than
$T(n)/n < c$
for $n > (1/c)^A/B$.
Let
$r = \sum_i r_i$
and
$s = 1-r$
so that
$0 < s < 1$.
Let $r_0 = \min_i r_i$.
I first show that if 
$T(k) \le bk$ 
for 
$r_0n \le k < n$
then $T(n) \le bnr$
for all subsequent $n$.
Suppose that 
$T(k) \le bk$
 for 
$r_0n \le k < n
$. 
We want to show that 
$T(n) \le bn
$. 
$\begin{align} 
T(n) 
&=\sum_i T(\lfloor r_i n \rfloor)\\ 
&\le \sum_i b r_i n\\
 &= n\sum_i b r_i \\
 &= nb r\\
\end{align} 
$ 
This shows that the bound on
$T(n)/n$
gets reduced by a factor
of $r$.
The next step is
to see when the bound
gets be reduced by
a factor of $r^2$.
Let $n_0 = n$.
We want to find an
$n_1$ such that
$r_0 n_1 = n_0$,
so that the interval
from $r_0 n_1$ to $n_1-1$
can be the basis for
another reduction in the bound
by a factor of $r$.
This obviously is satisfied by
$n_1 = n_0/r_0$.
Similarly, setting
$n_2 = n_1/r_0$
allows the bound to be reduced
by a factor of $r^2$.
By induction,
if $n_k = n_{k-1}/r_0
= n_0/r_0^k$,
$T(n)/n < b r^k$
for $n > n_k$.
Let $s = 1/r_0$,
so $s > 1$.
restating the preceding results
in terms of $s$,
if $n_k 
= n_{k-1}s 
= n_0 s^k$, 
$T(n)/n < b r^k$ for 
$n > n_k$.
This shows that
the bound is reduced
by a factor of $r^k$
in $n_0 s^k
$
steps.
If the bound,
starting at $b$,
is to be less than $c$,
where $0 < c < 1$,
$b r^k < c$
or
$k > \dfrac{\log (c/b)}{\log r}$
(since $r < 1$).
The number of steps
to have the bound reduced to
$c$
is thus
$\begin{align}
n_0 s^{\frac{\log (c/b)}{\log r}} 
&=n_0 \exp(\log s(\log (c)-\log(b))/(\log r)\\
&=n_0 \exp\left(\frac{\log s\log c}{\log r}-\frac{\log s\log b}{\log r}\right)\\ 
&=n_0 \exp\left(\frac{\log s\log c}{\log r}\right)/K\\ 
&=n_0 \exp\left(\frac{\log s\log (1/c)}{\log (1/r)}\right)/K\\ 
&=n_0 (1/c)^{(\log s)/(\log (1/r))}/K\\ 
\end{align}
$
where
$K 
= \exp\left(\frac{\log s\log b}{\log r}\right)
= b^{\log s/\log r} 
$.
In these formulas,
$c$ is the value the
bound on $T(n)/n$
is to be reduced to
(e.g., $c=0.01$),
$r$ and $s$ depend
on the recurrence,
and $b$ is the initial bound on
$T(n)/n$.
Therefore,
$T(n)/n$ can be made
arbitrarily small,
although the number of steps
seems to be
exponential in the
reciprocal of the bound.
A: Here is a proof for a special case that is not too involved yet does occur in actual settings. Suppose your $r_k$ are all inverse integer powers of some positive integer $p$, where $p\ge 2,$ so that $r_k = 1/p^{q_k}$ with $q_k\ge 1$ and the $q_k$ distinct.
Your recurrence now looks like this:
$$ T(n) = \sum_{k=1}^m T(\lfloor n/p^{q_k} \rfloor).$$
Let $D = \max_{k} q_k$ and introduce $$S(n) = \sum_{k=1}^m S(n-q_k)$$
where the initial values are $S(n) = T(p^n)$ for $0\le n < D.$ Then it is not difficult to see that the following exact formula holds: $$ T(n) = S(\lfloor\log_p n\rfloor).$$
Now $S(n)$ is linear and homogeneous with characteristic equation
$$\lambda^D = \sum_{k=1}^m \lambda^{D-q_k}.$$
Note that the maximum modulus of the roots of this equation is strictly less than two, because for $|\lambda|=R$ we have 
$$\left| \sum_{k=1}^m \lambda^{D-q_k} \right|
\le \sum_{k=1}^m |\lambda|^{D-q_k} = \sum_{k=1}^m R^{D-q_k}
\le \sum_{d=0}^{D-1} R^d = \frac{R^D-1}{R-1}.$$
But for $R\ge 2$ we have
$$ \frac{R^D-1}{R-1} < R^D $$
since this is just $$ R^D - 1 < R^{D+1} - R^D \quad\text{or}\quad 2R^D < R^{D+1} + 1,$$ producing a contradiction to the fact that $\lambda$ was supposed to be a root (modulus of LHS $>$ RHS in the original equation).
Let $\rho$ be the root with maximum modulus of the characteristic equation. Then by the basic theory of recurrence relations the asymptotically dominant term of the solution to the recurrence satisfies $$S(n) \sim c n^{a-1} \rho^n$$ with $c$ a constant and $a$ the multiplicity of the root. An easy continuity argument shows that in fact $\rho$ is real and $1<\rho<2.$ (The root $\rho$ cannot correspond to a pair of complex conjugate roots, because these would generate a fluctuating trigonometric term which, its modulus being the largest, would eventually produce a pair of consecutive values of $S(n)$ with different signs or one of them being zero, contradicting the fact that $S(n)$ is easily seen to be strictly increasing.)
This yields the following for $T(n):$
$$ T(n) \sim c \lfloor\log_p n\rfloor^{a-1} \rho^{\lfloor\log_p n\rfloor}.$$
Hence 
$$\frac{T(n)}{n} \in 
\Theta\left( \lfloor\log_p n\rfloor^{a-1} 
\left(\frac{\rho}{p}\right)^{\lfloor\log_p n\rfloor}\right).$$
This shows the claim that $T(n)/n\to 0$ because $\rho/p$ is strictly less than one and its positive powers vanish as $\log_p n$ goes to infinity, canceling the polynomial in $\log_p n$ along the way. (The trick was that $\rho<2$ and $p\ge 2.$)
Addendum I. The reader may wish to verify that $\sum_{k=1}^m \frac{1}{p^{q_k}}$ is indeed less than one. II. The argument goes through even if the set of roots with maximum modulus (which is finite) were to include complex numbers, because the bound on $|\rho|$ continues to hold.
A: I have some very exciting news for Mr. M. Cohen and other potential readers of this thread. I hope it gets viewed often because the result is really very pretty. We show that we can solve a more general case than in the first post using Dirichlet series and Mellin transforms, getting exact formulas for $T(n)$ and for the leading asymptotic term.
Suppose that $r_k = 1/p_k$ for all $k$ and $\sum_k 1/p_k < 1$ where the $p_k\ge 2$ are distinct and $k\ge 2$. Note that these can be arbitrary integers now as opposed to powers of a unique integer in our first post. Furthermore let $T(0) = 1.$
Now evidently what we are facing here is a tree where nodes branch out for every $p_k$ as long as $n$ is not zero and we want a count of the leaves. The following observation is the key: the finite Dirichlet series in $s$ given by 
$$D_l(s) = \left(\sum_k \frac{1}{p_k^s}\right)^l = \sum_q \frac{a_{l,q}}{q^s}$$ 
perfectly encodes by means of a bijection all paths of length $l$ (that is, $l$ edges) from the root to a leaf and the multiplier of $n$ corresponding to each path. If $q> \lfloor n/p_k \rfloor$ and $q\le n$ then appending a step along $p_k$ produces $a_{l,q}$ zero values, i.e. leaves.
Hence we have the following exact formula (exact for all $n$):
$$T(n) = \sum_k \sum_{l=0}^{\lfloor \log_2 n \rfloor}
\sum_{\lfloor n/p_k \rfloor < q \le n} a_{l, q}.$$
Now observe that we can safely replace this by
$$T(n) = \sum_k \sum_{l=0}^\infty
\sum_{\lfloor n/p_k \rfloor < q \le n} a_{l, q}$$
because $a_{l,q}$ never contributes when $q>n$ and the smallest denominator occurring in the corresponding $D_l(s)$ is $(\min_k p_k)^{\lfloor \log_2 p_k \rfloor + 1} > n.$
Introducing the Dirichlet series
$$D(s) = \sum_{l\ge 0} D_l(s) = 
\sum_{l\ge 0} \left(\sum_k \frac{1}{p_k^s}\right)^l =
\frac{1}{1 - \sum_k \frac{1}{p_k^s}} = \sum_q \frac{a_q}{q^s}$$
we thus obtain
$$T(n) = \sum_k\sum_{\lfloor n/p_k \rfloor < q \le n} a_q.$$
Now put $$M(n) = \sum_{q=1}^n a_q$$ so that
$$T(n) = \sum_k (M(n) - M(\lfloor n/p_k \rfloor).$$
We will evaluate $M(n)$ by means of the Wiener-Ikehara theorem, which is a form of Mellin summation. Note that by the intermediate value theorem $$1-\sum_k \frac{1}{p_k^s}$$ has a root between $s>0$ and $s<1$ (these inequalities are strict). Call this root $\rho.$
Now $$\frac{1}{1-\sum_k \frac{1}{p_k^s}}$$ has a simple pole there with residue
$$\operatorname{Res}
\left(\frac{1}{1-\sum_k \frac{1}{p_k^s}}; s=\rho\right) = 
\frac{1}{\sum_k \frac{\log p_k}{p_k^\rho}}.$$
We may thus conclude that
$$M(n) \sim \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} \frac{n^\rho}{\rho}$$
obtaining finally that
$$T(n) \sim \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} 
\sum_k\left(\frac{n^\rho}{\rho} - \frac{(n/p_k)^\rho}{\rho}\right)\\
= \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} 
\frac{n^\rho}{\rho}\sum_k\left(1 - (1/p_k)^\rho\right)
= (m-1) \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} 
\frac{n^\rho}{\rho}.$$
This asymptotic formula converges very nicely and the quotient between $T(n)$ and this leading term goes to one very quickly, as numerical experiments show.
In particular $$\frac{T(n)}{n}\in\Theta(n^{\rho-1})$$ so that
$$\frac{T(n)}{n}\to 0$$
as claimed since $\rho-1<0.$
I encourage readers to fill in the details and I am available for questions. Thanks go to M. Cohen for asking such a wonderful question.
This is the Maple code that I used to verify these formulas.


ex :=
proc(l, n)
option remember;
local k, r, t, ds, cfs, terms, tval, pos;
    if n=0 then return 1 fi;

    r := 0;
    for k from 0 to ilog[2](n) do
        if k=0 then
            for t in l do
                if t>n then r := r+1; fi;
            od;
        else
            ds :=
            map(simplify, expand(add(1/l[q]^s, q=1..nops(l))^k));
            ds := convert(ds,list);

            cfs := map(t->subs(s=0, t), ds);
            terms := [seq(ds[pos]/cfs[pos], pos=1..nops(ds))];

            for pos to nops(ds) do
                for t in l do
                    tval := op(1, terms[pos]);
                    if tval>floor(n/t) and tval<=n then
                        r := r+cfs[pos];
                    fi;
                od;
            od;
        fi;

    od;

    r;
end;

T :=
proc(l, n)
option remember;
    local t, r;

    if n=0 then return 1 fi;

    r := 0;
    for t in l do
        r := r+T(l, floor(n/t));
    od;

    r;
end;

rho :=
proc(l)
option remember;
    fsolve(1-add(1/l[k]^s, k=1..nops(l)), s);
end;


lterm :=
proc(l, n)
    (nops(l)-1)*1/
    add(log(l[k])/l[k]^rho(l), k=1..nops(l))*n^rho(l)/rho(l);
end;

A: I am presenting an important addendum. The code for my first answer does not work properly when some of the $p_k$ are repeated even though the math is right, and it is not all that efficient. I have remedied this defect and I am presenting code that works for duplicate $p_k$ and is amazingly fast even for large arguments $n$ to $T(n).$ I have used this code to verify the correctness of the above mathematical argument empirically for a number of sets of $p_k.$ 


mul_dir :=
proc(l1, l2)
option remember;
local r, res, t, t1, t2, pos;

    r := [];

    for t1 in l1 do
        for t2 in l2 do
            r := [op(r), [t1[1]*t2[1], t1[2]*t2[2]]];
        od;
    od;

    r := sort(r, (p1, p2) -> p1[2] < p2[2]);

    res := []; p := r[1];
    for pos from 2 to nops(r) do
        if p[2] <> r[pos][2] then
            res := [op(res), p];
            p := r[pos];
        else
            p[1] := p[1] + r[pos][1];
        fi;
    od;

    res := [op(res), p];
    res;
end;


ex :=
proc(l, n)
option remember;
local k, r, t, f, ds, cfs, terms, tval, pos;
    if n=0 then return 1 fi;

    r := 0; f:= [seq([1, l[q]], q=1..nops(l))];
    for k from 0 to ilog[2](n) do
        if k=0 then
            ds := [[1,1]];
        else
            ds := mul_dir(ds, f);
        fi;

        for pos to nops(ds) do
            for t in l do
                tval := ds[pos][2];
                if tval>floor(n/t) and tval<=n then
                    r := r+ds[pos][1];
                fi;
            od;
        od;
    od;

    r;
end;

T :=
proc(l, n)
option remember;
    local t, r;

    if n=0 then return 1 fi;

    r := 0;
    for t in l do
        r := r+T(l, floor(n/t));
    od;

    r;
end;

rho :=
proc(l)
option remember;
    fsolve(1-add(1/l[k]^s, k=1..nops(l)), s);
end;


lterm :=
proc(l, n)
    (nops(l)-1)*1/
    add(log(l[k])/l[k]^rho(l), k=1..nops(l))*n^rho(l)/rho(l);
end;

