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.
Asked
Active
Viewed 975 times
2 Answers
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$.
Carsten S
- 8,726
-
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)$] – RE60K Mar 02 '16 at 13:20
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}$$
RE60K
- 17,716