Closed form solution of $T(n) = 5T(n-1) + n^2$ [duplicate]
Solving or approximating recurrence relations for sequences of numbers (11 answers)
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}$$
recurrence-relation
TrakTrak
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.
Mr. Sigma.Mr. Sigma.
$\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 '19 at 4:48
$\begingroup$ @ryan Do you mean this solution is not useful? $\endgroup$ – Mr. Sigma. Apr 25 '19 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 '19 at 5:26
$\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 '19 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 '19 at 16:54
Not the answer you're looking for? Browse other questions tagged recurrence-relation or ask your own question.
Solving or approximating recurrence relations for sequences of numbers
Recurrence relations that do not have a closed form solution
Making a conjecture of a closed form
Closed-form solution to recurrence equation
Closed-Form Expression for Recursive Function
How to find closed form solution of linear recursion using recursive tree method