Pregunta sobre la técnica de Graham, Knuth y Patashnik para convertir recurrencias de primer orden en sumatorias

En Concrete Mathematics , Graham, Knuth y Patashnik describen la siguiente técnica para convertir las relaciones de recurrencia de primer orden de la forma

a norte T norte = b norte T norte 1 + C norte

en sumatorias.

  • Paso 1. Encuentra una función s norte con la propiedad que
    s norte b norte = s norte 1 a norte 1
  • Paso 2. Multiplica ambos lados de la recurrencia por s norte , dandote
    s norte a norte T norte = s norte b norte T norte 1 + s norte C norte
    o equivalente,
    s norte a norte T norte = s norte 1 a norte 1 T norte 1 + s norte C norte
  • Paso 3. Definir
    S norte = s norte a norte T norte
    y reescribir la recurrencia como
    S norte = S norte 1 + s norte C norte
  • Paso 4. Escribe S norte como la suma
    S norte = s 0 a 0 T 0 + k = 1 norte s k C k = s 1 b 1 T 0 + k = 1 norte s k C k
  • Paso 5. Encuentra una forma cerrada para la suma S norte .
  • Paso 6. Para encontrar la forma cerrada de T norte , simplemente multiplica la forma cerrada de S norte por 1 s norte a norte .

Adicionalmente, alegan que el valor adecuado de s norte siempre viene dado por

s norte = a 1 a 2 a norte 1 b 2 b 3 b norte
que justifican razonando de la siguiente manera:

Desde b norte s norte = s norte 1 a norte 1 , lo sabemos

s norte = s norte 1 a norte 1 b norte
insertando el valor de s norte 1 , encontramos que esto es igual a
s norte 2 a norte 2 a norte 1 b norte 1 b norte
y al continuar de esta manera, finalmente encontramos que
s norte = a 1 a 2 a norte 1 b 2 b 3 b norte
Pero cuando sigo de esta manera lo que encuentro es que
s norte = s 1 a 1 a 2 a norte 1 b 2 b 3 b norte
Observe la s 1 en el numerador . ¿Qué estoy haciendo mal aquí?

Respuestas (1)

s 1 no está definido si definimos s norte = a 1 a 2 . . . a norte 1 b 2 b 3 . . . b norte , porque hay b 2 en el denominador donde norte = 1 . si defines s 1 = 1 , el problema se resolverá.

A los ojos de Graham Knuth y Patashnik, a 1 a 2 . . . a norte 1 b 2 b 3 . . . b norte sería una forma abreviada de dividir 1 i norte 1 a i por 2 i norte b i . Cuando norte = 1 , ambos productos están vacíos, por lo que s 1 = 1 1 = 1 . (No es que el valor de s 1 importa mucho, siempre que sea distinto de cero.)