Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$
Now that we know the answer, we could simplify the proof.
Let's prove that $$T(n)\in\Theta\left(n^2\right)$$
Define $k=k_n$, index of $n$ in base $3/2$, to be the smallest $k$ such that $n/(3/2)^k&lt;1$.

Upper bound:
Assume that $C$ is very large such that $T(1)\leq C=C\cdot1^2$, $1-3C&lt;-C/2$, and that for all $k&lt;K$ and all $m$ with index $k$ we have $$T(m)\leq C(m^2-1/2)$$
Note: We are going to use the $-1/2$ to carry out the induction as it was done in the other answer.
Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. It follows that
$$\begin{align}T(n)&amp;=5T(n/3)+T(2n/3)+1\\
&amp;\leq 5C(n/3)^2-5C/2+C(2n/3)^2-C/2+1\\
&amp;=Cn^2\left(5/3^2+(2/3)^2\right)+1-3C\\
&amp;=Cn^2+1-3C\\
&amp;\leq Cn^2-C/2\\
&amp;=C(n^2-1/2)\end{align}$$

Lower bound:
Assume that $D$ is such that $D&gt;0$, $T(1)\geq D\cdot 1^2=D$, $1-3D\geq -D/2$, and that for every $k&lt;K$ and $m$ of index $k$ we have $$D(m^2-1/2)\leq T(m)$$
Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. Therefore,
$$\begin{align}
T(n)&amp;=5T(n/3)+T(2n/3)+1\\
&amp;\geq 5D((n/2)^2-1/2)+D((2n/3)^2-1/2)+1\\
&amp;=Dn^2\left(5/3^2+1/(3/2)^2\right)-5D/2-D/2+1\\
&amp;=Dn^2+1-3D\\
&amp;\geq D\left(n^2-1/2\right)
\end{align}$$

By induction we have proven that for all $n$ we have $$D(n^2-1/2)\leq T(n)\leq C(n^2-1/2)$$
Therefore, $$T\in \Theta(n^2-1/2)=\Theta(n^2)$$