I am trying to solve the 4.6-2 question in CLRS book which is <br> $T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$ While solving the above equation I reach the following point: 1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^j)\right) $ when I searched online, I saw people have solved this as below: 2. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^j)\right) $ 3. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $ 4. $T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $ 5. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $ I did not understand the following points: - $ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs? - In equation 4, after calculating the summation, how did the subtraction between logs turn to sum? - There is a small o in equation 4, then how can we write theta in equation 5.