2
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
gammatester
  • 18,827
Fran Navarro
  • 23
  • 4
  • So this defines a function ${\sf mul}\colon \mathbb N^2 \to \mathbb N$ by recursion. What to prove? – martini Jun 11 '14 at 07:58
  • So just do induction on $n$. The base case follows from $a\cdot 0 = 0$. For the step use the recursion. Where are you stuck? – martini Jun 11 '14 at 08:02
  • I'm clear with possibles bases cases, mul(a,0) = 0, mul(a,1) = mul(2a,0)+a = a, mul(a, 2) = mul(2a,1) = mul(4a,0)+2a = 0+2a... But i don't know that to use for induction step. – Fran Navarro Jun 11 '14 at 08:07

1 Answers1

0

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

martini
  • 84,101