\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsthm}
\usepackage{natbib}
\usepackage{graphicx}
% COMMANDS
% Sets
\newcommand{\N}{{\bf N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\R}{\Re}
\newcommand{\Q}{\mathcal{P}}
\newtheorem*{thm}{Theorem}
%\newtheorem*{def}{Definition}
% Proof by induction
\newcommand{\basis}{\newline \noindent {\bf Basis:} }
\newcommand{\hypothesis}{\newline \noindent {\bf Induction hypothesis:} }
\newcommand{\induction}{\newline \noindent {\bf Induction:} }
\newcommand{\recursiveStep}{\newline \noindent {\bf Recursive step:} }
\title{Proof Examples}
\author{Peter Cappello \\ \tt{cappello@cs.ucsb.edu} }
\date{}
\begin{document}
\maketitle
\section*{Introduction}
A mathematical proof, no less than a poem, musical composition, or computer program, can be a thing of beauty.
Composing a mathematical proof is similar, in some respects, to the human artifacts mentioned above:
The first version is not the final version.
There are stylistic considerations, as one seeks precision, clarity, and elegance.
Achieving these attributes entails iteratively refining the proof, as one would an essay, poem, musical composition, or computer program.
Incremental improvements are at best inconvenient when the proof is rendered with a pencil and paper,
enough so that, to seek excellence, one must venture into a machine-readable medium.
Latex currently is the easiest and most popular tool for this purpose.
Its use eliminates the inhibition and inconvenience associated with erasing and rewriting,
and enables rapid production of multiple lines of mathematics that differ symbolically only in small ways.
These seemingly minor mechanical advantages are key to the accumulation of improvements needed
to turn a first draft into an elegant proof of publication quality.
In producing the proofs below, I hope to help you 1) learn by example what I like to see in the form of a proof,
and 2) explore personally issues of mathematical style.
If you think any of the proofs are incorrect or could be simpler, clearer, or improved in any other way, please email me.
On a separate page, the latex used to produce these proofs is provided as evidence that latex is a labor-saving device,
even for mathematical work as ephemeral as homework.
\subsection*{Style}
I encourage a mathematical style that I think is appropriate for a student taking a
{\em first} course where mathematical proofs are the coin of the realm:
As you mature mathematically, some elements can be abbreviated or omitted.
For now, err on the side of giving an explanations where none is needed.
Similarly, strive for a form that is clear to another first-year student.
Indeed, asking another student to read your proof is a good source of feedback.
One source of thoughts about mathematical writing style is a document by Goss~\cite{Goss}.
Another is by Gillman~\cite{Gillman}.
There also is a guide to the use of the Americam Mathematical Society (AMS)
Latex package~\cite{amsthm-guide}
and an AMS author-related FAQ~\cite{ams-author-faq}.
Below, I produce a few style notes, certainly not a comprehensive list.
Also, some of these notes run against the grain of convention.
Please use your own judgment.
\begin{enumerate}
\item
It generally is considered bad form to mix mathematical symbols with English words
(e.g., $\forall n \in N, n^2$ is greater than 0.)
I disagree.
Please use mathematical symbols as much as possible;
this results in fewer characters, enabling the eye to see more content at once.
I also disagree, and for the same reasons,
with the rule that numbers less than 10 should be written in English.
In my opinion, this is like saying, for the number 7,
``Why use a single universally understood symbol,
when we can use a sequence of five letters that only English speakers understand?"
\item
It often is helpful to give a concrete example before giving a fully general proof.
\item
A proof should be free of debris that obscures the forest for the trees.
Omit purely {\em routine} symbol manipulation (i.e., not requiring a trick).
What constitutes a ``trick" however depends on your audience:
Whether or not a proof is well written depends on the intended audience.
\item
A diagram or picture may convey properties better than a 1000 words.
Fig.~\ref{pythagoras} is a fine proof of the Pythagorean theorem.
\begin{figure}[hbt]
\centering
\includegraphics[scale=0.4]{pythagoras.png}
\caption{Proof of Pythagorean theorem.}
\label{pythagoras}
\end{figure}
\end{enumerate}
%\begin{figure}[h!]
%\centering
%\includegraphics[scale=1.7]{universe.jpg}
%\caption{The Universe}
%\label{threadsVsSync}
%\end{figure}
\section*{Mathematical Induction}
The following proofs are of exercises in Rosen~\cite{RosenText}, \S 5.1: Mathematical Induction.
\subsubsection*{Exercise 62}
Show that $n$ lines separate the plane into $(n^2 + n + 2) / 2$ regions, if no 2 of these lines are parallel and no 3 pass through a common point.
Let $r_n$ denote the number of regions in the partition of the plane by $n$ lines,
where no 2 of these lines are parallel and no 3 pass through a common point.
%\newtheorem*{thm}{Theorem}
\begin{thm}
$\forall n \in \N \ r_n = (n^2 + n + 2) / 2$.
\end{thm}
\begin{proof}
By induction on $n$, the number of lines.
\basis
$n = 0$: If the plane is partitioned by 0 lines, there is $1 = (0^2 + 0 + 2)/2$ region.
\hypothesis
$r_n = (n^2 + n + 2) / 2$.
\induction
Let there be $n + 1$ lines in the plane, where no lines are parallel and no 3 lines intersect at the same point.
Remove any line.
By the inductive hypothesis, the remaining $n$ lines partition the plane into $(n^2 + n + 2)/2$ regions.
Fig.~\ref{5.1.62}(A) illustrates a plane partitioned into 11 regions by 4 lines.
In part (B), adding a $5^{th}$ (red) line increases the number of regions by 5.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.4]{Figure-5-1-62.png}
\caption{(A) A plane partitioned into 11 regions by 4 lines. \newline
(B) A plane partitioned into 11 + 5 regions by adding a $5^{th}$ (red) line.}
\label{5.1.62}
\end{figure}
In general, when line $n + 1$ is placed so that it is not parallel to any of the other $n$ lines and it intersects each line $l$ at a point where no other lines intersect line $l$,
then $n$ such intersections are formed.
Order these intersection points from left to right (or bottom to top, if they are vertical).
The region to the left of (or below) the $1^{st}$ intersection point, is divided into 2 regions by line $n + 1$.
Similarly, when this line enters the region to the right (or top) of an intersection point, it subdivides this region into 2 regions.
Since there are $n$ intersection points, this increases the number of regions by $n$, totalling $n + 1$ additional regions:
\begin{eqnarray}
r_{n + 1} & = & r_n + n + 1 \\
& = & \frac{n^2 + n + 2}{2} + n + 1 \\
& = & \frac{(n + 1)^2 + (n + 1) + 2}{2}
\end{eqnarray}
Above, the inductive hypothesis is used to go from Eqn. (1) to (2).
\end{proof}
\section*{Structural Induction}
The following proofs are of exercises in Rosen~\cite{RosenText}, \S 5.3: Recursive Definitions \& Structural Induction.
\subsubsection*{Exercise 44}
The set of {\em full binary trees} is defined recursively:
\begin{description}
\item[Basis step:]
The tree consisting of a single vertex is a full binary tree.
\item[Recursive step:]
If $T_1$ and $T_2$ are disjoint full binary trees, there is a full binary tree, denoted by $T_1 \cdot T_2$,
consisting of a root $r$ together with edges connecting $r$ to each of the roots of the left subtree $T_1$ and the right subtree $T_2$.
\end{description}
Use structural induction to show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T)$, the number of internal vertices of $T$.
\begin{thm}
If $T$ is a full binary tree, $l(T) = i(T) + 1$.
\end{thm}
\begin{proof}
By structural induction.
\basis
The full binary tree consisting of a single vertex, denoted $\bullet$, clearly has 1 leaf and 0 internal vertices:
$l( \bullet ) = i( \bullet ) + 1$.
\recursiveStep
Assume for full binary trees $T_1$ and $T_2$ that
\begin{eqnarray}
l( T_1 ) & = & i( T_1 ) + 1 \\
l( T_2 ) & = & i( T_2 ) + 1.
\end{eqnarray}
\begin{figure}[h!]
\centering
\includegraphics[scale=0.6]{Figure-5-3-44.png}
\caption{An illustration of full binary tree of $T_1 \cdot T_2$.}
\label{5.3.44}
\end{figure}
For full binary tree $T_1 \cdot T_2$ (see Fig.~\ref{5.3.44}),
\begin{eqnarray}
i( T_1 \cdot T_2 ) & = & i( T_1 ) + i( T_2 ) + 1 \\
l( T_1 \cdot T_2 ) & = & l( T_1 ) + l( T_2 ) \\
& = & ( i( T_1 ) + 1 ) + ( i( T_2 ) + 1 ) \\
& = & i( T_1 \cdot T_2 ) + 1.
\end{eqnarray}
Eqns. (6) and (7) follow from the construction of $T_1 \cdot T_2$; (8) follows from the induction hypotheses; (9) follows from (6).
\end{proof}
\section*{Equivalence Relations}
The following proofs are of exercises in Rosen~\cite{RosenText}, \S 9.5: Equivalence Relations.
\subsubsection*{Exercise 54}
Suppose that $R_1$ and $R_2$ are equivalence relations on a set $A$,
and that $P_1$ and $P_2$ are their respective partitions.
Show that $R_1 \subseteq R_2 \Leftrightarrow P_1$ refines $P_2$.
\begin{proof}
\begin{eqnarray}
R_1 \subseteq R_2 & \Leftrightarrow & \forall a \forall b \ ( a R_1 b \Rightarrow a R_2 b ) \\
& \Leftrightarrow & \forall a ( [a]_{R_1} \subseteq [a]_{R_2} ) \\
& \Leftrightarrow & P_1 \ \mathrm{ refines } \ P_2 .
\end{eqnarray}
The left side of eqn. (10) is equivalent to the right side, by the definition of subset.
The right side of (10) is equivalent to (11) by the definition of equivalence class.
Eqn. (11) is equivalent to (12) by the definition of partitions $P_1$ and $P_2$ in terms of their corresponding relations,
and the definition of refinement.
\end{proof}
\section*{Permutations \& Combinations}
The following proofs are of exercises in Rosen~\cite{RosenText}, \S 6.3: Permutations \& Combinations.
\subsubsection*{Exercise 54}
How many ways are there for a horse race with 4 horses to finish, if ties are possible? ({\em Note:} Any number of the 4 horses may tie.)
The following general solution was contributed by Benjamin Chang.
Let $H$ be a set of horses.
Define binary relation, $T$ on $H$, where $(horse_1 , \ horse_2 ) \in T$ when $horse_1$ ties $horse_2$.
Since $T$ is an equivalence relation, it partitions the set of horses.
A particular finish of a horse race corresponds to a particular ordered partition of $H$.
Let $\Q_n$ denote the number of ordered partitions of a set of $n$ elements.
For example, there are 3 ordered partitions of $\{ 1, 2 \}$:
\begin{enumerate}
\item $( \{ 1 \}, \{ 2 \} )$
\item $( \{ 2 \}, \{ 1 \} )$
\item $( \{ 1, 2 \} )$.
\end{enumerate}
In general,
\begin{enumerate}
\item $\Q_0 = 1$
\item $\Q_n = \sum_{k = 1}^n \left( \begin{array}{c} n \\ k \end{array} \right) \Q_{n - k}$.
\end{enumerate}
The recursive case partitions the set of ordered partitions of a set with $n$ elements into $n$ subsets
according to the number of elements in the {\em first} subset of the ordered partition.
%Using the product rule, the number of horse race finishes where $k$ horses tie for first place is the product of the number of ways that $k$ of the $n$ horses %can tie for first place,
%$\left( \begin{array}{c} n \\ k \end{array} \right)$, times
%the number of ways ways for the $n - k$ remaining horses to finish the race, $\Q_{n - k}$:
For each $k \in \{ 1, 2, \cdots, n \}$, there are $\left( \begin{array}{c} n \\ k \end{array} \right)$ ways to select the $k$-set comprising the first part of the partition and $\Q_{n - k}$ ways to complete the ordered partition of a set with $n$ elements.
\begin{eqnarray*}
\Q_1 & = & \left( \begin{array}{c} 1 \\ 1 \end{array} \right) \Q_{0} = 1 \\
\Q_2 & = & \left( \begin{array}{c} 2 \\ 1 \end{array} \right) \Q_{1} + \left( \begin{array}{c} 2 \\ 2 \end{array} \right) \Q_{0} = 3 \\
\Q_3 & = & \left( \begin{array}{c} 3 \\ 1 \end{array} \right) \Q_{2} + \left( \begin{array}{c} 3 \\ 2 \end{array} \right) \Q_{1} + \left( \begin{array}{c} 3 \\ 3 \end{array} \right) \Q_{0} = 13 \\
\Q_4 & = & \left( \begin{array}{c} 4 \\ 1 \end{array} \right) \Q_{3} + \left( \begin{array}{c} 4 \\ 2 \end{array} \right) \Q_{2} + \left( \begin{array}{c} 4 \\ 3 \end{array} \right) \Q_{1} + \left( \begin{array}{c} 4 \\ 4 \end{array} \right) \Q_{0} = 75 . \\
\end{eqnarray*}
\section*{Binomial Coefficients \& Identities}
The following proofs are of exercises in Rosen~\cite{RosenText}, \S 6.4: Binomial Coefficients \& Identities.
\subsubsection*{Exercise 32}
Prove the Binomial Theorem using mathematical induction.
\begin{proof}
\basis
$n = 0$: $1 = (x + y)^0 = \left( \begin{array}{c} 0 \\ 0 \end{array}\right) x^0 y^0$.
\hypothesis
$(x + y)^n = \sum_{j = 0}^n \left( \begin{array}{c} n \\ j \end{array}\right) x^{n - j} y^j$.
\induction
\begin{tiny}
\begin{eqnarray*}
(x + y)^{n + 1} & = & (x + y)(x + y)^n \\
& = & (x + y) \left[ \left( \begin{array}{c} n \\ 0 \end{array}\right) x^{n} y^0 + \left( \begin{array}{c} n \\ 1 \end{array}\right) x^{n - 1} y^1 + \cdots + \left( \begin{array}{c} n \\ j \end{array}\right) x^{n - j} y^j + \cdots + \left( \begin{array}{c} n \\ n \end{array}\right) x^0 y^n \right] \\
& = & \left( \begin{array}{c} n \\ 0 \end{array}\right) x^{n + 1} y^0 \ \ \ \ \ + \ \ \ \ \ \left( \begin{array}{c} n \\ 1 \end{array}\right) x^{n} y^1 + \ \ \cdots \ \ + \left( \begin{array}{c} n \\ j \end{array}\right) x^{n + 1 - j} y^j \ \ + \ \ \cdots + \ \ \ \ \left( \begin{array}{c} n \\ n \end{array}\right) x^1 y^n \\
& + & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( \begin{array}{c} n \\ 0 \end{array}\right) x^{n} y^1 + \cdots + \left( \begin{array}{c} n \\ j - 1 \end{array}\right) x^{n - (j - 1)} y^{j} + \cdots + \left( \begin{array}{c} n \\ n - 1 \end{array}\right) x^{1} y^{n} \ \ + \ \ \ \left( \begin{array}{c} n \\ n \end{array}\right) x^0 y^{n + 1} \\
& = & \left( \begin{array}{c} n + 1 \\ 0 \end{array}\right) x^{n + 1} y^0 + \left( \begin{array}{c} n + 1 \\ 1 \end{array}\right) x^n y^1 + \cdots + \left( \begin{array}{c} n + 1 \\ j \end{array}\right) x^{n + 1 - j} y^j + \cdots \ \ + \left( \begin{array}{c} n + 1 \\ n \end{array}\right) x^{1} y^{n} + \left( \begin{array}{c} n + 1 \\ n + 1 \end{array}\right) x^0 y^{n + 1}
\end{eqnarray*}
\end{tiny}
The $2^{nd}$ equation uses the induction hypothesis.
The sum that is broken over 2 lines is just $x(x + y)^n$ on one line plus $y(x + y)^n$ on the following line.
The last line makes use of the fact that $\left( \begin{array}{c} n + 1 \\ 0 \end{array}\right) = \left( \begin{array}{c} n \\ 0 \end{array}\right)$
and $\left( \begin{array}{c} n + 1 \\ n + 1 \end{array}\right) = \left( \begin{array}{c} n \\ n \end{array}\right)$,
and uses Pascal's identity to form the coefficient of each term as the sum of like terms in the preceding equation.
\end{proof}
\section*{Applications of Recurrence Relations}
The following proofs are of exercises in Rosen~\cite{RosenText}, \S 8.1: Applications of Recurrence Relations.
Let $\{ a_n \}$ be a sequence of real numbers.
The {\bf backward differences} of this sequence are defined recursively as follows. The {\bf $1^{st}$ difference} $\bigtriangledown a_n$ is
\[
\bigtriangledown a_n = a_n - a_{n - 1}.
\]
The ${\bf (k + 1)^{st}}$ difference $\bigtriangledown^{k + 1} a_n$ is
\[
\bigtriangledown^{k + 1} a_n = \bigtriangledown^k a_n - \bigtriangledown^k a_{n - 1}.
\]
\subsubsection*{Exercise 50}
Prove that $a_{n - k}$ is expressible in terms of $a_n, \bigtriangledown a_n, \bigtriangledown^2 a_n, \ldots, \bigtriangledown^k a_n$.
\begin{proof}
Proof by induction on $k$.
\basis $k = 1$: $a_{n - 1} = a_n - \bigtriangledown a_n$.
\hypothesis
$a_{n - k}$ is expressible in terms of $a_n, \bigtriangledown a_n, \bigtriangledown^2 a_n, \ldots, \bigtriangledown^k a_n$.
\induction We show that $a_{n - (k + 1)}$ is a function of $a_n, \bigtriangledown a_n, \bigtriangledown^2 a_n, \ldots, \bigtriangledown^{k + 1} a_n$.
\begin{eqnarray}
a_{n - (k + 1)} & = & a_{(n - 1) - k} \\
& = & f( a_{n - 1}, \bigtriangledown a_{n - 1}, \bigtriangledown^2 a_{n - 1}, \ldots, \bigtriangledown^k a_{n - 1} ) \\
& = & f( a_n - \bigtriangledown a_n, \bigtriangledown a_n - \bigtriangledown^2 a_n , \ldots, \bigtriangledown^k a_n - \bigtriangledown^{k + 1} a_n ) .
\end{eqnarray}
Eqn. 14 follows from 13 by the induction hypothesis; eqn. 15 follows from 14 by definition of backward differences.
\end{proof}
\newpage
\bibliographystyle{plain}
\bibliography{references}
\end{document}