7
$\begingroup$

I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together:

function multiply($n, $r) {
    if($n == 1)
	return $r;
    else if($r == 1)
	return $n;
    else
        return $r + multiply($n - 1, $r);
}

How do I prove my algorithm is correct?

A quick google search tells me I have to prove that it works for $n + 1$ and I have to prove that it terminates. Unfortunately I'm still incredibly new to this and haven't the faintest clue as to where to start for proving my algorithm correct, so I would really appreciate some help here. I think maybe I have to do some sort of proof by induction but as this is an algorithm, I wouldn't know where to start.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

You need to do a proof by induction on $n + r$. Let $P(m)$ be the statement "for any $n,r \geq 1$ satisfying $n+r = m$, $\mathrm{multiply}(n,r) = nr$. The proof by induction goes along the following lines.

Base case: $m=2$, so $n=r=1$. By inspection, $\mathrm{multiply}(1,1)=1$.

Induction step: suppose $P(m)$ is true for some $m \geq 2$, and let $n,r\geq 1$ satisfy $n+r = m+1$. If $n=1$ or $r=1$ then $\mathrm{multiply}(n,r)=nr$ by inspection. Otherwise, by $P(m)$, $\mathrm{multiply}(n-1,r)=(n-1)r$ (since $n-1+r = m$), so $\mathrm{multiply}(n,r) = r+\mathrm{multiply}(n-1,r) = r+(n-1)r = nr$.

By the principle of mathematical induction, $P(m)$ is true for all $m$, and so for any $n,r\geq 1$, $\mathrm{multiply}(n,r)=nr$.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Take special note of the $n+r=m$ trick he's using here; it's well worth remembering. The idea is that you've got some function with arguments $f(a_0,a_1,...,a_p)$, and the inductive step needs to hold regardless of what $a_i$ you might increment. But rather than proving the inductive step for each argument separately, you roll all of the arguments into one term ($m=\sum_{i=0}^pa_i$) and wrap that in a new function or relationship, $P(m)$. $\endgroup$
    – Nobbynob Littlun
    Sep 1, 2013 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.