# Finding solution of given recursive equation?

$T(n) = 1+ \sum_{j=0}^{n-1} T(j)$
I've proved $2^n$ be the solution of this equation using induction. But is there any other way to find the solution? I just proved not solved.

• What do you mean by complexity? There seems to be no complexity here, only a function defined by recursion. – Yuval Filmus May 23 '17 at 6:26

The trick in this case is to consider differences: $$T(n)-T(n-1) = \left(1 + \sum_{j=0}^{n-1} T(j)\right) - \left(1 + \sum_{j=0}^{n-2} T(j)\right) = T(n-1).$$ Hence $T(n) = 2T(n-1)$, and so $T(n) = 2^n T(0)$.