Recursive definition of multiplication

Question

I have the following function: $$ \begin{cases} mul (a, 0) = 0&\mbox{if }n=0\\ mul (a, n) = mul (2a, \frac{n}{2})&\mbox{if }n\mbox{ is even}\\ mul (a, n) = mul (2a, \frac{n-1}{2}) + a&\mbox{if }n\mbox{ is odd}\\ \end{cases} $$ It is clear that the function equals: $a * n$. a simple multiplication, but as I can prove by induction. Thank you.

Answer 1

Hint/here's one case: Suppose that $\mathrm{mul}(a,k) = ak$ for all $k \leq n$. If $n$ is odd, then by hypothesis $\mathrm{mul}(a,n+1) = \mathrm{mul}(2a,\tfrac{n+1}{2}) = 2a \tfrac{n+1}{2} = a(n+1)$.