Algorithms: Recurence Relation Can someone please help me solve this recurrence relation using back substitution method:
$$T(n) = T(n-1) + n(n-1)$$
Base case is T(1)=1. Also, what is the asymptotic notation?
Explanation of steps would be greatly appreciated.
 A: HINT:
If we assume $T(n)$ to be polynomial $=a_rn^r+a_{r-1}n^{r-1}+\cdots+a_1n+a_0$ where $a_i$s are independent of $n$
$$T(n)-T(n-1)=a_r\cdot r\cdot n^{r-1}+\cdots$$
$$\implies r-1=2\implies r=3 $$
Now, compare the coefficients of different powers $(3,2,1,0)$ of $n$ to determine $a_r$s where $r=3,2,1,0$
A: The homogeneous equation $S(n)=S(n-1)$ is solved by $S(n)=A$
The particular solution to $T(n)-T(n-1)=n(n-1)$ is expressed in terms of a third degree polynomial in $n$ (difference is quadratic).
The intelligent guess is $T(n)=B(n+1)n(n-1)$ so that $T(n-1)=Bn(n-1)(n-2)$ - this gives a common factor $n(n-1)$ and substituting we see we need $B=\frac 13$ so that the general solution is $$T(n)=\frac 13 (n+1)n(n-1)+A$$
If $T(1) = 1$ we have $A=1$.
A: *

*Start with $n=1$:  $T(1) = T(0)$.

*Next, try $n=2$:   $T(2) = T(1) + 2 = T(0) + 2$. Let $T(0) = a$, so $T(2) = a+2$.

*Then, try $n=3$:   $T(3) = T(2) + 3(2) = a+2+6 = a+8$.

*$n=4$:  $T(4) = T(3) + 4(3) = a+2+6+12 = a+20$.

*$n=5$:  $T(5) = T(4) + 5(4) = a+2(1)+3(2)+4(3)+5(4) = a+40$.


The pattern reveals itself explicitly if you do not simplify everything in advance.
It looks like
$T(k) = a + 2(1) + \ldots + k(k-1) = a + \sum_{j=1}^{k-1} j(j+1) = a + \sum_{j=1}^{k-1} j^2 + \sum_{j=1}^{k-1} j$.
Now you can use usual formulas for sum of consecutive integers and consecutive integers, squared.
Oh, looks like $a=1$.
A: Using magic to solve
$T(n) = T(n-1) + n(n-1)$.
Since
$(n+1)n(n-1)-n(n-1)(n-2)
=n(n-1)\left((n+1)-(n-2)\right)
=3n(n-1)
$,
$(n+1)n(n-1)/3
=n(n-1)(n-2)/3
+n(n-1)
$,
so
$\begin{align}
0
&=T(n)- T(n-1) - n(n-1)\\
&=(T(n)-(n+1)n(n-1)/3)- (T(n-1)-n(n-1)(n-2)/3
-n(n-1)) - n(n-1)\\
&=(T(n)-(n+1)n(n-1)/3)- (T(n-1)-n(n-1)(n-2)/3)\\
\end{align}
$
Therefore,
$T(n)-(n+1)n(n-1)/3)$
is constant for all $n$.
Since $T(1) = 1$,
$T(n)-(n+1)n(n-1)/3)=1$
for all $n$,
or
$T(n)=(n+1)n(n-1)/3)+1$
for all $n$.
