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?
Your question can be interpreted as asking about the number of compositions of the positive integer $n$, and this is indeed $2^{n-1}$.
In order to think of the answer as $2^{n-1}$, we need to assume that there is a marked left end of the rod, and a marked right end, and we are cutting (say) from left to right. So for example we need to think of the cutting $1+2+3+1$ as different from the cutting $1+3+2+1$, or $1+1+2+3$. If order does not matter, we are dealing with the partitions of $n$, which are very much harder to count.
Here is a quick proof of the $2^{n-1}$ result. Suppose that the rod is a ruler, and has a mark every inch. If the rod is $n$ inches long, there are $n-1$ marks. For a cutting pattern, at any of the marks we stop and write Y (we will cut there) or N (we won't cut there). There are $2^{n-1}$ strings of length $n-1$ made up of the letters Y and/or N, so there are $2^{n-1}$ ways to cut.
Comment: One could do a formal induction instead, but that I think would take away from the clarity of the idea. If the induction exercise is important to you, try it. If you experience difficulty, I can fill in details.