$T(n)=T(cn) + T((1-c)n)+1$ while $0Question:
$T(n)=T(cn) + T((1-c)n)+1$ 
$0<c<1$ and $T(1)$ is constant.
My thoughts:
I'm trying to solve this recursion using Induction, but I think I got it all wrong.
My guess is that $T(n) = O(n)$
The induction assumption:
for every $k<n$ exists a constant $m$ that $T(k) < mn $
because $0<c<1$ we know that $cn<n$ and $(1-c)n<n$ 
Therefore $T(cn)<mn$ and $T((1-c)n)<mn$
I need to prove that $T(n)<mn$
so I said that $T(n) = T(cn) + T((1-c)n)+1 < mn +mn +1 = 2mn+1$
But now my constant has changed to $m'=2m$
which is a problem...
what can I do?
I hadn't studied any fancy sentences.. 
I can use induction, recursion trees or something simple... 
any help would be highly appreciated! Thanks

If $T(n)=T(cn) + T((1-c)n)+1$ then let $S(n)={T(n)+1}$.  
You have $S(n)=S(cn) + S((1-c)n)$ or equivalently $S(a+b)=S(a)+S(b)$, with the linear solution $S(n)=nS(1)$.  
So $T(n)+1=n(T(1)+1)$, i.e. $$T(n)=nT(1)+n-1$$ which is indeed $O(n)$ 
