Solution to the recurrence relation

Question

I came across following recurrence relation:

1. $T(1) = 1, $
2. $T(2) = 3,$
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.

Answer 1

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

Answer 2

By inspection:

$T(n) = T(n-1) + (2n-2)$

$\Sigma{(2n-2)}= \frac{(2n-2)(2n-2+1)}{2} = 2n^2-3n+1$

Answer 3

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*}

Answer 4

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

Answer 5

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}