Recurrence equation

Question

Given the following recurrence equation:

$T(n)=T\left(\dfrac{n-1}{2}\right)+2$ , $T(1)=0$

How would you set this equation up in order to allow you to solve it using telescoping?

Thanks in advance.

Answer 1

$T(n)=T\left(\dfrac{n-1}{2}\right)+2$

$T(2^n-1)=T\left(\dfrac{2^n-2}{2}\right)+2$

$T(2^n-1)=T(2^{n-1}-1)+2$

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

$T(n)=2\log_2(n+1)+C$

$T(1)=0$ :

$2+C=0$

$C=-2$

$\therefore T(n)=2\log_2(n+1)-2$

Answer 2

$T_1=0$

$T_3=T_1+2$

$T_7=T_3+2$

$T_{15}=T_7+2$

$...$

$T_{2^n-1}=T_{2^{n-1}-1}+2$

Sum up all these, you'll get what you want.

For those $T_k$, which $k$ can't be expressed as the form $2^n-1$ where $n\in\mathbb N$, are not defined.