Rod cutting problem recurrence:

T(n)=1+∑i=1nT(n−i)=1+∑j=0n−1T(j)T(n)=1+∑i=1nT(n−i)=1+∑j=0n−1T(j)

T(0) = 0

Solution: T(n)=2^n