## Base Case

The base case $(z = 0)$ is true since it returns zero

if $z = 0$ then return(0)

## Assumptions

multiply(y,z) gives the correct answer where:

• z <= n
• c >= 2
• y >= 0

We will also assume the following. A brief proof will follow:

• $\left \lfloor z / c \right \rfloor c + (z\,\bmod\,c) = z$

## Proof

Where z = n+1, c >= 2, y >= 0

First we break the result of multiply into two parts:

A = $multiply(cy, \left \lfloor [n+1]/c \right \rfloor)$
B = $y([n+1]\,\bmod\,c)$

$multiply(y,z) = A + B$

Now, because c >= 2 we know that $\left \lfloor (n+1) / c \right \rfloor < (n+1)$.
Based on that, we know that the call to multiply in "A" returns the correct result.

$A = multiply(cy, \left \lfloor [n+1]/c \right \rfloor) = cy * \left \lfloor [n+1] / c \right \rfloor$

So now let's transform A into something more useful:

$A = cy * \left \lfloor [n+1] / c \right \rfloor = y * \left \lfloor z / c \right \rfloor c$
(Note: We transformed n+1 back into z for simplicity)

Based on our earlier assumption, we can transform this further:

$\left \lfloor z / c \right \rfloor c + (z \,\bmod\, c) = z$
$\left \lfloor z / c \right \rfloor c = z - (z \,\bmod\, c)$

$A = y * \left \lfloor z / c \right \rfloor c = y (z - z \,\bmod\, c) = yz - y(z \,\bmod\, c)$

And now we add B back into the mix:

$A + B = yz - y(z \,\bmod\, c) + y(z \,\bmod\, c) = yz$

## Subproof

Show that $\left \lfloor z/c \right \rfloor c + z\,\bmod\,c = z$ where c >= 2

We can prove this statement using a general example.

First, assume that $z\,\bmod\,c = a.$

Now, due to the definition of floor, we know the following:

$(z-a) / c = \left \lfloor z / c \right \rfloor$

This is because the remainder can't possibly be taken into account during a "floor" operation.

Based on that, we can restate the equation as:

$(z-a) / c * c + a = (z - a) + a = z$