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.

Answer 3

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.