# Proving number of calls made in cut-rod algorithm [duplicate]

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

In rod cutting problem it gives simple algorithm as follows:

    cutRod(p,n)
{
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?

• Just prove it by induction on $n$, since you're given the closed form for $T(n)$. – David Richerby Sep 4 '14 at 16:38
• 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. – D.W. Sep 5 '14 at 5:56
• You can see that it is 2^n by simply starting to expand it for n = 0, 1, 2 and 3 – Nils Jun 8 '18 at 9:18

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