# 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$

$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$.

-
Induction is a first principle... It forms part of the standard axiomatization of the integers. –  Shakespeare Aug 9 '14 at 20:42
Okay, but I would like to show this without the prior knowledge that T(n) = 2^n. –  user168880 Aug 9 '14 at 20:44
In such a case, you can compute the first few terms pretty easily, which suggests a pattern. There is nothing wrong with doing that, that is a large part of mathematics. –  Simon Rose Aug 9 '14 at 20:45

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$.

-

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.

-

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.

-

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$$

-

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.

-