Proof of correctness of algorithms (induction)
how do I include the if else statement in the proof?


In this example, the if statement describes the basic case and the else statement describes the inductive step.

Induction on $z$.

Basis: $z = 0$. 

$$ \text{multiply}(y,z) = 0 = y \times 0. $$

Induction Hypothesis: Suppose that this algorithm is true when $0 &lt; z &lt; k$. Note that we use strong induction (wiki).

Inductive Step: $z = k$. 

\begin{align}
\forall c&gt;0 : \text{multiply}(y,z) &amp;= \text{multiply}(cy, \lfloor \frac{z}{c} \rfloor) + y \cdot (z \text{ mod } c) \\
&amp;= cy\cdot\left\lfloor \frac{z}
{c}\right\rfloor+y\cdot (z \text{ mod } c) \\
&amp;= yz.
\end{align}