If $T(n) = \sum_i T(\lfloor r_i n \rfloor) $ for $n \ge 1$, then $T(n)/n \to 0$

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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;

Answer 4

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;