Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Need help proving a recursive function works

  1. Aug 31, 2010 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations



    3. 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?
     
    Last edited: Aug 31, 2010
  2. jcsd
  3. Aug 31, 2010 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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 [Broken] 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.
     
    Last edited by a moderator: May 4, 2017
  4. Aug 31, 2010 #3
    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
     
  5. Aug 31, 2010 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
     
    Last edited: Aug 31, 2010
  6. Sep 2, 2010 #5
    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
     
  7. Sep 2, 2010 #6

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
    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."
    Here, you're proving that the implementation is correct. It's where the induction part of the proof comes in.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook