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 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.
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 ==&gt; (n - 1)$ &amp; $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 ==&gt; 2^(n-1)$


Hence Proved.