# Help solving a recursion function T(n) = T(n-2) +3

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?

• 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). – Winther Sep 19 '14 at 4:02
• @Winther I pretty much though the same but I guess lab derived the closed form. – Krimson Sep 19 '14 at 4:07

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$

• 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? – Krimson Sep 19 '14 at 4:06
• 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$ – lab bhattacharjee Sep 19 '14 at 4:08
• @Krimson, How about the other answer? – lab bhattacharjee Sep 19 '14 at 4:15
• @SteveJessop, Thanks for your observation. Rectified – lab bhattacharjee Sep 19 '14 at 9:26

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

• I found this one to be more intuitive. +1 – Krimson Sep 19 '14 at 4:40