Recurrence of T(n) = T(n/3) + T(2n/3) I've searched online for this but I only seem to find answers for a similar equation: 
T(n) = T(n/3) + T(2n/3) + cn

But the one I'm trying to solve is:
T(n) = T(n/3) + T(2n/3)

Base case: We can assume T(a) = Theta(1) for any constant a.
I've succeeded in proving (by induction) that T(n) = O(n*log(n)). I thought the answer should be Theta(n*log(n)), but I cannot prove that T(n) = Omega(n*log(n)).
So my question is - am I correct that the answer is O(n*log(n)), and NOT Theta(n*log(n))? IF that's true that would really be great...
If I'm wrong I will of course explain where I'm stuck in the induction process...
Thanks!
P.S. If you need to, please try to explain using induction, because I haven't learned all methods for solving these problems yet.
 A: umm, if you have solution for $cn$ take $c=0$? Why waste time?
A: Without the additive term, the (exact) solution will be of the form $T(n)=\alpha n$ for some constant $\alpha$ depending on the first terms.
By substitution (or induction if you prefer):
$$T(n) = T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right) = \alpha \frac{n}{3}+\alpha \frac{2n}{3} = \alpha n$$
A: The other answers are simpler, but if you want to see how to use induction to prove the results from definitions:
$$T \in \Theta(g)$$
is defined as:
$$(\exists k_1 > 0,\, \exists k_2 > 0,\, \exists n_0,\,\forall n > n_0)\\
g(n)k_1 \le T(n) \le g(n)k_2$$
which means that $T$ is bounded above and below by scalar multiples of $g$ for sufficiently large $n$. You've already done the hard part, which is choosing a $g$, so we just use induction to find some $k_1$, $k_2$, $n_0$.  We will see that there actually aren't any though.
$$n\,\log(n)k_1 \le T(n) \le n\,\log(n) k_2$$
$$n\,\log(n)k_1 \le T(n/3) + T(2n/3) \le n\,\log(n) k_2$$
For the lower bound, we steal the strong inductive assumptions that $\frac n3\, \log(\frac n3)k_1 \le T(n/3)$ and $\frac {2n}3\, \log(\frac {2n}3)k_1 \le T(2n/3)$ to get :
$$n\,\log(n)k_1 \le
\frac n3\, \log(\frac n3)k_1 + \frac {2n}3\, \log(\frac {2n}3)k_1   $$
which simplifies to 
$$3n\,\log(n) \le
n\, \log(n) + 2n\, \log(n) -n\,\log(3)-2n\log(1.5)  $$
$$n\,\log(3)+2n\log(1.5) \le 0$$
...which means that you can't satisfy the lower bound, your function isn't growing as fast as $n\,\log\,n$.
We can try Clement C. answer:
$$\alpha\,n\,k_1 \le T(n/3) + T(2n/3) \le \alpha\,n\,k_2$$
By inductive assumptions:
$$\alpha\,n\,k_1 \le \alpha\,n/3\,k_1 + \alpha 2n/3 \,k_1 \land\\
\alpha\,n/3\,k_2 + \alpha 2n/3 \,k_2 \le \alpha\,n\,k_2 
$$
It is easy to see that any choice of $k_1$ and $k_2$ satisfy the bounds, so Clement C. answer holds for all values of $\alpha$:
$$(\forall \alpha)\, T \in \Theta(\alpha n)$$
