Esto puede parecer una pregunta estúpida, y estoy bastante seguro de saber la respuesta a esta pregunta, pero no estoy seguro.
De todos modos, en la página 14 de Concrete Mathematics, el autor acaba de terminar de repasar el problema de Josefo:
Josephus
$$ J(1) = 1;$$ $$ J(2n) = 2J(n) - 1;$$ $$ J(2n + 1) = 2J(n) + 1 $$
A continuación, obtiene una representación de forma más cerrada (a mi entender) de $J(n)$ , siendo:
$$ J(2^m + l) = 2l + 1$$
donde,
$$0 \le l < 2^m; n = 2^m + l, \text{for} \space n \ge 1$$
En general, para cada versión de $J$ define tres constantes correspondientes: $\alpha$ , $\beta$ , $\gamma$ :
Recurrencia 1.11 (según el libro)
Dejemos que $f(n)$ representan la forma general de $J(n)$ :
$$ f(1) = \alpha $$ $$ f(2n) = 2f(n) + \beta$$ $$ f(2n + 1) = 2f(n) + \gamma$$
Dónde $J(n) \implies (\alpha, \beta, \gamma) = (1, -1, 1)$
A continuación, deduce una hipótesis, que implica esta forma de $f(n)$ :
$$f(n) = \alpha A(n) + \beta B(n) + \gamma C(n)$$
donde,
$$ A(n) = 2^m$$ $$ B(n) = 2^m - 1 - l$$ $$ C(n) = l$$
Así, comienza su prueba "eligiendo valores particulares y combinándolos"; En particular, selecciona las constantes $(\alpha, \beta, \gamma) = (1, 0, 0)$ . Esto implica que $f(n) = A(n)$ .
El resultado es el siguiente:
$$ A(1) = 1; $$ $$ A(2n) = 2A(n), \text{for} \space n \ge 1 $$ $$ A(2n + 1) = 2A(n), \text{for} \space n \ge 1 $$
Mi confusión proviene del hecho de que, de repente, estamos mapeando $A(2n + 1) = 2A(n)$ con un 1 que se come la función...
¿Cómo es que $A(2n + 1) = A(2n) = 2A(n)$ ?
¿Significa esto que
$$ A(2n + 1) = 2A(n) + 1\gamma$$
con $\gamma = 0$ ?
