Let , . Write in binary as , with all .

From the binary string produce a string of and by replacing each 0 by and each 1 by .

Now, starting with and working from left to right, interpret as (i.e. replace by ), and as (multiply by ).

Prove that the result of this algorithm is indeed .

Anyone wanna tackle this? It's a tutorial question I have but you don't need to use it ever in the course, just seems to be stuck in there for anyone interested. I have no idea where to even begin...