\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{2}{September 21, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Let $P(n)$ be \[``{\displaystyle \sum_{j=1}^n j^2} = n(n+1)(2n+1)/6.''\]\\
{\em BASIS STEP:} $P(1)$ is true since \[{\displaystyle \sum_{j=1}^1 j^2} = 1 = 1(1+1)(2\cdot 1 +1)/6\].\\
{\em INDUCTIVE STEP:} Assume that \[{\displaystyle \sum_{j=1}^n j^2} = n(n+1)(2n+1)/6\]. 
Then 
\begin{eqnarray*}
{\displaystyle \sum_{j=1}^{n+1} j^2} & = ({\displaystyle \sum_{j=1}^n j^2}) + (n+1)^2 \\
		       & = n(n+1)(2n+1)/6 + (n+1)^2 \\
		       & = (n+1)(2n^2 + n + 6n + 6)/6 \\
		       & = (n+1)((n+1)+1)(2(n+1)+1)/6.
\end{eqnarray*}
This shows that $P(n+1)$ is true. Hence $P(n)$ is true for all natural numbers $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Definition of multiplication:
\begin{itemize}
\item $0\times n = 0$
\item $m'\times n = (m\times n) + n$ 
\end{itemize}
We prove, by induction, that $m\times (n+p) = (m\times n) + (m\times p)$.
Let $S = \{m|(\forall n\forall p)m\times (n+p) = (m\times n) + (m\times p)\}$.
We prove $S=N$.
\begin{itemize}
\item $0 \in S$, since  $0\times (n+p) = (0\times n) + (0\times p) = 0+0=0$.
\item Suppose $m \in S$ so that  $m\times (n+p) = (m\times n) + (m\times p)$.
Then
\begin{eqnarray*}
 m'\times (n+p) & = m\times (n+p) + (n+p) & \mbox{defn of $\times$}\\
		& = m\times n + m\times p + n + p & \mbox{inductive hypothesis}\\
		& = (m\times n + n) + (m\times p + p) & \mbox{commutativity of $+$}\\
		& = m'\times n + m'\times p & \mbox{defn of $\times$.}
\end{eqnarray*}
\end{itemize}
Therefore $S=N$ by induction axiom.

OR

Definition of multiplication:
\begin{itemize}
\item $m\times 0 = 0$
\item $m\times n' = (m\times n) + m$ 
\end{itemize}
We prove, by induction, that $m\times (n+p) = (m\times n) + (m\times p)$.
Let $S = \{p|(\forall m\forall n)m\times (n+p) = (m\times n) + (m\times p)\}$.
We prove $S=N$.
\begin{itemize}
\item $0 \in S$, since  $m\times (n+0) = (m\times n) + (m\times 0) = m\times n $.
\item Suppose $p \in S$ so that  $m\times (n+p) = (m\times n) + (m\times p)$.
Then
\begin{eqnarray*}
 m\times (n+p') & = m\times ((n+p)') & \mbox{defn of $+$}\\
		& = m\times (n+p) + m & \mbox{defn of $\times$}\\
		& = (m\times n) + ((m\times p) + m) & \mbox{inductive hypothesis}\\
		& = (m\times n) + (m\times p') & \mbox{defn of $\times$.}
\end{eqnarray*}
\end{itemize}
Therefore $S=N$ by induction axiom.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Let $P(n)$ be ``a full binary tree on $n$ nodes has $(n+1)/2$
leaves.''\\ 
{\em BASIS STEP:} $P(1)$ is true since a full binary tree on $1$ node has 
$(1+1)/2 = 1$ leaf. \\
{\em INDUCTIVE STEP:} Assume $P(n)$ is true. Consider a full binary tree on $n+1$ nodes. Let there be $k$ nodes in its left subtree. Then $k \leq n-1$ and its right subtree has $n-k$ nodes. By the inductive hypothesis, its left subtree has $(k+1)/2$ leaves and its right subtree has $(n-k+1)/2$ leaves. Hence the tree has $(k+1)/2 +(n-k+1)/2 = (n+1)/2$ leaves. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all natural numbers $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\begin{lemma} In any sequence of $n$ zeroes and
ones that begins with a zero and ends with a one, there is a zero
immediately preceding a one somewhere in the sequence.
\end{lemma}
\begin{proof}
Move from the left end of the sequence to the right end. At some point we must move from a $0$ to a $1$ since we start at a $0$ and end with a $1$. Consider the first time we move from a $0$ to a $1$, at this point we have a $0$
immediately preceding a $1$. This completes the proof.
\end{proof}

OR

\begin{proof}
We prove it by induction on the position on the length of the sequence. Let $P(n)$ be ``if the sequence has length $n$ then the sequence has a $0$ immediately preceding a $1$.''\\ 
{\em BASIS STEP:}  $P(2)$ is true since a sequence that has a $0$ in position one and a $1$ in position two has a $0$
immediately preceding a $1$. \\
{\em INDUCTIVE STEP:} Assume $P(n)$ is true. Consider a sequence of length $n+1$. If it has a $1$ in position two, we are done. Otherwise it has a $0$ in position two, in which, case consider the subsequence starting from position two and going to position $n+1$. This subsequence satisfies the preconditions of the lemma and has length $n$, hence by the inductive hypothesis, it and therefore the original sequence, contains a $0$ immediately preceding a $1$. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all natural numbers $n$.\\ 
\end{proof}


Having proved the lemma we move onto the main problem.

Let $P(n)$ be ``every tournament with $n$ teams has a chain.''\\
{\em BASIS STEP:} $P(2)$ is true since a tournament with $2$ teams has a winner and a loser and hence a chain.\\
{\em INDUCTIVE STEP:} Assume $P(n)$ is true. Consider a tournament with $n+1$ teams. Now split the $n+1$ teams arbitrarily into one team, called team $n+1$, and the remaining $n$ teams. Note that the tournament contains a sub-tournament on these $n$ teams which, by the inductive hypothesis must contain a chain. Let the teams be numbered $1,2,\ldots,n$ according to their position in the chain. Now create a sequence of length $n$ of $0$s and $1$s by considering the games between the team numbered $n+1$ and the rest. Put a $1$ at position $i$ in the sequence if team  $n+1$ beat team $i$. Pad the sequence with a $0$ at the beginning and a $1$ at the end. By the above lemma there must be a position $j$ at which there is a $0$ immediately preceding a $1$. It is clear that inserting team $n+1$ in the chain at position $j$ generates a valid chain. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all natural numbers $n$.

No, it does not mean the first team in
the order always beat all the other teams. A simple counterexample can be got by considering a tournament with three teams $A,B$ and $C$ where $A$ beats $B$, $B$ beats $C$ and $C$ beats $A$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart The inductive step does not work for $n=0$ since $a^{n-1}$ is undefined.
\ppart The inductive hypothesis is invoked wrongly in the inductive step. $r$ and $s$ need not be squares, they could also be primes.
\ppart The theorem is plainly false since there are only a finite number of 
thirteen word descriptions (assuming, of course that the English language has a finite number of words, a not unreasonable assumption) but there are an infinite number of positive integers. The ambiguity comes because of the meaning of the word {\em description}. If by description we mean a fixed (and computable) correspondence (from the ordered collection of thirteen words to a positive integer) then the sentence ``the smallest number that cannot be described in less than fourteen
English words'' would either not {\em describe} a number or if it did then it would correspond to that number and would not carry its self-referential English meaning at the same time. 
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Let $P(n)$ be ``$F_{3n-1}$ is even.''\\
{\em BASIS STEP:} $P(1)$ is true since $F_{3\cdot 1 -1} = F_2 = 2$ is even.\\
{\em INDUCTIVE STEP:} Assume $P(n)$ is true. Then $F_{3(n+1)-1} = F_{3n+2} = F_{3n+1} + F_{3n}$, by definition. But $F_{3n+1} = F_{3n} + F_{3n-1}$. Hence $F_{3n+2} = 2F_{3n} +F_{3n-1}$. But $F_{3n-1}$ is even by the inductive hypothesis, and hence so is $F_{3n+2}$. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all natural numbers $n$. 

OR

Let $P(n)$ be ``$F_{3n-1}$ is even, $F_{3n-2}$ and $F_{3n-3}$ are odd.''\\
{\em BASIS STEP:} $P(1)$ is true since $F_{3\cdot 1 -1} = F_2 = 2$ is even; and $F_{3\cdot 1-2} = F_1 = 1$ and $F_{3\cdot 1 -3} = F_0 = 1$ are odd.\\
{\em INDUCTIVE STEP:} Assume $P(n)$ is true. Then $F_{3(n+1)-3} = F_{3n} = F_{3n-1} + F_{3n-2}$, by definition. But $F_{3n-1}$ is even and $F_{3n-2}$ odd, by the inductive hypothesis, and hence $F_{3n}$ is odd. Similarly, $F_{3(n+1)-2}$ and $F_{3(n+1)-1}$ can be seen to be odd and even, respectively. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all natural numbers $n$.

\end{problems}

\end{document}





