How do I solve the following recurrence relation?
$$ T(n) = 1 + \sum_{j=0}^{n-1} T(j). $$
I thought of solving it by generating its recursion tree. I found that the height of the tree would be equal to $n$ but wasn't able to find the cost of each level.
Here are several ways to solve your recurrence relation.
Guessing
Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this guess, you can verify it by summing the appropriate geometric series: if $T(m) = 2^m$ for $m < n$ then
$$ T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-1} 2^m = 1 + (2^n-1) = 2^n. $$
Computing the first few values
Another approach which is very useful is to compute a few values of the sequence: $$ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... $$ If we're lucky, as in this case, we might spot a pattern. If not, it's always a good idea to consult the on-line encyclopedia of integer sequences. A quick search would reveal the sequence A000079.
Creative telescoping
In the method of creative telescoping, we try to find a combination of terms that results in major cancellation. In our case, we can try $T(n+1)-T(n)$:
$$ T(n+1)-T(n) = \sum_{m=0}^n T(m) - \sum_{m=0}^{n-1} T(m) = T(n), $$ and so $T(n+1) = 2T(n)$. Unrolling this rule, we deduce $T(n) = 2^n T(0) = 2^n$.
Back-substitution
Another way to look at the preceding trick is to try to "back-substitute" the recurrence inside itself:
$$ T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-2} T(m) + T(n-1) = 2T(n-1), $$
from which we can proceed as before.
Generating series
A very general method is that of generating series. Let $G(x) = \sum_{n=0}^\infty T(n) x^n$. Since $1/(1-x) = \sum_{n=0}^\infty x^i$, multiplying by $1/(1-x)$ is like computing "running sums": $$ \frac{G(x)}{1-x} = \sum_{n=0}^\infty \sum_{m=0}^n T(m) x^n = \sum_{n=0}^\infty (T(n+1)-1) x^n = \\ \frac{G(x)-T(0)}{x} - \sum_{n=0}^\infty x^n = \frac{G(x)-1}{x} - \frac{1}{1-x}. $$ From this it is not hard to deduce $$ G(x) = \frac{-1/x-1/(1-x)}{1/(1-x)-1/x} = \frac{-(1-x)-x}{x-(1-x)} = \frac{1}{1-2x} = \sum_{n=0}^\infty 2^nx^n, $$ and so $T(n) = 2^n$.
Recursion tree
It is also possible to deduce the value of $T(n)$ using a recursion tree. Each path in the recursion tree for $T(n)$ corresponds to a sequence of decreasing numbers $n_0 = n, \ldots, n_\ell$, where $n_\ell \geq 0$ (possibly $\ell = 0$); this is because all leaves are labeled by $1$. The set of possible decreasing sequences is in one-to-one correspondence with subsets of $\{n-1,\ldots,0\}$, because once we know which numbers appear, we also know their order. The number of subsets of $\{n-1,\ldots,0\}$ is exactly $2^n$.
