How to solve the recurrence $()=5(/2)+^3()$ using iteration method How do we solve the recurrence $()=5(/2)+^3()$ using the Iteration method?
I solved the recurrence using a master method - master method
Now using the iteration method
$()=5(/2)+3() = 5(5T(/4)+(n/2)^3)*log(n/2))+n^3*logn$ $=$ ... $= 5^i(n/2^i)+n^3*log(n) * ∑(n^3*(5^k) *log(n/2^k) ) / 8^k) $
How is it equal to $Θ(n^3log(n))$ ?

Do the substitution:
$$\begin{array} {rcl}
T(n) &=& n^3\log(n) \\
     &+& 5(n/2)^3\log(n/2)\\
     &+& 5^2(n/2^2)^3\log(n/2^2)\\
     &+& 5^3(n/2^3)^3\log(n/2^3)\\
     &+& \dots \\
\\
&=& n^3\log(n) \\
     &+& 5/2^3 n^3 (\log n - \log 2)\\
     &+& 5^2/2^6 n^3 (\log n - 2\log 2)\\
     &+& 5^3/2^9 n^3 (\log n - 3 \log 2)\\
     &+& \dots \\
\\
&=& n^3\log(n) (1 + 5/2^3 + 5^2/2^6 + 5^3/2^9 + \dots) \\
&-& n^3\log(2) (0 + 1\cdot 5/2^3 + 2\cdot 5^2/2^6 + 3 \cdot 5^3/2^9 + \dots )\\
\end{array}$$
That's a geometrics series and an arithmetico-geometric series.  But you don't actually need to calculate them to get the asymptotic behavior, since it is just going to be some positive constants.
