Perhaps some induction together with some diving into binary: if is a string of 1's and 0's, representing the number in decimal notation, then This is pretty straightforward, so we can now assume the theorem is true for all binary strings of length n-1, and we shall prove for a string of length n (of course, for n=0,1 the claim is easily seen to be true). Let be the decimal representation of :
First case: , with a bin. string of length n-1. In this case, , and the ind. hypothesis tells us that the SX method gives us on .
Since , after getting from we get because of the last S, and from the last X we get .
Second case: ...I let you this case (as easy as the above one).