Solución de forma cerrada para la recurrencia

Question

Necesito encontrar una solución de forma cerrada para la siguiente recurrencia:

$T(m) \leq T(\sqrt m) + 1$ , $T(1)=1$

Sinceramente, no tengo ni idea de por dónde empezar. ¡La ayuda sería muy apreciada!

Answer 1

$$T(m^{2^{0}})-T(m^{2^{-1}})\leq 1$$ $$T(m^{2^{-1}})-T(m^{2^{-2}})\leq 1$$ $$.$$ $$.$$ $$.$$ $$T(m^{2^{-(n-1)}})-T(m^{2^{-n}})\leq 1$$

Suma todas las desigualdades (observa que la suma en el LHS es telescópica): $$T(m)-T(m^{2^{-n}})\leq n$$ $$T(m)-n\leq T(m^{2^{-n}})$$

Answer 2

Si estás dispuesto a renunciar a la $T(1)=1$ y sólo definir $T$ en $(1, \infty)$ entonces si denotamos $\lg m =\log_2m$ una solución de forma cerrada (con igualdad, incluso) es $$ T(m) = a + \lg\lg m $$ donde $a$ es un número real arbitrario. Para ver esto, observe $$ \begin{align} T(\sqrt{m})+1&=(a+\lg\lg\sqrt{m})+1\\ &= a+1+\lg\lg(m^{1/2})\\ & =a + 1 +\lg\left(\frac{1}{2}\lg m\right)\\ &= a + 1 + \lg\left(\frac{1}{2}\right)+\lg\lg m\\ &= a + 1 - 1 +\lg\lg m\\ &= a+\lg\lg m = T(m) \end{align} $$ Para ver que no he sacado esto de la nada, la forma habitual de tratar las recurrencias que implican $\sqrt{m}$ es escribir la definición con $m=2^{2^k}$ como lo hizo Amr, y expandirse así: $$ \begin{align} T(2^{2^k}) &= T(2^{2^{k-1}})+1\\ &= T(2^{2^{k-2}})+1+1\\ &= T(2^{2^{k-3}})+3\\ &= T(2^{2^{k-4}})+4\\ \end{align} $$ y así sucesivamente, hasta llegar a $T(2^{2^k}) = T(2^{2^0})+k$ (por lo que el valor inicial de estas recurrencias suele ser 2, en lugar de 1).