Solution to the recurrence relation

Question

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.

Check the initial conditions from your given solution $T(1) = 1 \neq 0$. — Mithlesh Upadhyay, 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$. — Mahesha999, Dec 19 '15 at 15:50

Jimmy R. · Accepted Answer · 2015-12-19T15:56:07.527

4

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

edited Dec 19 '15 at 15:56

answered Dec 19 '15 at 14:32

Jimmy R.

35,868

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
1

@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

Cloverr · Answer 2 · 2016-02-02T12:43:16.360

2

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}

edited Feb 02 '16 at 12:43

answered Dec 19 '15 at 17:20

Cloverr

900

score 1 · Answer 3 · answered Dec 19 '15 at 14:13

1

By inspection:

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

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

answered Dec 19 '15 at 14:13

Mithlesh Upadhyay

4,787

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. – Mithlesh Upadhyay Dec 20 '15 at 05:55

bing · Answer 4 · 2015-12-19T14:19:41.217

1

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

edited Dec 19 '15 at 14:19

answered Dec 19 '15 at 14:16

bing

1,160

Check the initial conditions. – Mithlesh Upadhyay Dec 19 '15 at 14:18

score 0 · Answer 5 · answered Dec 19 '15 at 14:30

0

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

answered Dec 19 '15 at 14:30

Dr. Sonnhard Graubner

95,283

Solution to the recurrence relation

5 Answers5