[beyondCritics]

I like the idea to use super additivity, but in a proof you cannot creatively extend T to the reals, this should be fixed.

Here is the slightly mopped up proof i had in mind, when i posted my hints below:

  Let be r>=1 and 0<a(i) for all 1<=i<=r and 1/a(1) + ... + 1/a(n) =: s < 1.
  Then a(i) > 1 for all 1 <= i <= r. 

  Let be c > 0 and
  T(0) := 0
  T(n) := c \* n + T(floor(n/a(1))) + ... + T(floor(n/a(r)))

  Then T(n) <= b * n for all n with b := c/(1-s) > 0 !
  Proof by induction: 
  "n=0" : 
   The statement holds trivially.

  "k->n": 
   Let n>=1 and assume the statement holds for all 0<=k<n. 
   Now since a(i)>1 we have floor(n/a(i)) <= n/a(i) < n. By the induction hypothesis therefore
   T(floor(n/a(i))) <= b * floor(n/a(i)) <= b * n/a(i). 
   Apply this to get:
   T(n) =  c * n + T(floor(n/a(1))) + ... + T(floor(n/a(r)))
        <= c * n + b * n/a(1) + ... +  b * n/a(r)
        = (c + b*s) * n
        = b * n.
   Hence T(n) <= b * n.