4

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

zac
  • 247

2 Answers2

5

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)=?$$

lab bhattacharjee
  • 274,582
  • Ya, I literally just thought of looking at the difference of two successive terms, which makes it clear. Funny how a slight change in view can make a problem transparent! Thanks for your speedy reply! – zac Aug 31 '14 at 16:58
0

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.

Sidharth Ghoshal
  • 16,771