This question already has an answer here:

How to find the closed form solution of this equation? Is there a repeatable pattern for solving this equation?

$$T(n) = \begin{cases} 1 & n = 1\\ 5T(n-1) + n^2 & \text{otherwise} \end{cases}$$


marked as duplicate by ryan, Discrete lizard Apr 25 at 5:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


How to find the closed form solution of this equation?

This is linear nonhomogeneous recurrence relation of the form $a_n = a_n^{h}+a_n^{p}$ where former expression in the right hand side is homogeneous solution while later one particular. Now, $a_n^p$ becomes $p_2n^2+p_1n+p_0$ whereas $a_n^h$ becomes $\alpha5^n$. Now solve them.

Another straightforward approach is to recursively solve the equation as follows $$\begin{align*} T(n) &= 5\cdot T(n-1)+n^2 \\ &= 5[5\cdot T(n-2)+(n-1)^2]+n^2 \\ &= 5^2T(n-2)+5(n-1)^2 + n^2 \\ &= 5^3T(n-3)+5^2(n-2)^2 + 5(n-1)^2 + n^2 \\ & \vdots\\ &= \sum_{k=0}^{n-1}5^{n-k}\cdot k^2 \end{align*}$$

Is there a repeatable pattern for solving this equation?

The very word recurrence implies pattern.

  • 3
    $\begingroup$ It may also be worth noting that deducing the sum is pure extrapolation at this point. You would also need to prove it is equivalent to $T(n)$ by induction or some other method. Though, this is a minor detail and should be relatively trivial. $\endgroup$ – ryan Apr 25 at 4:48
  • $\begingroup$ @ryan Do you mean this solution is not useful? $\endgroup$ – Mr. Sigma. Apr 25 at 5:14
  • $\begingroup$ Not at all, the solution is entirely correct, but it is based on intuition, or pattern extrapolation. This is a good thing though, because the extrapolation gives us this "guess" for the summation, then we can formally prove equivalence between $T(n)$ and this sum with induction. $\endgroup$ – ryan Apr 25 at 5:26
  • 1
    $\begingroup$ @ryan Your comment was dead on, but I'd argue that at the introduction level, it's anything but a minor detail. $\endgroup$ – Rick Decker Apr 25 at 12:53
  • $\begingroup$ @RickDecker that's fair too, maybe minor detail was not the best description. My intent was to convey it is important, while proving it is usually not all that difficult, so it's often omitted. I typically omit it and say "this can be proven correct via induction, etc." I would agree though, at an introductory level, I would want to see the proof (if I were grading an assignment or something). $\endgroup$ – ryan Apr 25 at 16:54

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