1
$\begingroup$

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?

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

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. $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.