This question already has an answer here:

I was reading dynamic programming chapter from famous book Introduction To Algorithm

In rod cutting problem it gives simple algorithm as follows:

       if (n == 0)
          return 0
       q = -∞
       for (i=1 to n)
          q = max(q,p[i]+cutRod(p,n-i))
       return q

It then says:

T(n) be the total number of calls made to cutRod() when called with its second parameter equal to n. T(n) equals the number of nodes in a subtree whose root is labeled n in the recursion tree. The count includes the initial call at its root. Thus,

T(0) = 1 and

T(n) = ${\sum\limits_{j=0}^{n-1} T(j)}$

Exercise at the end of this chapters asks to prove from above two that in fact

T(n) = 2$^n$

How can we go about proving this?


marked as duplicate by FrankW, Rick Decker, David Richerby, D.W., Wandering Logic Sep 6 '14 at 3:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Just prove it by induction on $n$, since you're given the closed form for $T(n)$. $\endgroup$ – David Richerby Sep 4 '14 at 16:38
  • $\begingroup$ Please don't just copy a exercise problem here and ask us to solve it for you. We expect you to make a serious effort before asking, and to show us what you've tried in the question, and to articulate a specific question about your attempt. $\endgroup$ – D.W. Sep 5 '14 at 5:56
  • $\begingroup$ You can see that it is 2^n by simply starting to expand it for n = 0, 1, 2 and 3 $\endgroup$ – Nils Jun 8 '18 at 9:18

You can easily prove this by induction.

Base Case T(0) = 2^0 = 1.

Say T(k) = 2^k. is true for some k.

Hence T(k+1) = T(k) + sum(Ti) {i = 0 to k-1}
             = T(k) + T(k)
             = 2*2^k = 2^(k+1)

Note: By looking at the code, it seems that if you use dynamic programming and memo-ize the T(i)'s from bottom-up, you can make this algorithm into a O(n^2) algorithm.


Not the answer you're looking for? Browse other questions tagged or ask your own question.