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

Question

Suppose that $T(0) = 1$ and define $T(n)$ as follows $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j) $$ Show that $T(n) = 2^n$.

If I substitute values, I can see that the sequence goes like $1, 2, 4, 8, \dotsc$, that is that they are powers of $2$.

But how do I mathematically prove it? Any hints should be good too.

Answer 1

We have $$T(n+1) = 1+\sum_{k=1}^n T(k) = \left(1 + \sum_{k=1}^{n-1} T(k) \right) + T(n) = T(n) + T(n) = 2T(n)$$ Hence, we have $$T(n+1) = 2T(n) = 2^2 T(n-1) = 2^3 T(n-2) = \cdots = 2^n T(1) = 2^{n+1} T(0) = 2^{n+1}$$

Answer 2

HINT: Mathematical induction principle plus $1+2\dots+2^n=2^{n+1}-1$.

Answer 3

You can use strong induction on $n$. For the inductive step, you assume $T(m)=2^m$ for every $m\leq n$. For $T(n+1)$, from the definition, you have: $$ T(n+1)=1+\sum_{j=0}^{n}T(j)=1+(1+2^1+\ldots+2^n)=1+\frac{1-2^{n+1}}{1-2}=2^{n+1} $$