<s>[INST] 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?
 [/INST] 
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.
</s>