I tried to solve the recurrence relation $ T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $ n^3$ , the second level will be $ 6^1(n-1)^3$ , the third will be $ 6^2 (n-2)^3$ , and so on.

The formula as I understood it is: $ \sum_{i=0}^n 6^i(n-i)^3$ .

After entering this in Wolfram, the result is:

$ $ \sum_{i=0}^n 6^i(n-i)^3 = \frac{1}{625}(-125n^3-450n^2-630n+366(6^n-1)). $ $

And it doesn’t look like a valid solution. Did I miss anything?