\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\medskip {\bf Solution:}\\ #1\medskip}
\newcommand{\depth}{\mbox{depth}}
\newcommand{\height}{\mbox{height}}
\newcommand{\lcm}{\mbox{lcm}}

\begin{document}

\tutn{5}{9/24/99}{September 24, 1999}

\begin{problems}


\problem \textbf{Recursively Defined Sequences}

% Variant of problem on practice quiz Fall98.

Consider an infinite sequence of rational numbers $a_0, a_1, a_2, \dots$
with the following properties:

\begin{enumerate}
\item $a_0 = 65$, and $a_1 = 26$,
\item for all $n > 2$, either
   \begin{enumerate}
    \item $a_n$ is the sum of two numbers earlier in the sequence, or
    \item $a_n$ is obtained by dividing the product of any $k>0$ numbers
          earlier in the sequence by $13^{k-1}$.
   \end{enumerate}
\end{enumerate}
Use the well-ordering principle to prove that every element in the
sequence is an natural number divisible by $13$.

\solution{
\begin{proof}
Let $I$ be the set of $i \in \naturals$ such that $a_i$ is not a natural
number or $a_i$ is a natural number but not divisible by 13.  We want to
show that $I$ is empty.

Suppose for contradiction that $I \neq \emptyset$.  Then by the
Well-ordering Principle, there must be a least natural number $m \in I$.
Now by definition, either $a_m$ is not a natural number or $a_m$ is a
natural number which is not divisible by 13.

Clearly $m \neq 0,1$, since $a_0$ and $a_1$ are natural numbers
divisible by 13.  So there are two possibilities:

The first possibility is that $a_m$ is a sum of $a_i$ and $a_j$ for $i,j <
m$.  In this case, by minimality of $m$, both $a_i$ and $a_j$ are natural
numbers divisible by 13.  But then their sum $a_m$ is also a natural
number divisible by 13, a contradiction.

The other possibility is that $a_m$ is a product, divided by
$13^{k-1}$, of $k>0$ numbers $a_i$ with $i<m$.  But again by minimality of
$m$, all the $a_i$'s must be natural numbers divisible by 13.  That is,
$a_m$ is a product, divided by $13^{k-1}$, of $k$ natural numbers each of
which is divisible by 13.  Now the product must be a natural number
divisible by $13^k$, so dividing by $13^{k-1}$ to obtain $a_m$ will leave
a factor of 13 in $a_m$.  That means that $a_m$ is a natural number
divisible by 13 in this case also, again a contradiction.

Since assuming $I$ is not empty yields a contradiction in both cases, it
must be that $I$ is empty.
\end{proof}
}

\problem

\iffalse
\ppart Let $m,n$ be positive integers.  Prove that $\gcd(n,m) \cdot \lcm(n,m) = mn$.
\hint Use the Fundamental Theorem of Arithmetic.

\solution{Each $n>1$ can be written as a unique product of prime powers.
Let $m = \prod_{i=0}^k p^{\alpha_i}$ and $n = m = \prod_{i=0}^k
p^{\beta_i}$ where $p_i$'s are {\bf all} the primes occurring in the
factorization of either $m$ and $n$ in increasing order (note that some of
the $\alpha_i$'s and $\beta_i$'s are 0).  But $\gcd(m,n)= {p_1^{min{(
\alpha_1 ,\beta_1)} }} {p_2^{min{( \alpha_2 ,\beta_2)}}} \dots p_k^{min(
\alpha_k ,\beta_k)}$ (cf Rosen, page 119, Example 13).  Similarily, in
Rosen, page 120, it was shown that $\lcm(m,n)= {p_1^{max{( \alpha_1
,\beta_1)} }} {p_2^{max{( \alpha_2 ,\beta_2)}}} \ldots {p_k^{max{(
\alpha_k ,\beta_k)} }}$.

Now, since $\alpha + \beta = \max(\alpha, \beta) + \min(\alpha,\beta)$, it
follows that $mn=\gcd(m,n)\lcm(m,n)$.}
\fi

Suppose $m,n,k \in \integers$, $i,j \in \naturals$, and $m>1$.
Prove that
\[
((n^j \equiv 1 \pmod m) \wedge (n^k \equiv 1 \pmod m))
 \implies n^{gcd(j,k)} \equiv 1 \pmod m.
\]
\hint $\gcd(j,k)=xj+yk$ for some $x,y \in \integers$.

