Rod cutting: requesting a proof for $2^{n-1}$ possible ways 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?
 A: 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.
A: 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.
A: This can be proved using Binomial theorem $(1 + x)^n$.
$(1 + x)^n = nC_0*(x^0) + nC_1*(x^1) + nC_2*(x^2) + .... + nC_{n-1}*(x^n-1) + nC_n*(x^n)$
Total number of Cuts can be made = $(n - 1)$
    So, $n ==> (n - 1)$ & $x = 1$


*

*0 Cut NO CUT - $(n-1)C0$

*1 Cut can be made in different ways - $(n-1)C1$

*2 Cut can be made in different ways - $(n-1)C2$
.....

*n-1 Cut can be made in different ways - $(n-1)Cn-1$
Hence, Total possible ways to cut $= (n-1)C_0 + (n-1)C_1 + (n-1)C_2 + ... + (n-1)C_{n-1}$
That will be equals to -> $(1 + 1)^n-1 ==> 2^(n-1)$
Hence Proved.
