Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree I am trying to solve the following recurrence relation:
$$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$ 

I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} &lt; n$

I am trying to prove it using a recurrence tree. 

The tree is not balanced. Particularly, the longest path from the root to a leaf is the leftmost one  with a length of $\log_2n$ when the shortest path is the rightmost one with a length of  $\log_3n$. 

We get that at each level,except the first one, the cost is $&lt; n$. In more detail,the first level has a cost of $n$. The nodes on the second level add to a $\frac{5}{6}\cdot n$ cost, the third level has a cost equal to $\left (\frac{5}{6}  \right )^2\cdot n$ and so on...

So, untill the height of $\log_3n$ we have a cost of $$n\sum_{i=0}^{\log_3n-1}\left (\frac{5}{6}   \right )^i = n\cdot \frac{\left (\frac{5}{6}\right)^{\log_3n}-1}{\left (\frac{5}{6}\right)-1}$$

So, the result above seems to be a lower bound for my function $T(n)$

Is my approach correct? If yes, then how do I go on in order to prove that the time complexity is $T(n)=Θ(n)$.Thanks in advance!
On the one hand, clearly $T(n) \geq n$ (see detailed proof below). On the other hand, let us find prove by induction that $T(n) \leq Cn$, for large enough $C$. The base case trivially holds for $C \geq T(1)$. For the inductive step, we have
$$
T(n) = T(n/2) + T(n/3) + n \leq C\cdot (n/2) + C\cdot (n/3) + n = [\tfrac{5}{6}C+1]n.
$$
(We're cheating here a bit since $n$ isn't necessarily a multiple of 6.) If $C \geq 6$, then $\tfrac{5}{6}C+1 \leq C$, and so we can conclude that $T(n) \leq Cn$, thus completing the inductive step. In total, if we take $C = \max(T(1),6)$ then the proof goes through, hence
$$ n \leq T(n) \leq \max(T(1),6) n. $$
This implies that $T(n) = \Theta(n)$.



Finally, let us prove that $T(n) \geq n$. We first prove that $T(n) \geq 0$. The proof by induction. The base case clearly holds, and the inductive step is a consequence of
$$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + 0, $$
using the inductive hypothesis twice. Finally,
$$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + n = n. $$