\solution{
Let $\gcd(j,k)=xj+yk$ for some $x,y \in \integers$. Then,
\[
n^{\gcd(j,k)}  =  n^{xj+yk}
\]
At this point we would like to say
\[
n^{xj+yk}  =  n^{xj} n^{yk} \pmod m,
\]
but $xj$ or $yk$ may be negative, and in general, $n$ to a negative power
modulo $m$ may not be defined.  It is only defined if $n$ has an inverse
modulo $m$, denoted $n^{-1} \bmod m$, which allows us to interpret $n^{-p}
\bmod m$ as $(n^{-1})^p \bmod m$.  But in this problem, $n$ clearly does
have an inverse, namely $n^{j-1}$, which does justify this last equation,
turning the rest of the proof into a straightforward calculation.

Alternatively, there is a simple algebraic argument which does not involve
negative exponents.  Namely, note that
\[
n^{\abs{x}j} \equiv (n^{j})^{\abs{x}} \equiv 1^{\abs{x}} \equiv 1 \pmod m,
\]
and similarly 
\[
n^{\abs{y}j} \equiv 1 \pmod m.
\]
Therefore,
\begin{eqnarray*}
n^{xj+yk} & \equiv & n^{xj+yk} \cdot 1 \cdot 1 \pmod m\\
 & \equiv & n^{xj+yk} \cdot n^{\abs{x}j} \cdot n^{\abs{y}k} \pmod m\\
 & \equiv & (n^j)^{x+\abs{x}} \cdot (n^k)^{y+\abs{y}} \pmod m\\
 & \equiv & 1^{x+\abs{x}} \cdot 1^{y+\abs{y}} \pmod m\\
 & \equiv & 1 \pmod m.
\end{eqnarray*}
Notice that the third equivalence above is ok because both ${x+\abs{x}}$ and
${y+\abs{y}}$ will surely be nonnegative.
}

\iffalse
\ppart Let $n,m$ be natural numbers with $m>2$.  Suppose there are
$m - 1$ distinct powers of $n$ modulo $m$.  Prove that $m$ is prime.
\hint Every positive number $<m$ must occur in the sequence
$n^1,n^2,\dots,n^{m-1}$.

\solution{If $n^j \equiv n^k (\bmod m)$ for some $0<j<k$, then there would
be at most $k-1$ distinct powers modulo $m$, so since there are $m-1$ such
powers, the hint must hold.

In particular, $n^k \equiv 1 (\bmod m)$ must hold for some $k>0$.  Hence
$n$ and all its powers have inverses modulo $m$, which means that $\gcd$
of $m$ and any positive integer $<m$ is 1, which means that none of the
numbers $>1$ and $<m$ divide $m$.  So $m$ is prime by definition.
}

\eparts
\fi

\problem A \emph{complete binary tree of height $h \in \naturals$} and its
\emph{nodes} are defined inductively as follows:
\begin{itemize}

\item A complete binary tree of height 0 consists of an object which is
called its \emph{root} (see Fig. 1).  The root is the only node of the
tree of height 0.

\item A complete binary tree, $T$, of height $h+1$ consists of two
complete binary trees of height $h$, one of which is called the \emph{left
subtree} of $T$, and the other is called the \emph{right subtree}, along
with an object called the \emph{root} of $T$; the root must be different
from the nodes of the left and right subtrees of $T$ (see Figs. 2 and 3).
The \emph{nodes} of $T$ are its root and the nodes of its left and right
subtrees.
\end{itemize}

For example, a complete binary tree of height 3 is shown in Fig. 4.

\bparts

\ppart How many nodes are there in a complete binary tree of height $h$?
Prove it.

\solution{$1 + 2 + 4 + \dots + 2^h = 2^{h+1} - 1$ nodes.  We can prove
this by induction

base case $h=0$: the complete binary tree of height 0 has
$1=2-1=2^{h+1}-1$ nodes.

induction case: The number, $n_T$, of nodes in a complete binary tree of height
$h+1$ is $1+n_L+ n_R$ where its left subtree has $n_L$ nodes and it right
$n_r$.  By induction $n_L=n_R=2^{h+1}-1$, so $n_T=1+ 2(2^{h+1} -1)=1+
2^{h+2} -2 = 2^{(h+1)+1}-1$, as required.
}

\eparts

Looking at the Fig. 4, the \emph{depth} of a node in the tree is the
number of edges on the path from the root down to the node.  We can give a
precise recursive definition of the depth of a node in a tree, $T$, as follows:
\begin{itemize}
\item The depth in $T$ of the root of $T$ is 0.
\item The depth in $T$ of a node of $T$ which is in the left subtree, $L$,
of $T$ is one plus its depth in $L$.
\item The depth in $T$ of a node of $T$ which is in the right subtree, $R$,
of $T$ is one plus its depth in $R$.
\end{itemize}
For example, in Fig. 3, $\depth(r)=0$, and $\depth(l)=h$.

