Need help proving a recursive function works

[SpiffyEh]

Homework Statement

Prove the correctness of the following recursive algorithm to multiply two
natural numbers, for all integer constants c ≥ 2.
function multiply(y, z)
comment Return the product yz.
1. if z = 0 then return(0) else
2. return(multiply(cy,[ z/c]) + y · (z mod c))

Homework Equations

The Attempt at a Solution

I know I have to use an inductive proof
Base case: z=0
the vaule returned by line 1 is 0 which is correct
Inductive Step:
Inductive Hypothesis: The algorithm works for z =n
Show: the algorithm works for z=n+1

I know I have to do both even and odd due to the mod in the function but I'm confused because I don't know what y is or c and I'm not sure where to go with it. Can someone please help me?

 

[vela]

You're told that c is an integer greater than or equal to 2 and that y is, like z, a natural number. I take it z/c is supposed to be an integer division, i.e. you throw away the fractional part. It looks like you need to use http://mathcircle.berkeley.edu/BMC4/Handouts/induct/node6.html since z/c isn't typically equal to z-1.

You might try expressing z as z=qc+r for some non-negative integers q and r where 0≤r≤c-1.

 

[SpiffyEh]

I'm lost, I've never heard of string induction so I'm not sure what to do there. I don't understand the z=qc+r either, the only way we've done insuctive proofs is the way i started in the problem

 

[vela]

With weak induction, you assume that p(k) is true and prove that p(k+1) is true. You make no assumptions about the validity of p(k-2), p(k-3), ... , p(1). With strong induction, you assume that p(k), p(k-1), ..., p(1) are all true for the induction step.

Look at a specific case where c=2 and say you wanted to show multiply(1,11) gives the right answer. You have [z/c]=5 and yc=2, so the function will give the correct answer if multiply(2,5) returns the right answer. If you were using weak induction, you wouldn't be able to assume multiply(2,5) returns the right answer; you'd only know that multiply(something,10) was correct because the assumption is it works for z-1=10. With strong induction, you're fine assuming the routine works all the way back to the base case z=0.

When you say z=qc+r, you're just dividing z by c. The quotient is q and the remainder is r. For instance, take z=11 and c=4. If you divide 11 by 4, you get a quotient of 2 and a remainder of 3, i.e. 11=2(4)+3. The reason for writing it this way is that [z/c]=q and (z mod c)=r.

 

[SpiffyEh]

Sorry for the late reply. I had a chance to go see the teacher for the course and this in the information she gave me.

You assumed the algorithm works for all z<=n and you want to prove that it works for n. We know that yn=(cyn)/c=(cy)(n/c). Can you put the division, n/c, in terms of the floor of n/c and n%c? If you can do that then you can show yn=cy*floor(n/c)+y(n mod c), which is what line 2 of the algorithm should return. Thus you have shown that the math works.

Then all you have to do is show that line 2 of the algorithm, multiply(cy,floor(z/c))+y(z mod c) really returns cy*floor(n/c)+y(n mod c). Does the recursive call return the correct value?

So, I have somewhat of a starting point but I'm still confused about what she said

 

[vela]

You assumed the algorithm works for all z<=n and you want to prove that it works for n.

This is just strong induction as opposed to weak induction.

To prove the routine works, you have to show two things: (1) the math it's based on works and (2) the implementation is correct.

We know that yn=(cyn)/c=(cy)(n/c). Can you put the division, n/c, in terms of the floor of n/c and n%c? If you can do that then you can show yn=cy*floor(n/c)+y(n mod c), which is what line 2 of the algorithm should return. Thus you have shown that the math works.

This might help with (1). It looked a bit terse, in my opinion, if you haven't seen it before.

http://en.wikipedia.org/wiki/Division_algorithm

In your proof, it may be enough to just assert that "By the division algorithm, we know we can write blah blah blah."

Then all you have to do is show that line 2 of the algorithm, multiply(cy,floor(z/c))+y(z mod c) really returns cy*floor(n/c)+y(n mod c). Does the recursive call return the correct value?

Here, you're proving that the implementation is correct. It's where the induction part of the proof comes in.