Prove that a rod of integral length be broken in \( 2^{n-1} \) different ways
Assumptions
- The rod to be broken into parts is of length \( n \)
- The parts this rod can be broken into can only be of integral lengths i.e \( x \in \mathbb{N} \)
If you do not want the answer, but just want a hint ... think of cuts and the places you can place these cuts to form parts
Now given a bar of length n, the number of cuts to get a maximum of \( n \) parts of unit length is atmost \( n-1 \) cuts
This step also determines the sequential locations of cuts.
The locations of these cuts cannot be placed elsewhere as otherwise we would not get unit integral parts
Now let's imagine a scenario as such:
given I want to cut the rod in exactly one place, where should I place the cut? (each choice of cut location is a different way of cutting the rod)
I have \( n-1 \) locations to choose from so the answer is \( n-1 \)
Given I want to cut the rod in exactly two places, where should I place these cuts?
You could be tempted to say \( ( n-1 )* ( n-2 ) \) but recognize this: the ordering of the location doesn't matter so the correct answer is \( \frac{(n-1) * (n-2)}{2} \) OR \( C^{n-1}_{2} \)
We add the results for cases all the way to (n-1) (We also throw in the zeroth case)
\( C^{n-1}_{0} + C^{n-1}_{1} + C^{n-1}_{3} + C^{n-1}_{4} + ... \)
Recognize the above as the sum of the binomial coefficients
Now what is this sum equal to?
Sum of binomial coefficients
From the binomial theorem
\( (x+y)^{n} = C^{n}_{0}x^{n}y^{0} + C^{n}_{1}x^{n-1}y^{1} + C^{n}_{2}x^{n-2}y^{2} + C^{n}_{3}x^{n-3}y^{3} + ... \)
replacing \( x \) with 1 and \( y \) with 1
\( (1+1)^{n} = C^{n}_{0}1^{n}1^{0} + C^{n}_{1}1^{n-1}*1^{1} + C^{n}_{2}1^{n-2}*1^{2} + C^{n}_{3}1^{n-3}*1^{3} + ... \)
\( 2^{n} = C^{n}_{0} + C^{n}_{1} + C^{n}_{2} + C^{n}_{3} + ... \)
Trumpets !!!!
\( C^{n-1}_{0} + C^{n-1}_{1} + C^{n-1}_{2} + C^{n-1}_{3} + C^{n-1}_{4} + ... = 2^{n-1}\)