If $T(n) = un + \sum_i T(\lfloor r_i n \rfloor) $, show that $T(n) = \Theta(n)$ Let $(r_i)_{i=1}^m$ be a sequence
of positive reals such that
$\sum_i r_i < 1$
and let $t$ and $u$ be positive reals.
Consider the sequence $T(n)$
defined by $T(0) = t$,
$T(n) = un + \sum_i T(\lfloor r_i n \rfloor) $
for $n \ge 1$.


*

*Show that
$T(n) = \Theta(n)$,
that is 
$T(n) = O(n)$
and
$T(n) = \Omega(n)$.

*Show that there exists a
real number $L$ such that
$\lim_{n \to \infty}
\dfrac{T(n)}{n} = L
$.

*Specify $L$
in terms of
$t$, $u$,
and the $r_i$.
Note:
This is a generalization of https://math.stackexchange.com/questions/504495/recurrence-relation-using-induction-method/504536#504536.
I have a proof of part 1
which is a fairly straightforwand
generalization of
my solution to that question.
I do not yet have a solution to part 2. 
I have a conjecture as to the
solution to part 3
which should be pretty evident
from my solution to part 1,
which I will submit if
no one submits a solution within two days.
 A: Here is my proof of part 1, as promised.
Let
$r = \sum_i r_i$
and
$s = 1-r$
so that
$0 < s < 1$.
Let $r_0 = \min_i r_i$.
First, the upper bound.
Suppose that
$T(k) \le bk$
for $r_0n \le k < n$.
We want to be able to deduce that
$T(n) \le bn$.
$\begin{align}
T(n)
&=un + \sum_i T(\lfloor r_i n \rfloor)\\
&\le un + \sum_i b r_i n\\ 
&= n(u + \sum_i b r_i )\\ 
&= n(u + b r)\\ 
\end{align}
$
and this is
$\le bn$
if 
$n(u + b r)
\le bn$
or
$u+br \le b$
or
$u \le b(1-r) = bs$
or
$b \ge \dfrac{u}{s}$.
For a particular $n$,
if we choose
$b \ge \max\left(\dfrac{u}{s},
\max_i \left( \dfrac{T(\lfloor r_i n \rfloor)}{\lfloor r_i n \rfloor}\right)\right)
$,
all subsequent $T(n)$ will be
$\le bn$.
The only problem might be if
some $r_i n < 1$,
so that $\lfloor r_i n \rfloor
= 0$. To avoid this,
start with $n$ such that
$r_0 n \ge 1$,
or
$n \ge \dfrac1{r_0}$.
Then, the lower bound.
Suppose that 
$T(k) \ge ak+c$ for 
$r_0n \le k < n$. 
We want to be able to deduce that 
$T(n) \ge an+c$.
The constant term $c$
is needed because of the
floor functions in 
the recurrence for $T(n)$.
$\begin{align} 
T(n) 
&=un + \sum_i T(\lfloor r_i n \rfloor)\\ 
&\ge un + \sum_i (a(\lfloor r_i n \rfloor+c)\\ 
&> un + \sum_i (a (r_i n-1)+c)\\ 
&= n(u + \sum_i (a r_i )
- \sum_i (c-a) \\ 
&= n(u + a r) + m(a-c)\\ 
\end{align} 
$ 
and this is 
$\ge an+c$ if 
$n(u + a r)+m(a-c) \ge an$ 
or 
$n( a (1-r)-u)+m(a-c) \le 0$ 
or
$n( as-u)\le m(c-a)$.
For this to be true,
we must have
$as-u \le 0$
or $a \le \dfrac{u}{s}=v$.
Otherwise,
the left side would get
arbitrarily large
for large enough $n$.
If, in addition,
$a < \dfrac{u}{s}$,
then this will be true
for all large enough $n$
(i.e., all $n$ if $c \ge a$
and
$n > \dfrac{a-c}{as-u}$
if $c < a$.
We now choose $a$ small enough
so that
$a < \dfrac{u}{s}=v$
(as before, remembering that
$vs = u$).
To do this,
let $a = v-d$
where $v > d > 0$
so $a > 0$.
Since we want
$n( as-u)\le m(c-a)$,
or
$n( as-u)+am\le mc$, 
this will be true if
$n( (v-d)s-u)+am\le mc$, 
or
$n( -ds)+am\le mc$.
Since $-dsn < 0$,
this will be true if
$c \ge a$,
and this, in turn,
will be true if
$c \ge v$.
We also need,
for the induction hypothesis,
that
$T(k) \ge ak+c$
for
$r_0n \le k < n$.
Since $c = v$ works for
the recurrence to be true,
we want
$a \le \dfrac{T(k)-c}{k}$
for $r_0 n \le k < n$.
To ensure that $a > 0$,
we need $T(k) > c$.
Since $T(k) \ge uk$,
this will be true if
$uk > c$ or 
$k > \dfrac{c}{u}$
and this will be true if
$k > \dfrac{v}{u}$.
Since we want to look at
$r_0 n \le k$,
we need
$r_0 n > \dfrac{v}{u}$
or
$n > \dfrac{v}{u r_0}$.
Following all these prescriptions
will allow us to find a value of $n$
that will allow us
to compute a value of $a$
such that
$T(k) \ge ak+c$
for $r_0 n \le k < n$
will imply that
$T(n) \ge an+c$
for all larger $n$.
For problem 2,
I do not know how to refine
this solution
so show how the
values for $a$ and $b$
can be made arbitrarily close.
For problem 3,
my obvious conjecture is that
$\lim_{n \to \infty} \dfrac{T(n)}{n}
= v 
= \dfrac{u}{s}
= \dfrac{u}{1-\sum_i r_i} 
$.
