Recurrence trouble: $T(n)=2T(n/2)+T(n/3)+\theta(n^2)$ I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$ 
I have done the whole tree analyses and  now I have to prove that $\displaystyle T(n) \leq dn^{2}\log_{2}(n)$ but I can not find mathematical way to prove that, is there any trick with logarithms that I can use?
 A: Try applying the Akra-Bazzi theorem.
By Akra-Bazzi, if $p$ satisfies
$\displaystyle 2(1/2)^p + (1/3)^p = 1$, (notice that $\displaystyle 1 \lt p \lt 2$)
then
$\displaystyle T(x) = \theta(x^p(1 + \int_{1}^{x} x^{1-p})) = \theta(x^p(1+x^{2-p}))$
since $\displaystyle 1 \lt p \lt 2$
we must have that
$\displaystyle T(x)  = \theta(x^2) = O(x^2 \log_{2} x)$.
A: Do it by induction. First, let's set the constant in $\theta$ to 1, so we get
$T(n)=2T(n/2)+T(n/3)+n^2$
Now, assume $T(m) \leq k m^2$ for some constant $k$ for all $m < n$. Then
$T(n) = 2 T(n/2) + T(n/3) + n^2 \leq k n^2/2 + k n^2/9 + n^2 \leq (11 k /18 +1) n^2 $
and if $k = 3$, say, we have
$T(n) \leq (11/6+1) n^2 \leq 3 n^2.$
so if our bound holds for all $m < n$, then our bound holds for $n$. 
To make this a real proof, you would need to take the case when $n$ is not a multiple of 6 into account, but the details will work out when you do them carefully.
A: For suitable constant $c$, $f(n) = (T(n)/n^2) + c$ satisfies a recurrence $f(n) = Af(n/2)+Bf(n/3)$ which has solutions (for continuous-valued $n$) of the form $n^\alpha$.  This should give a guess about the asymptotics for integer $n$ and one could probably incorporate lower order terms (fluctuations from the complex solutions with real part less than that of $\alpha$) by analyzing the zeros of $G(x)=1 - Ax^{\log 2} - Bx^{\log 3}$ or the generating function with real exponents (generalized power series expansion) for $1/G(x)$.
I think this type of exercise for the large $n$ asymptotics and translation to the continuous problem is in books such as (e.g.) Flajolet and Sedgewick's text on asymptotic combinatorics.  However, for this specific recurrence it might be possible to go beyond the standard asymptotics and handle integer-valued $n$ directly, because the operations of replacing $n$ by $P(n)=[n/2]$ and $Q(n)=[n/3]$ commute.  One could look at base 6 expansions of $n$, or classify integers according to which operations $P^a Q^b$ take them to $0$ and $1$, and sums over the $(a,b)$ would give an integer-valued expansion formula for $f(n)$, similar to the binomial theorem or the expansion of a rational generating function $1/(1-H(x))$ as a geometric series.
