1
$\begingroup$

I have the following recursion function:

$T(1) = 0$
$T(n) = T(n-2) + 3$
where n is odd integers

I know the closed form of this is:
$T(n) = \frac{3n-3}{2}$ but this was purly by guessing.

Is it possible to show how you can derive the close form?

$\endgroup$
  • $\begingroup$ The 'guessing it' (educated guessing) is in fact not far from the standard method (which I'm sure someone will tell you about soon, or you can read about it here). $\endgroup$ – Winther Sep 19 '14 at 4:02
  • $\begingroup$ @Winther I pretty much though the same but I guess lab derived the closed form. $\endgroup$ – Krimson Sep 19 '14 at 4:07
3
$\begingroup$

We have $T(n)=T(n-2)+3$

Setting $T(n)=S(n)+an+b,$

$S(n)+an+b=S(n-2)+a(n-2)+b+3\iff S(n)=S(n-2)+3-2a$

Set $2a=3$ to find $S(n)=S(n-2)=\cdots=S(1)=T(1)-a-b=0-\dfrac32-b$

$T(n)=\left(-\dfrac32-b\right)+\dfrac32n+b=\dfrac{3n-3}2$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for the answer! Would you mind telling me the process you went through, particularly the "Setting T(n)=S(n)+an+b" it this a standard way to solve such type of relation? $\endgroup$ – Krimson Sep 19 '14 at 4:06
  • 1
    $\begingroup$ As $T(n)-T(n-2)=3$ which is constant, we can derive $T(n)=an+b$ Has it been $T(n)-T(n-2)=O(n^m),$ we can derive $T(n)=An^{m+1}+\cdots$ $\endgroup$ – lab bhattacharjee Sep 19 '14 at 4:08
  • $\begingroup$ @Krimson, How about the other answer? $\endgroup$ – lab bhattacharjee Sep 19 '14 at 4:15
  • $\begingroup$ @SteveJessop, Thanks for your observation. Rectified $\endgroup$ – lab bhattacharjee Sep 19 '14 at 9:26
2
$\begingroup$

Setting $n=2m+1, n-2=2m-1=2(m-1)-1,T(2m+1)=S(m),$

$S(m)-S(m-1)=3, S(0)=T(1)=0$

So, $S(m)$ is the $(m+1)$th term of an Arithmetic Progression with $S(0)=0,$ common difference $=3$

$\implies S(m)=S(0)+(m+1-1)\cdot 3=3m=3\cdot\dfrac{n-1}2$

But $S(m)=T(2m+1)=T(n)$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I found this one to be more intuitive. +1 $\endgroup$ – Krimson Sep 19 '14 at 4:40

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.