Hi Prunthaban is correct!!!
The proof goes like this
First take what he said as premises P(n) of a mathematical induction
"With n ones..
1. Use first n-1 ones to reach 2^(n-1) - 1
2. Set 2^(n-1) th one.
3. Reverse the first step.[So the premise states that we can make the first (n-1) ones 0. Assume this as a part of P(n) say premise X ]
4. Now use the n-1 ones to set the next 2^(n-1) - 1 ones!"
Now to prove that it can be extended to the next level(for (n+1) ones), we have to prove the following P(n+1) is true because
1. We can use ((n+1)-1) ones to reach the 2^((n+1)-1) [ This is directly the result of previous algorithm ]
2. We can set the 2^((n+1)-1)th one [ We have the (n+1)th one still left]
3. Reverse the first step
This can be proved as follows:-
We can set the (n-1) ones in the second 2^(n-1)-1 part as zero [ From P(n) Premise X]
We can now use the first n-1 ones to reach 2^(n-1) - 1
We can now unset the 2^(n-1) th one
We can now unset the first n-1 ones used to reach 2^(n-1) - 1 [From P(n) Premise X]
4. Now use the ((n+1)-1) ones to set the next 2^((n+1)-1) - 1 ones [This is same as step 1 and follows from the algorithm in P(n)]
Regards
Karthik
