Cómo resolver esta relación de recurrencia, [matemática] T (n) = 2T (n-1) + n [/ matemática] dada, [matemática] T (0) = 0 [/ matemática]

Answer 1

Para resolver este tipo de recursiones, siempre es mejor escribir los primeros términos.

Dado, [matemáticas] T (0) = 0 [/ matemáticas]

[matemáticas] T (1) = 1 [/ matemáticas]

[matemáticas] T (2) = 2 ^ {1} \ cdot 1 + 2 ^ {0} \ cdot 2 [/ matemáticas]

[matemáticas] T (3) = 2 (2 ^ {1} \ cdot 1 + 2 ^ {0} \ cdot 2) + 3 = 2 ^ {2} \ cdot 1 + 2 ^ {1} \ cdot 2 + 2 ^ {0} \ cdot 3 [/ matemáticas]

[matemáticas] T (4) = 2 (2 ^ {2} \ cdot 1 + 2 ^ {1} \ cdot 2 + 2 ^ {0} \ cdot 3) + 4 = 2 ^ {3} \ cdot 1 + 2 ^ {2} \ cdot 2 + 2 ^ {1} \ cdot 3 + 2 ^ {0} \ cdot 4 [/ matemáticas]

[matemáticas] T (5) = 2 (2 ^ {3} \ cdot 1 + 2 ^ {2} \ cdot 2 + 2 ^ {1} \ cdot 3 + 2 ^ {0} \ cdot 4) + 5 = 2 ^ {4} \ cdot 1 + 2 ^ {3} \ cdot 2 + 2 ^ {2} \ cdot 3 + 2 ^ {1} \ cdot 4 + 2 ^ {0} \ cdot 5 [/ matemática]

Claramente, puedes ver un patrón emergente. Para [matemáticas] n = k [/ matemáticas], [matemáticas] T (k) [/ matemáticas] toma la forma,

[matemáticas] T (k) = \ sum_ {i = 1} ^ {k} 2 ^ {ki} i [/ matemáticas]

que se puede probar usando inducción.

La solución de forma cerrada toma la forma,

[matemáticas] T (k) = 2 ^ {k + 1} – 2 – k [/ matemáticas]

que se puede probar tomando la diferencia entre [matemáticas] T (k) [/ matemáticas] y [matemáticas] 2T (k) [/ matemáticas] y luego sumando la serie geométrica resultante.

Answer 2

Divide ambos lados de la ecuación.

[matemáticas] T (k) – 2 T (k-1) = k [/ matemáticas]

por [matemáticas] 2 ^ k [/ matemáticas] para obtener

[matemáticas] \ displaystyle \ frac {T (k)} {2 ^ k} – \ displaystyle \ frac {T (k-1)} {2 ^ {k-1}} = \ displaystyle \ frac {k} {2 ^ k} [/ matemáticas].

Sumando de [matemáticas] k = 1 [/ matemáticas] a [matemáticas] k = n [/ matemáticas], obtenemos

[matemáticas] \ displaystyle \ sum_ {k = 1} ^ n \ left (\ frac {T (k)} {2 ^ k} – \ frac {T (k-1)} {2 ^ {k-1}} \ right) = \ displaystyle \ sum_ {k = 1} ^ n \ frac {k} {2 ^ k} [/ math].

La suma de los “telescopios” de LHS a

[matemáticas] \ displaystyle \ frac {T (n)} {2 ^ n} – \ displaystyle \ frac {T (0)} {1} = \ displaystyle \ frac {T (n)} {2 ^ n} [/ matemáticas].

Por lo tanto

[matemática] T (n) = \ displaystyle \ sum_ {k = 1} ^ nk \ cdot 2 ^ {nk} [/ matemática]. [matemática]… (1) [/ matemática]

Multiplicando ambos lados de la ecuación. (1) por 2 da

[matemáticas] 2 T (n) = \ displaystyle \ sum_ {k = 1} ^ nk \ cdot 2 ^ {n-k + 1} = \ displaystyle \ sum_ {k = 0} ^ {n-1} (k + 1) \ cdot 2 ^ {nk} [/ math]. [Math]… (2) [/ math]

Restando ambos lados de la ecuación. (1) desde ambos lados de la ec. (2), obtenemos

[matemáticas] T (n) = 2 ^ n + \ displaystyle \ sum_ {k = 1} ^ {n-1} 2 ^ {nk} – n = \ displaystyle \ sum_ {k = 0} ^ {n-1} 2 ^ {nk} – n = (2 ^ {n + 1} -1) – 1 – n = 2 ^ {n + 1} – n – 2 [/ matemática].

---

Se puede aplicar el mismo método para resolver las recurrencias del formulario.

[matemáticas] T (n) = c \ cdot T (n_1) + f (n), \ quad T (0) = T_0 [/ matemáticas],

siempre que [math] f (n) [/ math] sea un polinomio en [math] n [/ math] o de la forma [math] {\ alpha} ^ n [/ math], donde [math] \ alpha [/ matemáticas] es una constante.

Dividir entre [matemática] c ^ k [/ matemática] en lugar de [matemática] 2 ^ k [/ matemática] y sumar la serie como se indica arriba conduce a

[matemáticas] T (n) = c ^ n \ displaystyle \ sum_ {k = 1} ^ n \ displaystyle \ frac {f (k)} {c ^ k} + c ^ n \ cdot T_0. … (3) [/ matemáticas]

Encontrar una expresión de forma cerrada para la serie en la ecuación. (3) depende de [matemáticas] f (k) [/ matemáticas].