El lector puede estar interesado en notar que existe un recurrencia que podemos resolver exactamente y no sólo para los poderes de dos.
Supongamos que ponemos $$f(n) = 3 f(\lfloor n/2 \rfloor) - 2 f(\lfloor n/4 \rfloor).$$ Esto requiere un valor para $f(0)$ por lo que fijamos $$f(n) = 2n+1 \quad\text{when} \quad n<3.$$
Ahora observe que la función generadora $$g(z) = \frac{1}{1-(3z-2z^2)}$$ codifica el árbol de valores visitado durante la cálculo de $f(n)$ de forma natural.
Dejemos que $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ sea el representación binaria de $n$ . Ahora calculamos una expresión de forma cerrada para $f(n)$ cuando $n\ge 2.$
Caso A. Los dígitos iniciales son dos dígitos uno, es decir $(d_{\lfloor \log_2 n \rfloor} d_{\lfloor \log_2 n \rfloor-1})_2 = (11)_2.$ Entonces los dos valores terminales de la recursión son $n=3$ y $n=1$ .
El caso $n=3$ tiene $f(n)=7$ y por lo tanto da la contribución $$7\times [z^{\lfloor \log_2 n \rfloor - 1}] \frac{1}{1-(3z-2z^2)}.$$ El caso $n=1$ tiene $f(n)=3$ pero el último paso debe haber sido en el $\lfloor n/4 \rfloor$ rama para no ser enrutado a través de $n=3$ , dando $$3\times (-2)\times [z^{\lfloor \log_2 n \rfloor - 2}] \frac{1}{1-(3z-2z^2)}.$$
Caso B. Los dígitos iniciales son un dígito seguido de un cero es decir, un dígito cero. $(d_{\lfloor \log_2 n \rfloor} d_{\lfloor \log_2 n \rfloor-1})_2 = (10)_2.$ Entonces los valores terminales de la recursión son $n=2$ y $n=1$ .
El caso $n=2$ tiene $f(n)=5$ y por lo tanto da la contribución $$5\times [z^{\lfloor \log_2 n \rfloor - 1}] \frac{1}{1-(3z-2z^2)}.$$ El caso $n=1$ tiene $f(n)=3$ pero el último paso debe haber sido en el $\lfloor n/4 \rfloor$ rama para no ser enrutado a través de $n=2$ , dando $$3\times (-2)\times [z^{\lfloor \log_2 n \rfloor - 2}] \frac{1}{1-(3z-2z^2)}.$$
Evaluación. Nótese que por fracciones parciales tenemos que $$[z^q] \frac{1}{1-(3z-2z^2)} = 2^{q+1}-1$$ por lo que obtenemos para el caso A $$ 7 \times 2^{\lfloor \log_2 n \rfloor} - 7 - 6 \times 2^{\lfloor \log_2 n \rfloor-1} + 6 = (14-6) \times 2^{\lfloor \log_2 n \rfloor-1} - 1 = 2^{\lfloor \log_2 n \rfloor+2} - 1$$ y para el caso B $$ 5 \times 2^{\lfloor \log_2 n \rfloor} - 5 - 6 \times 2^{\lfloor \log_2 n \rfloor-1} + 6 = (10-6) \times 2^{\lfloor \log_2 n \rfloor-1} + 1 = 2^{\lfloor \log_2 n \rfloor+1} + 1 $$
Esto produce la secuencia para $n\ge 2$ $$5, 7, 9, 9, 15, 15, 17, 17, 17, 17, 31, 31, 31, 31, 33,\ldots$$ que coincide perfectamente con $f(n).$
Obsérvese que podemos decir que $f(n)\in\Theta(n)$ en cierto sentido ( $2^{\lfloor \log_2 n \rfloor}\in\Theta(n).$ )
Este Enlace MSE muestra una aplicación más sofisticada del truco con la función generadora.
