Solution to the recurrence relation I came across following recurrence relation:


*

*$T(1) = 1, $

*$T(2) = 3,$

*$T(n) = T(n-1) + (2n-2)$ for $n > 2$.


And the solution to this recurrence relation is given as 
$$T(n)=n^2-n+1$$
However I am not able to get how this is obtained.
 A: Write the given relation as $$T(k)-T(k-1)=2(k-1)$$ and sum up from $k=2$ to $n$ to obtain $$\sum_{k=2}^{n}T(k)-T(k-1)=2\sum_{k=2}^n(k-1) \tag{1}$$ The LHS is a telescopic sum $$\sum_{k=2}^{n}T(k)-T(k-1)=T(n)-T(1)$$ and the RHS is the sum of all integers from $1$ to $n-1$ so $$2\sum_{k=2}^n(k-1)=2\sum_{k=1}^{n-1}k=2\frac{(n-1)(n)}{2}=n^2-n$$ so putting these back in $(1)$ gives $$T(n)-T(1)=n^2-n\implies T(n)=n^2-n+1$$
A: One way to solve it can be like this, 
Note that the recurrence always stop at T(2), we have for $ n > 3 $
\begin{align}
T(n) &= T(2) + \sum_{k=3}^n(2k-2)\\
     &= 3 \, + 2\sum_{k=3}^nk \, - \, 2(n-3+1)\\
     &= 3 \, + 2\left(\frac{n^2+n-6}{2}\right) -2n + 4\\
     &= n^2 - n + 1
\end{align}
A: By inspection:
$T(n) = T(n-1) + (2n-2)$
$\Sigma{(2n-2)}= \frac{(2n-2)(2n-2+1)}{2} = 2n^2-3n+1$
A: By this recurrence relation $T(n)=T(n−1)+(2n−2)$ for $n>2$, we have
\begin{align*}
& T(3)-T(2)=4, \\
& T(4)-T(3)=6, \\
& T(5)-T(4)=8, \\
& \ldots \ldots, \\
& T(n-1)-T(n−2)=(2n−4), \\  
& T(n)-T(n−1)=(2n−2). \\  
\end{align*}
A sum of the left hand side is $T(n)-T(2)$ and a sum of the right hand side is $n^{2}-n-2$ (a arithmetic sequence). Therefore, 
\begin{align*}
T(n)=T(2)+n^{2}-n-2=n^{2}-n+1.
\end{align*}
A: $C=const$ is the solution of the homogeneous equation $T(n)=T(n-1)$ and $n^2-n$ is a solution of the inhomogeneous equation since $n^2-n=(n-1)^2-(n-1)+2n-2$
