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

Question

For the recurrence defined by

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

Apparently $T(n) = 2^n$ .. but I cannot see it. This recurrence pops up during analysis of the Rod Cutting Problem. I keep looking to find a viewpoint to look at this problem where the factors of 2 pop out ..

Answer 1

Setting $n=m+1,m$

$$T(m+1) = 1 +\sum_{i=0}^mT(i)$$

$$T(m) = 1 +\sum_{i=0}^{m-1}T(i)$$

On Subtraction,

$$T(m+1)-T(m)=T(m)\iff T(m+1)=?$$

Answer 2

We can go backwards by proving the identity:

$$1 + 2^0 + 2^1 + 2^2... 2^n = 2^{n+1}$$

We use strong induction: assume it is true that:

$$1+ 2^0 + 2^1 ... 2^{n-1} = 2^n$$ then it is clear that the original statement is simply:

$$(1 + 2^0 + 2^1 ... 2^{n-1}) + 2^n = 2*2^n = 2^{n+1}$$

Now see that:

$$1 + 2^0 = 1 + 1 = 2^1$$

Thus this we have shown this pattern always holds since from our most recently proven base case case we can use the middle statement to show it is true for any n.