Prove that the sequence with $T(0)=1$ and $T(n) = 1 + \sum_{j=0}^{n-1}T(j)$ is given by $T(n)=2^n$

Question

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

Show that $T(n) = 2^n$.

I know how to prove this by induction, but I would like to know how to show this using first principles.

Edit: The way I want to solve this problem is manipulate $T(n)$ in such a way that it ends up as $2^n$.

Answer 1

Clearly, $$T(n+1)=1+T(n)+\sum_{j=0}^{n-1}T(j)=T(n)+T(n)=2T(n)$$ So, $(T(n))_n$ is a geometric progression with common ratio $2$ and starts at $1$. That is $T(n)=2^n$.

Answer 2

You could perhaps show that $2^n$ satisfies the same recurrence relation and initial condition, I suppose, by using the fact that $$ \frac{r^n - 1}{r-1} = r^{n-1} + r^{n-2} + \cdots + r + 1 $$

Answer 3

The ugliest piece in the definition $T_n = 1 + \sum\limits_{k=0}^{n-1} T_{k}$ is the sum. One should attempt to get rid of it first. We have $$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$$

The rest is obvious.

This is one common tactic to attack an problem. You identify the ugliest, hardest piece and attempt to get rid of it. If you can repeat this procedure and get rid of all the nasties, what should/could do next is usually obvious.

Answer 4

the second equality implies T[n+1] - T[n] = T[n] so T[n+1] = 2T[n]. Look for solutions of the form T[n] = c q^n. Substitution yields q = 2. The initial condition T[0] = 1 yields c = 1.

Answer 5

This is just the brute force method. It is obviously an overkill in this case, but I think it is worth to learn it. Put: $$ f(x)=\sum_{j=0}^{+\infty}T(j)\, x^j. $$ The recurrence relation then gives $f(0)=1$ and: $$\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},$$ hence: $$f(x)=\frac{1}{1-2x}=\sum_{j=0}^{+\infty}2^j\,x^j,$$ from which: $$T(j)=2^j$$ as wanted.