Solucionar $T(n) = 1 +\sum_{i=0}^{n-1}T(i)$

Question

Para la recurrencia definida por

$$T(n) = 1 +\sum_{i=0}^{n-1}T(i)$$

Aparentemente $T(n) = 2^n$ .. pero yo no la veo. Esta recurrencia aparece durante el análisis de la Barra de Corte de Problema. Sigo buscando para encontrar un punto de vista para mirar a este problema, donde los factores de 2 de pop ..

Answer 1

Establecimiento $n=m+1,m$

$$T(m+1) = 1 +\sum_{i=0}^mT(i)$$

$$T(m) = 1 +\sum_{i=0}^{m-1}T(i)$$

En La Resta,

$$T(m+1)-T(m)=T(m)\iff T(m+1)=?$$

Answer 2

Podemos ir hacia atrás, comprobando la identidad:

$$1 + 2^0 + 2^1 + 2^2... 2^n = 2^{n+1}$$

Utilizamos fuerte de inducción: supongamos que es cierto que:

$$1+ 2^0 + 2^1 ... 2^{n-1} = 2^n$ $ , entonces es claro que la declaración original es simplemente:

$$(1 + 2^0 + 2^1 ... 2^{n-1}) + 2^n = 2*2^n = 2^{n+1}$$

Ahora a ver que:

$$1 + 2^0 = 1 + 1 = 2^1$$

Por lo tanto esto nos han demostrado que este patrón de siempre de titular, ya que desde nuestra más recientemente demostrado con el caso base caso podemos utilizar el medio de la declaración de demostrar que es verdadera para cualquier n.