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?

One approach that can tackle recurrences like this is the Akra-Bazzi method:
$T(n) = T(n/3) + T(2n/3) + 5n$ means we must solve for $\left(\frac{1}{3}\right)^p + \left(\frac{2}{3}\right)^p = 1$, which is true for $p=1$. Then we have:
$$T(n) \in \Theta\left(n^p\left(1 + \int_{1}^{n} \frac{5u}{u^{p+1}} \, du\right)\right)$$
$$T(n) \in \Theta\left(n\left(1 + 5\int_{1}^{n} \frac{1}{u} \, du\right)\right)$$
$$T(n) \in \Theta\left(n\left(1 + 5\log(n)\right)\right)$$
$$T(n) \in \Theta\left(n + 5n\log(n)\right)$$
$$T(n) \in \Theta\left(n\log(n)\right)$$
