The recursion $T(n) = T(n/2)+T(n/3)+n$ I'm looking at the reccurrence
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).

Using induction, I found that $T(n) = O(n\log n)$, but have been told that this is not tight. Indeed, assume inductively that $T(k) \leq Ck\log k$ for all $k&lt;n$ (and sufficiently large values of $k$), then

\begin{align*}
T(n)&amp;\leq C\frac{n}{2}\log\frac{n}{2} + C\frac{n}{3}\log \frac{n}{3} + n\\
&amp;= C\frac{5}{6}n\log n - n(C/2+C\log3/3 - 1).
\end{align*}

Now I choose $C$ large enough for $(C/2+C\log3/3 - 1) &gt; 0$, and so the last expression is dominated by $C\frac{5}{6}n\log n\leq Cn\log n$.

My first question is, what is a tighter bound that this?

Second, I tried to use the Akra-Bazzi method to solve this, so let $p$ solve
$$\left(\frac{1}{2}\right)^p + \left(\frac{1}{3}\right)^p = 1.$$
Then approximately $p=0.79$, and (with $g(n) = n$) I get
$$\int_1^n \frac{g(u)}{u^{p+1}} du = \int_1^n \frac{1}{u^{p}} du = \frac{1}{1-p}(n^{1-p}-1),$$
and so

$$T(n) = \Theta\left(n^p\left(1+\frac{1}{1-p}(n^{1-p}-1)\right)\right).$$

This equals $\Theta(n^p + \frac{1}{1-p}n-\frac{1}{1-p}n^p)$, so overall $\Theta(n)$, since $p&lt;1$. My second question is that I don't really believe that $T$ is linear, so what went wrong in my application of Akra-Bazzi?

Best regards.
If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction.

$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$ 

More generally, let $c\gt6$ be a constant such that $T(1)\le c$ and $T(2)\le 2c$,  then we can prove routinely that $T(n)\le cn$. Although it might seem unbelievable to you, it is true that
$$T(n)=O(n).$$

Intuitively, since $\dfrac12+\dfrac13\lt1$, the terms $T(n/2)$ and $T(n/3)$ is not big enough to lift $n$ to a power of $n$ of a larger exponent.

There is nothing wrong in your application of Akra-Bazzi method, which tells us that $T(n)=\Theta(n)$.