(adsbygoogle = window.adsbygoogle || []).push({}); 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**