Can this be solved by induction? (number of ways of cutting a rod into pieces) 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?
 A: 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.  
A: Thomas Andrews has given a direct proof in his comment.  To put it in terms of induction, a one inch rod can be cut in  $1=2^{1-1}$ way (not at all).  If a length $k$ rod can be cut in $2^{k-1}$ ways, a length $k+1$ rod can be cut either by cutting off the right inch and cut the remaining in $2^{k-1}$ ways or by not cutting off the right inch and cut the remaining in $2^{k-1}$ ways, totaling $2^{(k+1)-1}$ ways.
