induction proof of recursive multiplication

Question

mul(a,0) = 0 
mul(a,n) =
    if a%2 then mul(2a,n/2)
    else mul(2a, (n-1)/2)+a


mul(a,n) = a*n

Answer 1

$\def\mul{{\sf mul}}$We do induction on $n$. For $n = 0$, we have $$ \mul(a,0) = 0 = a \cdot 0 $$ for any $a \in \mathbb N$.

Now let $n \ge 1$, suppose $\mul(b,k) = b \cdot k$ holds for any $b \in \mathbb N$ and any $k < n$. Let $a \in \mathbb N$ be arbitrary. Then if $n$ is even $$ \mul(a,n) = \mul(2a, n/2) $$ Now as $n/2 < n$, we have by induction hypothesis $$ \mul(a,n) = \mul(2a, n/2) = 2a \cdot \frac n2 =a \cdot n. $$ If $n$ is odd, we have again by recursion and induction hypothesis $$ \mul(a,n) = \mul\left(2a,\frac{n-1}2\right) + a = 2a \cdot \frac{n-1}2 + a = a(n-1) + a = a\cdot n. $$ This proves $\mul(a,n) = an$.