I am reading an algorithm example.
The example is about Rod cutting
.
The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and sell the pieces. The goal is to find what is best. Sell a rod as a whole or in pieces (prices for rod lengths are assumed to be known).
In the presentation of the solution it says that a rod can be cut in $2^{n-1}$ ways.
I can see and verify that, for $n=1$, $n=2$, $n=3$, and $n=4$ but after that how can this be proved for any value of $n$?
By induction? I mean to verify it for $n=4$ I drew the various cuts. I didn't use some relation with $n=3$.
So although this problem seems to be proved by induction, it seems to me that it is proven some other way, but I am not sure on how.
How can we be sure that the rod can be cut in $2^{n-1}$ ways?