Proving number of calls made in cut-rod algorithm
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.