Demostrar que la secuencia con $T(0)=1$ y $T(n) = 1 + \sum_{j=0}^{n-1}T(j)$ viene dada por $T(n)=2^n$

Question

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

Demostrar que $T(n) = 2^n$ .

Sé cómo demostrarlo por inducción, pero me gustaría saber cómo demostrarlo utilizando los primeros principios.

Editar: La forma en que quiero resolver este problema es manipular $T(n)$ de tal manera que termine como $2^n$ .

Answer 1

Claramente, $$T(n+1)=1+T(n)+\sum_{j=0}^{n-1}T(j)=T(n)+T(n)=2T(n)$$ Así que, $(T(n))_n$ es una progresión geométrica con relación común $2$ y comienza en $1$ . Es decir $T(n)=2^n$ .

Answer 2

La pieza más fea de la definición $T_n = 1 + \sum\limits_{k=0}^{n-1} T_{k}$ es la suma. Primero hay que intentar deshacerse de ella. Tenemos $$T_{n+1} - T_n = \left( 1 + \sum_{k=0}^n T_k \right) - \left( 1 + \sum_{k=0}^{n-1}T_k \right) = T_n \quad\implies\quad T_{n+1} = 2T_n$$

El resto es obvio.

Esta es una táctica común para atacar un problema. Identificas la pieza más fea y dura e intentas deshacerte de ella. Si se puede repetir este procedimiento y deshacerse de todos los elementos desagradables, lo que se debe/podría hacer a continuación suele ser obvio.

Answer 3

Este es sólo el método de fuerza bruta. Obviamente es un exceso en este caso, pero creo que vale la pena aprenderlo. Pon: $$ f(x)=\sum_{j=0}^{+\infty}T(j)\, x^j. $$ La relación de recurrencia da entonces $f(0)=1$ y: $$\frac{f(x)}{1-x}=\sum_{j=0}^{+\infty}\left(\sum_{k\leq j}T(k)\right)x_j=\sum_{j=0}^{+\infty}(2T(j)-1)\,x^j = 2f(x)-\frac{1}{1-x},$$ por lo tanto: $$f(x)=\frac{1}{1-2x}=\sum_{j=0}^{+\infty}2^j\,x^j,$$ de la cual: $$T(j)=2^j$$ como se quería.

Answer 4

Tal vez pueda demostrar que $2^n$ satisface la misma relación de recurrencia y condición inicial, supongo que utilizando el hecho de que $$ \frac{r^n - 1}{r-1} = r^{n-1} + r^{n-2} + \cdots + r + 1 $$

Answer 5

La segunda igualdad implica T[n+1] - T[n] = T[n] por lo que T[n+1] = 2T[n]. Busca soluciones de la forma T[n] = c q^n. La sustitución da como resultado q = 2. La condición inicial T[0] = 1 da como resultado c = 1.