3
$\begingroup$

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.

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

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ – Imago Dec 19 '15 at 16:01
  • $\begingroup$ @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)$. $\endgroup$ – Jimmy R. Dec 19 '15 at 16:12
  • $\begingroup$ 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. $\endgroup$ – Imago Dec 19 '15 at 16:28
  • 1
    $\begingroup$ @Imago Oh, sorry the $a_n$'s are scalars, which may depend on $n$. Here $a_n=1$ for all $n$. $\endgroup$ – Jimmy R. Dec 19 '15 at 16:29
  • $\begingroup$ Ah ok, thanks! This was indeed very enlightened! $\endgroup$ – Imago Dec 19 '15 at 16:30
2
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

By inspection:

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

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

$\endgroup$
2
  • $\begingroup$ 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 $. $\endgroup$ – Cloverr Dec 19 '15 at 16:13
  • $\begingroup$ @Nilanjan, you are correct. $\endgroup$ – ً ً Dec 20 '15 at 5:55
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Check the initial conditions. $\endgroup$ – ً ً Dec 19 '15 at 14:18
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.