Hace un par de meses, pregunté este y recibí una respuesta sólida que proporcionaba un nivel de detalle y análisis exhaustivo sobre la lógica detrás de la prueba inicial para $A(n) = f(n)$ .
Para aclarar, su objetivo es demostrar que esta recurrencia:
$$f(1) = \alpha;$$ $$f(2n) = 2f(n) + \beta;$$ $$f(2n + 1) = 2f(n) + \gamma;$$
es equivalente a la siguiente forma cerrada:
$$f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma;$$
Deduciendo eso,
$$A(n) = 2^m;$$ $$B(n) = 2^m - l - 1;$$ $$C(n) = l$$
Sin embargo, esto requiere una prueba para estar seguro.
Para ello, primero demuestra que $A(n) = 2^m$ a través de la siguiente recurrencia:
$$A(1) = 1;$$ $$A(2n) = 2A(n) + \beta$$ $$A(2n + 1) = 2A(n) + \gamma$$
para $(\alpha, \beta, \gamma) = (1, 0, 0)$
Entonces, utilizando $(\alpha, \beta, \gamma) = (1, 0, 1)$ que proporciona:
$$1 = \alpha;$$ $$2n = 2 \times 1 + \beta$$ $$2n + 1 = 2 \times 1 + \gamma$$
Que satisface $f(n) = n$ .
Para $f(n) = 1$ , proporciona:
$$1 = \alpha;$$ $$1 = 2\times1 + \beta$$ $$1 = 2\times1 + \gamma$$
Lo que nos da $(\alpha, \beta, \gamma) = (1, -1, -1)$
Lo que estoy tratando de entender es el panorama general detrás de todo esto. Entiendo que esta técnica de generalización para $f$ puede utilizarse como marco para resolver diferentes tipos de problemas utilizando el hecho de que podemos representar esencialmente cualquier valor $n$ como $2^m + l$ y luego derivar una recurrencia de la forma dada, utilizando constantes arbitrarias $(\alpha, \beta, \gamma)$ para algún propósito arbitrario.
Lo que no entiendo es... ¿cómo es exactamente que estas pruebas demuestran que esto es cierto? Entiendo, dada la pregunta que he proporcionado y su correspondiente respuesta, que están diseñadas para llenar vacíos en áreas donde se representa $f(n)$ a través de alguna forma de estas constantes requiere que $f(n)$ estar definida para todo n, y que este es un medio de proporcionar dicha prueba.
¿Cómo es que estas declaraciones muestran este hecho cuando requiere que $(\alpha, \beta, \gamma)$ ¿se definen a valores específicos para cada caso?
