\problemdata     
{induction-8}           
{induction, proofs, structural induction}              
{}              
{S01-PS2} 		
{S01 Karger}        	


\def\mult{\diamond}
\begin{problem} 
Consider the following ``mungiplication''
operation $\mult$, defined recursively on the natural numbers as follows:
\begin{enumerate}
\item for any $x$, $0 \mult x = 0$
\item for any $x$, $(n+1) \mult x = n\mult x + x$
\end{enumerate}
(You may note some similarity to the famous ``multiplication''
operation, but should {\bf not} use any facts about multiplication in
this problem.)  Do not assume anything about $\mult$ beyond what is
given above.
\begin{problemparts}

\ppart Prove the {\bf distributive law:} for any $n,a,b$, 
\[
n\mult (a+b) = n\mult a+n \mult b
\]
You may use all standard facts about addition.  But do not use
summation notation.

\solution{

\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[ 0 \mult (a + b) = 0 = 0 + 0 = (0 \mult a) + (0 \mult b) \]

{\em Inductive case, assuming $n \mult (a + b) = (n \mult a) + (n \mult b)$:}

\begin{eqnarray}
\label{mung-one}
(n + 1) \mult (a + b) & = & n \mult (a + b) + (a + b)\\
\label{mung-two}
& = & n \mult a + n \mult b + (a + b)\\
\label{mung-three}
& = & (n \mult a + a) + (n \mult b + b)\\
\label{mung-four}
& = & (n + 1) \mult a + (n + 1) \mult b
\end{eqnarray}

Equations~\ref{mung-one}~and~\ref{mung-four} are by the
``mungiplication'' definition. Equation~\ref{mung-two} is by the inductive
assumption. Equation~\ref{mung-three} is by addition's commutative and associative
properties.
\end{proof}
}

\ppart Prove the {\bf annihilation law:} for any $x$,
\[
x \mult 0 = 0
\]

\solution{

\begin{proof}
By induction on $x$:

{\em Base case, $x = 0$:}
\[ 0 \mult 0 = 0 \]
{\em Inductive case, assuming $x \mult 0 = 0$:}

By the ``mungiplication'' definition,
\( (x + 1) \mult 0 = x \mult 0 + 0\).
But \( x \mult 0 + 0 = x \mult 0 = 0 \) by the inductive assumption.
\end{proof}
}

\ppart Prove the {\bf commutative law:} for any $x, n$,
\[
x \mult n = n \mult x
\]

\solution{

\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[ x \mult 0 = 0 \mult x = 0 \]
{\em Inductive case, assuming $x \mult n = n \mult x$:}

\begin{eqnarray}
\label{mungcom-one}
x \mult (n + 1) & = & x \mult n + x \mult 1\\
\label{mungcom-onefive}
& = & x \mult n + x\\
\label{mungcom-two}
& = & n \mult x + x\\
\label{mungcom-three}
& = & (n + 1) \mult x
\end{eqnarray}

Equation~\ref{mungcom-one} is by the distributive property from part A.
Equation~\ref{mungcom-onefive} is by a subproof that we show next. 
Equation~\ref{mungcom-two} is by the inductive assumption.
Equation~\ref{mungcom-three} is by the ``mungiplication'' definition.
\end{proof}

\begin{proof}For any $x$, $x \mult 1 = x$ (by strong induction):

{\em Base cases, $x = 0,1$:}
\[ 0 \mult 1 = 0 \]
\[ 1 \mult 1 = 0 \mult 1 + 1 = 0 + 1 = 1 \]

{\em Inductive case, assuming $x \mult 1 = x$:}
\begin{eqnarray}
\label{lemma-one}
(x + 1) \mult 1 & = & x \mult 1 + 1\\
\label{lemma-two}
& = & x + 1
\end{eqnarray}

Equation~\ref{lemma-one} is by the ``mungiplication'' definition.
Equation~\ref{lemma-two} is by the inductive assumption.
\end{proof}
}

\ppart
{\em Optional:} Prove the {\bf associative law:} for any $a, b, n$,
\[
(a \mult n) \mult b = a \mult (n \mult b)
\]

\solution{
\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[
(a \mult 0) \mult b = 0 \mult b = 0 = a \mult 0 = a \mult (0 \mult b)
\]
This is by the identity law from part B and the definition of
``mungiplication''.

{\em Inductive case, assuming $(a \mult n) \mult b = a \mult (n \mult b)$:}

\begin{eqnarray}
\label{mungbon-1}
(a \mult (n + 1)) \mult b & = & ((n + 1) \mult a) \mult b\\
\label{mungbon-2}
& = & (n \mult a + a) \mult b\\
\label{mungbon-3}
& = & (n \mult a) \mult b + a \mult b\\
\label{mungbon-4}
& = & (a \mult n) \mult b + a \mult b\\
\label{mungbon-5}
& = & a \mult (n \mult b) + a \mult b\\
\label{mungbon-6}
& = & a \mult (n \mult b + b)\\
\label{mungbon-7}
& = & a \mult ((n + 1) \mult b)
\end{eqnarray}

Equations~\ref{mungbon-1}~and~\ref{mungbon-4} use the commutative property from
part C. Equations~\ref{mungbon-2}~and~\ref{mungbon-7} use the
``mungiplication'' definition.
Equation~\ref{mungbon-6} uses the distributive property from part A.
Equation~\ref{mungbon-3} uses both the commutative and
distributive properties. Equation~\ref{mungbon-5} uses the inductive assumption.

\end{proof}
}

\end{problemparts}

\end{problem}
