# Proving correctness of a recursive function of multiplication by induction.

Define multiplication of two numbers y and z as: $$m_c(y,z)=\begin{cases}0&z=0\\m_c\left(cy,\left\lfloor \frac zc\right\rfloor\right)+y(z\mod c)&z\neq 0\end{cases}\tag{\forall c\geq 2}$$ Now I need to show that this is correct using induction. It is obviously true for the case $z=0$. Otherwise: \begin{align}\forall z\neq 0,\;m_c(y,z)=&m_c\left(cy,\left\lfloor \frac zc\right\rfloor\right)+y(z\mod c)\\=&m_c\left(c^2y,\left\lfloor\frac 1c\left\lfloor \frac zc\right\rfloor\right\rfloor\right)+y(z\mod c)+cy\left(\left\lfloor\frac zc\right\rfloor\mod c\right)\\=&m_c\left(c^3y,\left\lfloor\frac 1c\left\lfloor\frac 1c\left\lfloor \frac zc\right\rfloor\right\rfloor\right\rfloor\right)+y(z\mod c)+cy\left(\left\lfloor\frac zc\right\rfloor\mod c\right)+\\&c^2y\left(\left\lfloor\frac 1c\left\lfloor\frac zc\right\rfloor\right\rfloor\mod c\right)\\=&\ldots\\=&m_c\left(c^ny,\underbrace{\left\lfloor\frac 1c\left\lfloor\frac 1c\left\lfloor\frac 1c\ldots\left\lfloor\frac zc\right\rfloor\ldots\right\rfloor\right\rfloor\right\rfloor}_{\text{n times c}}\right)\\&+\sum_{r=0}^{n-1} c^ry\left(\underbrace{\left\lfloor\frac 1c\left\lfloor\frac 1c\left\lfloor\frac 1c\ldots\left\lfloor\frac zc\right\rfloor\ldots\right\rfloor\right\rfloor\right\rfloor}_{\text{n-1 times c}}\mod c\right)\end{align} Now for induction, where do I start? From n=1 , then k then k+1. Or something else? A hint is enough.

You should do induction on $z$, so that you can assume in the inductive step that $m_c\left(cy,\left\lfloor \frac zc\right\rfloor\right)=cy\cdot\left\lfloor \frac zc\right\rfloor$.
• Assuming $m_c\left(cy,\left\lfloor \frac zc\right\rfloor\right)=cy\cdot\left\lfloor \frac zc\right\rfloor$, then do we prove for $m_c\left(cy,\left\lfloor \frac zc\right\rfloor+1\right)$? [$=m_c(c^2y,\left\lfloor\frac{\left\lfloor \frac zc\right\rfloor+1}c\right\rfloor)+y(\left\lfloor\frac zc\right\rfloor+1\mod c)$] Mar 2 '16 at 13:20
Base Case: If $z=0$ then it is true.
Assumption: true for $z\le n,c\ge 2,y\ge 0$ Induction: \begin{align}m(y,n+1)&=m\left(cy,\left\lfloor\frac {n+1}c\right\rfloor\right)+y((n+1)\mod c)\\ &=cy.\left\lfloor\frac {n+1}c\right\rfloor+y((n+1)\mod c)\tag{\left\lfloor\frac{n+1}c\right\rfloor<n+1\forall c\ge 2} \\&=y\left(c\left\lfloor\frac{n+1}c\right\rfloor+(n+1\mod c)\right) \\&=y(n+1)\end{align}