Question

Encontrar la recurrencia lineal no homogenea de las siguientes ecuaciones:
1. t(n) = 2t(n-1) + n
2. t(n) = 2t(n-1) + (n+5)^(3n)

Si logran resolverlas doy 80 puntos por el resultado

Answer 1

Respuesta:

1.t (n)=2t(n- 1)+n

solución:

Down vote

Accepted

T(n) =2T(n−1)+n=2(2T(n−2)+n−1)+n=4T(n−2)+2(n−1)+n =8T(n−3)+4(n−2)+2(n−1)+n=2kT(n−k)+

k−1

∑

j=0 2j(n−j) =2n−1T(1)+

n−2

∑

j=0 2j(n−j)=2n−1+

n−2

∑

j=0 2j(n−j)

n−2

∑

j=0 2j(n−j) =n

n−2

∑

j=0 2j−

n−2

∑

j=0 j2j=n(2n−1−1)−

n⋅2n−3⋅2n+4

2

=n(2n−1−1)−(n⋅2n−1−3⋅2n−1+2)=3⋅2n−1−n−2

Hence,

T(n)=2n−1+3⋅2n−1−n−2=2n+1−n−2

Explicación paso a paso:

espero te sirva de ayuda