Number of possible rod cuts of a long rod . Basically I am trying to understand the concept of dynamic programming via Rod Cutting example.  

How the  number of ways in which a rod of length $n$ units can be cut is ${2}^{n-1}$ and not $2^n$? 

Consider the smallest cut be of one unit and there can also be a case where there is no cut at all . 
 A: I take it you are only allowed to cut the rod into integer lengths. I don't know about dynamic programming, but if you mark all the places where you are allowed to cut the rod, there are $n-1$ of them, and at each of those $n-1$ places, either you cut, or you don't, making, all told, $2^{n-1}$ different ways to cut. 
A: We can do this in a dynamic programming way like this.
WAYS(n) = $1 + \sum_{i=0}^{n-1}$WAYS(i). (this is because we can either not cut the rod (hence 1 way) or cut it by $n-i$ length and hence $i$ length remains. Now this $i$ length can be cut in WAYS(i) number of ways. And this $n-i$ length cut can go from $1$ to $n$. So we sum WAYS(i) from $i=0$ to $i=n-1$.)
WAYS(n-1) = $1 + \sum_{i=0}^{n-2}$WAYS(i)..... Just by replacing n with (n-1)
Now we can subtract the second equation from first equation.
WAYS(n)-WAYS(n-1)=WAYS(n-1) $\implies$ WAYS(n)=2*WAYS(n-1)
This recurrence relation simply computes to WAYS(n)= $2^{n-1}$ with the given base condition of WAYS(1)=1.
I know this strays from the contents of this SE but since the question was put forward from a dynamic programming standpoint, I thought it was apt to show it via this method too
