Rod cutting: requesting a proof for $2^{n-1}$ possible ways

Question

The rod cutting problem states that: Given a rod of length $n$ inches and a table of prices $P_i$ for $i=1,\dots,n$, determine the maximum revenue $R_n$.

In CLRS chapter 15 Rod cutting page 360:

We can cut up a rod of length $n$ in $2^{n-1}$ different ways

I can intuitively understand why this is so; basically we can construct a binary tree of height $\log N$. But can someone provide me a proof of why this is so?

Answer 1

A rod of length $n$ can be cut at any of the positions $1$ inch, $2$ inches, up to $n-1$ inches. Therefore for each way of cutting the rod, there is a corresponding sequence of $0$s and $1$s of length $n-1$, with a $1$ in the $i$th place meaning that the rod is cut at this position and a $0$ meaning that it is not cut.

Since there are $2^{n-1}$ such sequences, there must be $2^{n-1}$ ways of cutting the rod.

Answer 2

For Example:- n = 4
 --- --- --- --- 
|   |   |   |   |  --> Rod of length 4 inches
 --- --- --- ---       ^ is showing where we can make cuts
    ^   ^   ^     

Now, Above given ^ position either we make a cut or not i.e; 0 for not making a cut and 1 for making a cut. We get $ 2^3 $ binary combinations are as follows:

           ---     --- --- ---
1 0 0 --> |   |   |   |   |   |
           ---     --- --- ---
           --- ---     --- ---
0 1 0 --> |   |   |   |   |   |
           --- ---     --- ---
           --- --- ---     ---
1 0 0 --> |   |   |   |   |   |
           --- --- ---     ---
           ---     ---     --- ---
1 1 0 --> |   |   |   |   |   |   |
           ---     ---     --- ---
           ---     --- ---     ---
1 0 1 --> |   |   |   |   |   |   |
           ---     --- ---     ---
           --- ---     ---     ---
0 1 1 --> |   |   |   |   |   |   |
           --- ---     ---     ---
           ---     ---     ---     ---
1 1 1 --> |   |   |   |   |   |   |   |
           ---     ---     ---     ---
           --- --- --- ---
1 1 1 --> |   |   |   |   |
           --- --- --- ---

Hence, A Rod of length "n" inches can be cut into $ 2^{n-1} $ pieces.