En Concrete Mathematics , Graham, Knuth y Patashnik describen la siguiente técnica para convertir las relaciones de recurrencia de primer orden de la forma
anorteTnorte=bnorteTnorte - 1+Cnorte
en sumatorias.
- Paso 1. Encuentra una funciónsnorte
con la propiedad que
snortebnorte=snorte - 1anorte - 1
- Paso 2. Multiplica ambos lados de la recurrencia porsnorte
, dandote
snorteanorteTnorte=snortebnorteTnorte - 1+snorteCnorte
o equivalente,
snorteanorteTnorte=snorte - 1anorte - 1Tnorte - 1+snorteCnorte
- Paso 3. Definir
Snorte=snorteanorteTnorte
y reescribir la recurrencia como
Snorte=Snorte - 1+snorteCnorte
- Paso 4. EscribeSnorte
como la suma
Snorte=s0a0T0+∑k = 1norteskCk=s1b1T0+∑k = 1norteskCk
- Paso 5. Encuentra una forma cerrada para la sumaSnorte
.
- Paso 6. Para encontrar la forma cerrada deTnorte
, simplemente multiplica la forma cerrada deSnorte
por1snorteanorte
.
Adicionalmente, alegan que el valor adecuado desnorte
siempre viene dado por
snorte=a1a2⋯anorte - 1b2b3⋯bnorte
que justifican razonando de la siguiente manera:
Desdebnortesnorte=snorte - 1anorte - 1
, lo sabemos
snorte=snorte - 1anorte - 1bnorte
insertando el valor de
snorte - 1
, encontramos que esto es igual a
snorte - 2anorte - 2anorte - 1bnorte - 1bnorte
y al continuar de esta manera, finalmente encontramos que
snorte=a1a2⋯anorte - 1b2b3⋯bnorte
Pero cuando sigo de esta manera lo que encuentro es que
snorte=s1a1a2⋯anorte - 1b2b3⋯bnorte
Observe las1
en el numerador . ¿Qué estoy haciendo mal aquí?
Misha Lavrov