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 :

, with a bin. string of length n-1. In this case, , and the ind. hypothesis tells us that the SX method gives us on .First case:

Since , after getting from we get because of the last S, and from the last X we get .

...I let you this case (as easy as the above one).Second case:

Tonio