2

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.

Frank
  • 2,348
Jose
  • 83
  • 1
    You do not necessarily need induction to prove this. Here is a direct proof : if $n$ is even, $n = 2p$ ($p \in \mathbb{Z}$) then $\mathrm{mult}(2a,\frac{n}{2}) = 2a \times p = a \times 2p = a \times n = \mathrm{mult}(a,n)$. And if $n$ is odd, write $n = 2*p+1$ ($p \in \mathbb{Z}$). Then, $\mathrm{mult}(2a,\frac{n-1}{2})+a = (2a) \times p + a = a \times (2p+1) = a \times n = \mathrm{mult}(a,n)$. – pitchounet Sep 16 '14 at 12:12
  • It is possible, in fact giving values ​​is sufficient, it is clear but my question is how could a demonstration by induction applied to this problem. – Jose Sep 16 '14 at 12:17

1 Answers1

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

fuglede
  • 6,716