Originally Posted by

**Deadstar** Let $\displaystyle a \in \mathbb{Z}$, $\displaystyle r \in \mathbb{N}$. Write $\displaystyle r$ in binary as $\displaystyle r = b_kb_{k-1} \dots b_1b_0$, with all $\displaystyle b_i \in \{0, 1\}$.

From the binary string $\displaystyle b_kb_{k-1} \dots b_1b_0$ produce a string of $\displaystyle S's$ and $\displaystyle X's$ by replacing each 0 by $\displaystyle S$ and each 1 by $\displaystyle SX$.

Now, starting with $\displaystyle A = 1$ and working from left to right, interpret $\displaystyle S$ as $\displaystyle A \to A^2$ (i.e. replace $\displaystyle A$ by $\displaystyle A^2$), and $\displaystyle X$ as $\displaystyle A \to Aa$ (multiply $\displaystyle A$ by $\displaystyle a$).

Prove that the result of this algorithm is indeed $\displaystyle a^r$.

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...