Prove that $T(n) = T(n/3) + T2n/3) + 5n$ is $O(n log n)$ I'm doing some research about time complexity of algorithms and stumbled upon the following problem that I'm not able to solve:
Let $T(n) = T(n/3) + T(2n/3) + 5n$. prove that $T(n) = O(n log n)$
First, I made a recursion tree, which is the same as the one in the question: Recursion tree T(n) = T(n/3) + T(2n/3) + cn
I found out that each level costs $5n$ and that the leaves have different depths (The left path is the shortest with height $log_3 n$ and the one on the right is the longest with height $log_{\frac{3}{2}}n$).
Now, since we need an upper bound, I took the longest path of height $log_{\frac{3}{2}}n$. This gives total costs $5n \cdot log_{\frac{3}{2}}n$.
Now I want to prove with induction on $n$ that this is true. I proceeded in the following way:
Assume as induction hypothesis that $T(k) \leqslant 5k \cdot log_{\frac{3}{2}}k$ for $k < n$. Then:
$T(n) \leqslant T(n/3) + T(2n/3) + 5n$
$=^{IH} \frac{5}{3}n log_{\frac{3}{2}}(\frac{n}{3}) + \frac{10}{3}n log_{\frac{3}{2}}(\frac{2n}{3}) + 5n$
$= \frac{25}{3}n log_{\frac{3}{2}} n - \frac{5}{3}n log_{\frac{3}{2}} 3 - \frac{10}{3}n log_{\frac{3}{2}} 3 + 5n$
$= \frac{25}{3}n log_{\frac{3}{2}} - 5n log_{\frac{3}{2}} 3 + 5n$
And this is certainly not smaller then or equal to $5n \cdot log_{\frac{3}{2}}n$. I've spend an entire day now on solving this recurrence relation, but nothing solved it so far. Could you help me solving this problem?


You seem way too attached to the constant 5 and the base $3/2$. You don't need this exact constant to prove what you want, so why make your life miserable by clinging to it instead of picking "anything that works"?

Short advice: do not commit in advance to anything that makes your life harder if you can avoid it.
As an example, in your case let your induction hypothesis be 
$$
T(k) \leq C k \ln k, \qquad \forall k < n \tag{$\dagger$}
$$
($\ln$ is the natural logarithm) for some absolute constant $C>0$ that we will pick momentarily.
Then you get
$$\begin{align}
T(n) &= T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+5n \\
&\leq_{(\dagger)}  C \frac{n}{3}\ln \frac{n}{3} + C\frac{2n}{3}\ln \frac{2n}{3} + 5n\\
&\leq Cn \ln n- C\frac{n}{3}\ln 3 -  C\frac{2n}{3}\ln \frac{3}{2} + 5n \\
&\leq Cn \ln n
\end{align}$$
where the last inequality holds as long as we can choose $C$ such that
$$
C\frac{n}{3}\ln 3 +  C\frac{2n}{3}\ln \frac{3}{2} \geq 5n
$$
for all $n\geq 1$. This is satisfied for any $C$ such that
$$
C \geq \frac{5}{\frac{1}{3}\ln 3+\frac{2}{3}\ln \frac{3}{2}} \simeq 7.8
$$
so we can "retroactively" choose, say, $C\stackrel{\rm def}{=} 8$: the proof now goes through.
