Proving correctness of a recursive function of multiplication by induction.

Question

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.

Answer 1

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}$$

Answer 2

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$.