Ecuación de recurrencia

Question

Dada la siguiente ecuación de recurrencia:

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

¿Cómo plantearías esta ecuación para poder resolverla utilizando el telescopio?

Gracias de antemano.

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$

Si sumas todo esto, conseguirás lo que quieres.

Para aquellos $T_k$ que $k$ no puede expresarse como la forma $2^n-1$ donde $n\in\mathbb N$ no están definidos.