# Solution to the recurrence relation

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.

• Try to use induction. – Mahbub Alam Dec 19 '15 at 14:03
• Check the initial conditions from your given solution $T(1) = 1 \neq 0$. – ً ً Dec 19 '15 at 14:04
• Extremely sorry to all here. It says its $T(1)=0$, but after reading more, I realize it should be $T(1)=1$. – Maha Dec 19 '15 at 15:50

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

• Great solution :) Tried it myself, it always surprises me how neatly those sequences collapse to a closed form by beginning to look at the difference of two following terms. – Imago Dec 19 '15 at 16:01
• @Imago Indeed! This method works if $T(n)=T(n-1)+p(n)$ or in a more general version for all relation of the form $T(n)=a_nT(n-1)+p(n)$. – Jimmy R. Dec 19 '15 at 16:12
• I assume p(n) here denotes any arbitrary polynomial. I am a bit unsure about the $a_n$ though. Polynomials have a nice structure, however mixing another sequence into these equation may turn out to be very ugly. – Imago Dec 19 '15 at 16:28
• @Imago Oh, sorry the $a_n$'s are scalars, which may depend on $n$. Here $a_n=1$ for all $n$. – Jimmy R. Dec 19 '15 at 16:29
• Ah ok, thanks! This was indeed very enlightened! – Imago Dec 19 '15 at 16:30

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}

By inspection:

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

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

• We have by your solution $T(3) = T(2) + (2.3^2) - (3.3) + 1$ so it evaluates to $T(3) = 13$ but $T(3)$ should be $7$. – Cloverr Dec 19 '15 at 16:13
• @Nilanjan, you are correct. – ً ً Dec 20 '15 at 5:55

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

• Check the initial conditions. – ً ً Dec 19 '15 at 14:18

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