The \emph{height} of a node in $T$ is the number of edges on a path from
the node down to a leaf (the paths to each leaf will have the same
length).

\bparts

\ppart Give an inductive definition of the \emph{height} of a node in a
complete binary tree $T$.

\solution{\begin{itemize}
\item The height of the root of $T$ is the height of $T$.
\item The height of a node of $T$ which is in the left subtree, $L$,
of $T$ is the same as its height in $L$.
\item The height in $T$ of a node of $T$ which is in the right subtree, $R$,
of $T$ is the same as its height in $R$.
\end{itemize}
}

\ppart Prove by induction that the sum of the heights of all the
nodes in a complete binary tree of height $h$ is $2^{h+1} -h -2$.

\solution{The induction hypothesis $P(h)$ is the same as the statement to be proved.

Base case $h=0$.  $P(0)$ holds because the sum of the heights of the
single node of the tree is $0=2^{h+1} -h -2$.

Inductive step: Note that the height of any node of a complete binary tree
$T$ is the same in the subtrees of $T$, and the subsubtrees of the subtrees
of $T$, \dots, in which the node appears.  (This remark itself could be
prove by a trivial induction.)

So, the sum, $s$, of the heights in a complete binary tree $T$ of height
$h+1$ is the sum of the heights of the nodes in $L$ and the nodes in $R$
and the height of the root.  By induction hypothesis $P(h)$, the sum of the
heights in $L$ is $2^{h+1} -h -2$ and the same for $R$.  So $s =2(2^{h+1}
-h -2) + h + 1= 2^{h+2} -2h-4+{h+1} =2^{h+2} -(h+1) -2$, which proves
$P(h+1)$. \qed}

\ppart Prove by induction that the height of a node, $N$, in a complete binary
tree $T$ of height $h$ is $h - \depth(N)$.

\solution{The induction hypothesis
$P(h) ::= \forall T \forall N(\height(N) = h -\depth(N))$.
\begin{proof}
Base case $h=0$: The only node is the root $r$ and $\height(r) = 0 = h - 0
= h - \depth(r)$, proving $P(0)$.

Induction step: Suppose $T$ is of height $h+1$.  If $N$ is the root, then
$\height(N) = h+1$ and $\depth(N) = 0$ by definition, so $\height(N) = h+1
- 0 = (h+1) -\depth(N)$ as required.  Otherwise $N$ is a node of a
subtree, say of the left subtree, $L$.  We know $\height(N)$ is the same
in $T$ or in $L$.  But $\depth_T(N) = 1+ \depth_L(N)$ by definition of
depth.  Now by $P(h)$, we have $\height(N) = h - \depth_L(N) = (h + 1) -
(1 + \depth_L(N)) = (h+1) - \depth_T(N)$, proving $P(h+1)$.
\end{proof}
}


\iffalse

\ppart Let $T$ be a complete binary tree of height $h$.  Prove by
induction that the sum of the depths of all the nodes in $T$ is $2
+h2^{h+1} -2^{h+1}$.

\solution{The induction hypothesis $P(h)$ is the same as statement to be
proved.

Base case $h=0$.  The depth of the sole node is $0 = 2 - 0 -2 = 2
+h2^{h+1} -2^{h+1}$, proving $P(0)$.

Inductive Step: Let $T$ be a complete binary tree of height $h+1$.  All
nodes in $R$ and $L$ are now one level deeper.  The root adds nothing as
it is at depth 0.  So, the sum, $s_T$, of the depths of node in $T$ is the
sum of $s_L$ plus the number of nodes in $L$, and $s_R$ plus the number of
nodes in $R$.  Namely $s_T = 2((2 +h2^{h+1} -2^{h+1}) + 2^{h+1}-1) =
2(h2^{h+1}+1)=h2^{h+2} + 2 =
2+ (h+1)2^{h+2} -2^{h+2}$.  \qed}
\fi

\eparts

\begin{figure}[htbp]
\include{figs/fig1}
  \begin{center} \leavevmode 
    \caption{Complete binary tree of height 0} \end{center}
\end{figure}
\begin{figure}[htbp]
\include{figs/fig2}
  \begin{center} \leavevmode 
    \caption{Complete binary tree of height 1} \end{center}
\end{figure}
\begin{figure}[htbp]
\include{figs/fig3}
  \begin{center} \leavevmode 
    \caption{Depth and height of root and leaf nodes} \end{center}
\end{figure}
\begin{figure}[htbp]
\include{figs/fig4}
  \begin{center} \leavevmode 
    \caption{Complete binary tree of height 3} \label{fig:family} \end{center}
\end{figure}

\end{problems}

\end{document}
