Maybe someone knows how to write sum formula using tree method for this recurrence relation? $$ T(n)=T(n/2)+T(n/3)+\ln(n) $$ I found that it should be like:
$$\sum\limits_{i=0}^{h} \ln \frac{n^{2^{i}}}{(2\cdot3)^{?}}$$
But I have no idea what to write instead of ‘?’, because I didn’t find any relations between this.
You have $$T(n)=ln(n)+T(n/2)+T(n/3)=ln(n)+\left (T(n/2^2)+T(n/(2\cdot 3))+ln(n/2)\right )+\left (T(n/3^2)+T(n/(2\cdot 3))+ln(n/3)\right ),$$ Notice that each time you are paying a factor of $\ln \left (\frac{n}{2^i\cdot 3^j}\right ),$ notice also that everytime you do it, the sum of $i+j$ is preserved as how far did you go. Meaning, if you go back the first recurrence, they add up to $1.$ If you do it two times, they add up to $2.$ In your notation this is given by $i,$ so you have $$\sum _{i=0}^h\binom{h}{i}\ln \left(\frac{n}{2^i\cdot 3^{h-i}}\right ).$$ The binomial is because there are multiple ways to reach $h.$
If you are going all of the way down using $h,$ the longest path should be $\log _2(n),$ and so you have $$\sum _{i=0}^h\binom{h}{i}\ln \left(\frac{n}{2^i\cdot 3^{h-i}}\right )=\sum _{h=0}^{\log _2(n)}\ln \left(\prod _{i=0}^h\frac{n^{\binom{h}{i}}}{2^{i\binom{h}{i}}\cdot 3^{(h-i)\binom{h}{i}}}\right )$$$$=\sum _{h=0}^{\log _2(n)}\ln \left(\frac{n^{\sum _{i=0}^h\binom{h}{i}}}{2^{\sum _{i=0}^hi\binom{h}{i}}\cdot 3^{\sum _{i=0}^h(h-i)\binom{h}{i}}}\right ),$$ recall that $$\sum _{i=0}^hi\binom{h}{i}=\sum _{i=1}^h\binom{i}{1}\binom{h}{i}=\sum _{i=1}^h\binom{h-1}{i-1}\binom{h}{1}=h\cdot 2^{h-1}$$ and so $$\sum_{h=0}^{\log _2(n)}\ln \left(\frac{n^{2^h}}{2^{h\cdot 2^{h-1}}\cdot 3^{h\cdot 2^{h-1}}}\right )$$