# Why $T(n)=6T(n-1) + n^3$ has such a mess solution?

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?

• If that is the solution, that would be incredibly clean. – gnasher729 May 3 '20 at 23:04
• (Asymptotic ballpark assessment?) – greybeard May 4 '20 at 7:13

## 1 Answer

I'm not sure why you think this solution is invalid. It implies that $$\sum_{i=0}^n 6^i(n-i)^3 \sim \frac{366}{625} 6^n,$$ and in particular, $$\sum_{i=0}^n 6^i(n-i)^3 = \Theta(6^n).$$ You can also check it for particular values of $$n$$.

For example, when $$n = 0$$ you clearly get zero, and for $$n = 1$$ you get $$\frac{-125-450-630+366 \cdot 5}{625} = 1 = 6^0 (1-0)^3 + 6^1 (1-1)^3.$$