\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
% --------------------------------------------------------------
% This is all preamble stuff that you don't have to worry about.
% Head down to where it says "Start here"
% --------------------------------------------------------------
\documentclass[12pt,leqno,oneside]{book}
\usepackage{amsmath,amssymb,amsfonts} % Typical maths resource packages
\usepackage{graphics} % Packages to allow inclusion of graphics
\usepackage{color} % For creating coloured text and background
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{mathrsfs}
\usepackage[colorlinks = true, linkcolor = black, citecolor = black, final]{hyperref}
\usepackage{tikz}
\parindent 1cm
\parskip 0.2cm
\topmargin 0.2cm
\oddsidemargin 1cm
\evensidemargin 0.5cm
\textwidth 15cm
\textheight 21cm
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{exer}[theorem]{Exercise}
\newtheorem{refer}[theorem]{Reflection}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\newtheorem{caut}[theorem]{CAUTION}
\makeatletter
\def\blfootnote{\xdef\@thefnmark{}\@footnotetext}
\makeatother
\def\R{\mathbb{ R}}
\def\Z{\mathbb{ Z}}
\def\Q{\mathbb{ Q}}
\def\S{\mathbb{ S}}
\def\I{\mathbb{ I}}
\def\N{\mathbb{N}}
\def\ra{\Rightarrow}
\def\lra{\Leftrightarrow}
\def\ul{\underline}
\newcommand{\ds}{\displaystyle}
\newcommand{\comp}{\widetilde}
\newcommand{\scr}{\mathscr}
\newcommand{\dom}{\text{Dom}}
\newcommand{\ran}{\text{Ran}}
% Code for creating empty pages
% No headers on empty pages before new chapter
\makeatletter
\def\cleardoublepage{\clearpage\if@twoside \ifodd\c@page\else
\hbox{}
\thispagestyle{plain}
\newpage
\if@twocolumn\hbox{}\newpage\fi\fi\fi}
\makeatother \clearpage{\pagestyle{plain}\cleardoublepage}
\title{MATH 301 Portfolio}%replace X with the appropriate number
\author{Pythagorus} %replace with your name
\begin{document}
\maketitle
\frontmatter
\tableofcontents
\newpage
\mainmatter
\chapter{The Words Matter}
\begin{center}
{\small\em If you don't say it well, people won't know what you're talking about.}
\end{center}
\section{Wordplay}\label{s:word}
We begin with a definition.
\vskip10pt
\begin{defn}
The \emph{length} of a word is however many letters long it is. Given a word $W$, denote its length by $l(W)$.
\end{defn}
\begin{ex}
$l(\text{book})=4$ and $l(\text{trigonometry})=12$.$\quad\Box$
\end{ex}
We would next like to develop a measure of similarity between two words of equal length.
\begin{defn}
The \emph{difference} between two words of equal length is the number of letter positions in which the two words have different letters. Given two equal length words $W$ and $V$, denote their difference by $d(W,V)$.
\end{defn}
\begin{ex}
$d(\text{book},\text{look})=1$ because they have different letters in exactly one position (the first position on this example).
On the other hand, $d(\text{cat},\text{hog})=3$ because they have different letters in all three letter positions.$\quad\Box$
\end{ex}
\begin{defn}
A list of distinct words is called \emph{stable} if all the words on the list are the same length and the difference
between consecutive words is equal to 1.
\end{defn}
With these few definitions in hand, our ``theory of words" will now blossom. As you consider the following propositions, remember
that their content is not the real prize; you are unlikely to encounter any of these results in your mathematical lives beyond this course. The real prize is your own burgeoning awareness that theories are built on definitions and that deep and precise
understanding of the definitions is one of the key prerequisites for mathematical success.
Determine whether each proposition is true or false. Justify your conclusion thoroughly.
\begin{prop}
There exists a stable list of five length-4 words.
\end{prop}
\begin{prop}
Every stable list of length-2 words has fewer than 1000 words.
\end{prop}
\begin{prop}
If $W$ and $V$ are on the same stable list, then $d(W,V)<l(W)$.
\end{prop}
As we define new notions into an existing theory, the theory grows both in richness and complexity.
\begin{defn}
A list of distinct words is called \emph{tight} if all the words on the list are the same length and
$d(W,V)\leq 2$ for any two words $W$ and $V$ on the list.
\end{defn}
Determine whether each proposition is true or false. Justify your conclusion thoroughly.
\begin{prop}
There exists a fourth word $W$ beginning with an ``h" such that the list
\[
\{\ \text{\emph{sit}}, \text{\emph{hut}}, \text{\emph{sum}}, W\ \}
\]
is tight.
\end{prop}
\begin{prop}
If the list
\[
\{\ \text{\emph{sit}}, \text{\emph{hut}}, \text{\emph{sum}}, W\ \}
\]
is tight and $W$ begins neither with ``s" nor ``h", then the last letter of $W$ is a ``t".
\end{prop}
It is natural to wonder about the relationships, if any, between tight and stable lists.
\begin{prop}
There exist tight stable lists of length-3 words.
\end{prop}
\begin{prop}
All tight lists are stable.
\end{prop}
\begin{prop}
All stable lists are tight.
\end{prop}
\begin{refer}
How does a mathematical definition differ from the definitions you're used to learning in other disciplines?
\end{refer}
%\begin{prop}
%For each tight stable list of length-3 words, there is some letter position in which all the listed words have the same letter.
%\end{prop}, put this much later in the course.
\section{Formalizing the Lexicon}\label{s:lex}
In Section \ref{s:word} we began developing a miniature ``theory of words" based on a mere four definitions. The
definitions and resulting theory were completely contrived and are probably not known to many outside our
class.
There is, however, a widely agreed-upon language of mathematics. A high level of fluency in this language will be
invaluable to you as you progress into your upper-division coursework.
In this section we introduce important vocabulary and begin to develop the rules of grammar within the language
of mathematics.
\begin{defn}
A \emph{proposition} is a statement that is either true or false.
\end{defn}
\begin{ex}
The following are all propositions:
\begin{itemize}
\item Elvis lives.
\item The president had eggs for breakfast the morning of his tenth birthday.
\item All stable lists are tight.
\end{itemize}
\end{ex}
\begin{ex}\label{e:notprop}
Each of the following is not a proposition:
\begin{itemize}
\item Van Gogh was the best artist ever.
\item What time is it?
\item $x^2=4$.
\end{itemize}
\end{ex}
The body of mathematical knowledge is a vast collection of propositions. Most of these are combinations of simpler
propositions. There are three primary ways in which we combine propositions to form new propositions.
\begin{defn}[Conjunction]\label{d:con}
Let $P$ and $Q$ represent propositions. The \emph{conjunction} of $P$ and $Q$ is expressed symbolically
\[
P \wedge Q
\]
and is read ``$P$ and $Q$". The proposition $P \wedge Q$ is true precisely when the component propositions
$P$ and $Q$ are {\bf{both}} true.
\end{defn}
\begin{defn}[Disjunction]\label{d:dis}
Let $P$ and $Q$ represent propositions. The \emph{disjunction} of $P$ and $Q$ is expressed symbolically
\[
P \vee Q
\]
and is read ``$P$ or $Q$". The proposition $P \vee Q$ is true precisely when {\bf{at least one}} of the component propositions
$P$ and $Q$ is true.
\end{defn}
\begin{defn}[Negation]\label{d:neg}
Let $P$ represent a proposition. The \emph{negation} of $P$ is expressed symbolically
\[
\sim P
\]
and is read ``not $P$". The proposition $\sim P$ is true precisely when the component proposition
$P$ is {\bf{false}}.
\end{defn}
\begin{exer}
Consider the following propositions
\begin{itemize}
\item $P$: ``All stable lists of words are tight."
\item $Q$: ``Cal Poly is on semesters."
\item $R$: ````Elvis lives." is a proposition."
\end{itemize}
and determine whether each of the following compound propositions is true or false, thoroughly justifying your answers:
\begin{enumerate}[(i)]
\item $P \vee R$.
\item $\sim(Q \wedge R)$.
\item $(\sim Q \wedge P)\vee(\sim P \wedge R)$.
\end{enumerate}
\end{exer}
\begin{remark}
Note that the symbol $\sim P \wedge Q$ can have a different truth value than the symbol $\sim (P \wedge Q)$; one must take care
with parentheses when forming compound propositions.
\end{remark}
Mathematics is full of notation that can look impenetrable to the lay person, but is actually quite convenient to those in the know. In many
ways, this class is your initiation into the latter group. Consider, for instance, the following \emph{truth tables}:
\[
\begin{tabular}{| c c | c |} \hline
\(P\) & \(Q\) & \(P \wedge Q\) \\ \hline\hline
T & T & T \\
T & F & F \\
F & T & F \\
F & F & F \\ \hline
\end{tabular}
\qquad
\begin{tabular}{| c c | c |} \hline
\(P\) & \(Q\) & \(P \vee Q\) \\ \hline\hline
T & T & T \\
T & F & T \\
F & T & T \\
F & F & F \\ \hline
\end{tabular}
\qquad
\begin{tabular}{| c | c |} \hline
\(P\) & \(\sim P\) \\ \hline\hline
T & F \\
F & T \\ \hline
\end{tabular}
\]
These truth tables are designed to succinctly summarize definitions \ref{d:con}-\ref{d:neg}. To wit, the first truth table above merely indicates that the
conjunction $P \wedge Q$ is true only when both constituent propositions $P$ and $Q$ are true.
The second truth table above indicates that
the disjunction $P \vee Q$ is true as long as at least one of the constituent propositions $P$ and $Q$ is true.
The final truth table indicates that
the proposition $\sim P$ has the opposite truth value as the proposition $P$.
There is a second utility to truth tables beyond summarizing the definitions of conjunction, disjunction and negation. One can use
truth tables to recognize two different looking compound propositional forms as being logically equivalent. For instance, here is the truth table
indicating the truth value of the propositional form $\sim (P \wedge Q)$:
\[
\begin{tabular}{| c c c | c |} \hline
\(P\) & \(Q\) & \(P \wedge Q\) & \( \sim (P \wedge Q) \) \\ \hline\hline
T & T & T & F \\
T & F & F & T\\
F & T & F & T\\
F & F & F & T \\ \hline
\end{tabular}
\]
\begin{exer}
Construct a truth table for the propositional form $(\sim P) \vee (\sim Q)$. Is there any combination of truth values for the constituent propositions
$P$ and $Q$ that yields different truth values for the propositional forms $\sim (P \wedge Q)$ and $(\sim P) \vee (\sim Q)$?
\end{exer}
\begin{exer}
Create a definition for what it means for two propositional forms to be \emph{equivalent}.
\end{exer}
\begin{exer}
Conjecture a propositional form equivalent to $\sim (P \vee Q)$ and use truth tables to verify your conjecture.
\end{exer}
The preceding exercises indicate that the negation operation $\sim$ ``distributes" across parentheses in a regular and intuitive way. This is
an important part of writing useful and stylistic ``denials".
\begin{defn}
A \emph{denial} of a proposition $P$ is any proposition with the same truth value as $\sim P$.
\end{defn}
\begin{exer}
Write a denial of the proposition
\newline
\centerline{``Cal Poly is on semesters."}
\end{exer}
\begin{exer}
Write a denial of the proposition
\newline
\centerline{``The window is open and the pie is missing."}
\end{exer}
\begin{exer}
Write a denial of the proposition
\newline
\centerline{``The function $f(x)$ is unbounded or constant."}
\end{exer}
\section{Consider the Implications}\label{s:imp}
Most mathematical theorems are formulated as so-called ``if, then" statements. We begin this section by making a rigorous definition of ``if, then".
\begin{defn}[Conditional]\label{d:conditional}
Let $P$ and $Q$ represent propositions. The \emph{conditional sentence} ``If $P$, then $Q$" is expressed symbolically
\[
P \ra Q
\]
and has truth table
\[
\begin{tabular}{| c c | c |} \hline
\(P\) & \(Q\) & \(P \ra Q\) \\ \hline\hline
T & T & T \\
T & F & F \\
F & T & T \\
F & F & T \\ \hline
\end{tabular}
\]
\end{defn}
The last two rows of the truth table for $P \ra Q$ are sometimes an initial shock. We are agreeing in Definition \ref{d:conditional} that the
proposition ``If $P$, then $Q$" is true when the proposition $P$ is false, no matter whether the proposition $Q$ is itself true or false!?
An example may clarify our reasons for entering into this contract. Let's say I'm the coach of our basketball team and you all are the
players. Suppose I tell you
\vskip7pt
\centerline{
``If you win tonight, then I will give you the day off tomorrow."
}
\vskip7pt
\noindent What is the only circumstance in which you can rightly claim to have been lied to?
\begin{enumerate}
\item If you win and I give you the day off tomorrow, then I have kept my word (first row of truth table).
\item If you lose and I don't give you the next day off, then I have not broken my word (last row of the truth table).
\item If you lose and I \emph{do} give you the next day off, then I have granted you a break despite the loss but have not broken my word (third row of truth table).
\item The only way my ``if, then" can possibly end up false is for you to win and for me to not give you the next day off (second row of the truth table).
\end{enumerate}
\begin{exer}
Determine a propositional form involving some of $P$, $Q$, $\wedge$, $\vee$ and $\sim$ that is logically equivalent to $P\ra Q$ and justify
your assertion with truth tables.
\end{exer}
\begin{defn}
In the conditional sentence $P\ra Q$, the proposition $P$ is called the \emph{antecedent} and the proposition $Q$ is called the
\emph{consequent}.
\end{defn}
\begin{exer}
Write a true conditional sentence where the consequent is false.
\end{exer}
\begin{exer}
Write a true conditional sentence where the consequent is true.
\end{exer}
\begin{exer}
Write a true conditional sentence where the antecedent is false.
\end{exer}
\begin{exer}
Determine the truth value for each of the following conditional sentences.
\begin{enumerate}[(i)]
\item ``If Euclid was a Leo, then squares have four sides."
\item ``If $5<2$, then $10<7$."
\item ``If $\sin\left(\frac{\pi}{2}\right)=1$, then Betsy Ross was the first president of the United States."
\end{enumerate}
\end{exer}
There are two conditional sentences that are very closely related to the conditional sentence $A\ra B$.
\begin{defn}
The \emph{converse} of the conditional sentence $P\ra Q$ is the conditional sentence $Q\ra P$.
\end{defn}
\begin{defn}
The \emph{contrapositive} of the conditional sentence $P\ra Q$ is the conditional sentence $(\sim Q)\ra (\sim P)$.
\end{defn}
\begin{exer}\label{exer:conandcontra}
Determine which of the converse and/or contrapositive is logically equivalent to the conditional sentence $P\ra Q$ and justify
your conclusions with truth tables.
\end{exer}
\begin{exer}
Write the converse and contrapositive of the conditional sentence
\vskip7pt
\centerline{``If $f$ is an even function, then $f(2)=f(-2)$."}
\end{exer}
When the implication between propositions $P$ and $Q$ ``runs both ways", we have a much stronger logical relationship.
\begin{defn}[Biconditional]\label{d:biconditional}
Let $P$ and $Q$ represent propositions. The \emph{biconditional sentence} ``$P$ if and only if $Q$" is expressed symbolically
\[
P \lra Q
\]
and has truth table
\[
\begin{tabular}{| c c | c |} \hline
\(P\) & \(Q\) & \(P \lra Q\) \\ \hline\hline
T & T & T \\
T & F & F \\
F & T & F \\
F & F & T \\ \hline
\end{tabular}
\]
\end{defn}
\begin{exer}\label{exer:twopart}
Use truth tables to show that $P\lra Q$ is logically equivalent to $(P\ra Q)\wedge(Q\ra P)$.
\end{exer}
\begin{exer}
Determine the truth value for each of the following biconditional sentences.
\begin{enumerate}[(i)]
\item ``The moon is made of cheese if and only if the earth is flat."
\item ``$1+1=2$ if and only if $\cos(\pi)=-1$."
\item ````If $5<2$, then $10<7$." if and only if ``Elvis lives." is a proposition."
\end{enumerate}
\end{exer}
As we begin writing mathematics, do not underestimate stylistic considerations. There are many phrases equivalent to the conditional
sentence $P\ra Q$ and a few others equivalent to the biconditional sentence $P\lra Q$. We use these to lend texture and interest to
how we \emph{communicate} mathematics. We end this section with a number of these common phrases, feel free to use them correctly and
stylistically.
\bigskip
\centerline{\ul{Phrases translated by $P\ra Q$}}
\begin{center}
\begin{tabular}{c c}
If $P$, then $Q$. & $Q$, if $P$.\\
$P$ implies $Q$. & $Q$ whenever $P$.\\
$P$ is sufficient for $Q$. & $Q$ is necessary for $P$.\\
$P$ only if $Q$. & $Q$, when $P$.\\
\end{tabular}
\end{center}
\bigskip
\centerline{\ul{Phrases translated by $P\lra Q$}}
\begin{center}
\begin{tabular}{c}
$P$ if and only if $Q$.\\
$P$ iff $Q$.\\
$P$ is equivalent to $Q$.\\
$P$ is necessary and sufficient for $Q$.\\
\end{tabular}
\end{center}
\section{Quantifiers}\label{s:quant}
The mathematical sentence ``$x^2=4$" is not a proposition. In our discussion of Example \ref{e:notprop}, we decided that ``$x^2=4$" is
neither true nor false, but rather has truth value dependent upon the value of the variable $x$ under consideration. If $x=2$, it's true; if
$x=3$ it's false. The need to deal with such expressions motivates the following definition.
\begin{defn}
An \emph{open sentence} $P(x_1, x_2, \ldots, x_k)$ is a sentence containing one or more variables that becomes a proposition
only when the variables are assigned specific values.
The realm of all possible values that the variables may be assigned is called the \emph{universe}.
The collection of all values of the variables in the universe that make a true proposition upon substitution into the open sentence is called
the \emph{truth set} of the open sentence.
\end{defn}
\begin{ex}
Consider the open sentence $P(x)$ : ``$x^2=4$."
\noindent If the universe is the set $\R$ of all real numbers, then the truth set is $\{-2, 2\}$.
\noindent On the other hand, if the universe is the set $\R^+$ of positive real numbers, then the truth set is $\{2\}$.
The point is that it is very important to be clear about the universe within which we are considering open sentences and to
always stop and ask whenever in doubt.$\quad\Box$
\end{ex}
\begin{exer}
Write an open sentence in the universe of real numbers that is true for every member of the universe.
\end{exer}
\begin{exer}
Write an open sentence in the universe of cats that is true for no member of the universe.
\end{exer}
\begin{exer}
Write an open sentence in the universe of vegetables that is true for at least one but not every member of the universe.
\end{exer}
The preceding examples illustrate some of the common types of truth sets for open sentences. There is standard notation for each.
\begin{defn}[Universal Quantifier]\label{d:univ}
Let $P(x)$ be an open sentence with variable $x$. The proposition
\[
(\forall x) P(x)
\]
is read ``For all $x$, $P(x)$" and is true precisely when $P(x)$ is true for \emph{every} value of $x$ in the universe. The
symbol $\forall$ is called the \emph{universal quantifier}.
\end{defn}
\begin{defn}[Existential Quantifier]\label{d:exist}
Let $P(x)$ be an open sentence with variable $x$. The proposition
\[
(\exists x) P(x)
\]
is read ``There exists $x$ such that $P(x)$" and is true precisely when $P(x)$ is true for \emph{at least one} value of $x$ in the universe. The
symbol $\exists$ is called the \emph{existential quantifier}.
\end{defn}
The ability to effectively handle quantified propositions is a necessary condition for reading and writing mathematics. As with all
languages, fluency is earned through practice.
\begin{exer}
Let the universe be the real numbers $\R$. Determine the truth value for each proposition.
\begin{enumerate}[(i)]
\item $(\forall x)(x^2+1\geq 0)$.
\item $(\exists x)(|x|>0)$.
\item $(\forall x)(|x|>0)$.
\item $(\exists x)(2x+3=6x+7)$.
\end{enumerate}
\end{exer}
\begin{exer}
Name a universe in which $(\exists x)(2x+3=6x+7)$ is false.
\end{exer}
\begin{exer}
Name a universe in which $(\exists x)(x^2+1=0)$ is true.
\end{exer}
We have seen already in Section \ref{s:imp} that the negation $\sim$ interacts nicely with parentheses, $\wedge$ and $\vee$. It is
natural to next consider intermingling negations and quantifiers.
\begin{exer}
Let $P(x)$ be an open sentence in some universe. Determine whether the proposition
\[
[\sim(\forall x)P(x)]\lra [(\exists x)(\sim P(x))]
\]
is true or false and justify your conclusion.
\end{exer}
\begin{exer}
Let $P(x)$ be an open sentence in some universe. Determine whether the proposition
\[
[\sim(\exists x)P(x)]\lra [(\forall x)(\sim P(x))]
\]
is true or false and justify your conclusion.
\end{exer}
The results of the previous two exercises are particularly useful when formulating denials of quantified propositions.
\begin{exer}
Write a denial of the proposition
\vskip5pt
\centerline{``All even numbers are divisible by four."}
\end{exer}
\begin{exer}
Write a denial of the proposition
\vskip5pt
\centerline{``Some intelligent people revile mathematicians."}
\end{exer}
\begin{exer}
Let the natural numbers $\N=\{1,2,3,\ldots\}$ be the universe. Translate the proposition
\[
(\forall x)(\,[(x \text{ prime})\wedge(x\neq 2)]\ra[(\exists j)(x=2j+1)]\,)
\]
into English.
\end{exer}
Most of the fundamental theorems in real analysis (Math 431 here at Adelphi) are multiply quantified propositions. Strive
always to take your time and calmly assess such statements.
\begin{exer}\label{exer:nest1}
Let the universe be the real numbers $\R$. Determine the truth value for each proposition.
\begin{enumerate}[(i)]
\item $(\forall x)(\exists y)(x < y)$.
\item $(\exists y)(\forall x)(x < y)$.
\end{enumerate}
\end{exer}
\begin{exer}\label{exer:nest2}
Let the universe be the real numbers $\R$. Write the negation of each proposition.
\begin{enumerate}[(i)]
\item $(\forall x)(\exists y)(x < y)$.
\item $(\exists y)(\forall x)(x < y)$.
\end{enumerate}
\end{exer}
We conclude with the special notation reserved for the situation when an open sentence is true for exactly one member of the
universe.
\begin{defn}[Unique Existential Quantifier]\label{d:uniqexist}
Let $P(x)$ be an open sentence with variable $x$. The proposition
\[
(\exists !x) P(x)
\]
is read ``There exists a unique $x$ such that $P(x)$" and is true precisely when $P(x)$ is true for \emph{exactly one} value of $x$ in the universe. The
symbol $\exists !$ is called the \emph{unique existential quantifier}.
\end{defn}
\begin{exer}
Let the universe be the real numbers $\R$. Determine the truth value for each proposition.
\begin{enumerate}[(i)]
\item $(\exists !x)(x\geq 0 \wedge x \leq 0)$.
\item $(\exists !x)(x > 5)$.
\item $(\exists !x)(x^2 = 4)$
\end{enumerate}
\end{exer}
\begin{exer}
Let $P(x)$ be an open sentence in some universe. Is the quantified proposition
$$\sim(\forall x)(\forall y)[(P(x)\wedge P(y))\Rightarrow x=y]$$ a denial
of $(\exists !x)(P(x))$?
\end{exer}
%%% DEFINITIONS
\section{Definitions}
If what has come before has been the grammar of mathematics, definitions are the vocabulary of mathematics. They are the single most important thing to understand before attacking any mathematical problem.
In English, definitions are modified and changed over time. This is not true in mathematics. Definitions are technical, precise, and immutable. Let's take a look at a familiar definition.
\begin{defn}[Even Integer]
An integer $n$ is \emph{even} if and only if there exists an integer $k$ such that $n = 2k$.
\end{defn}
There are several things to note here. The phrase {if and only if} is a stock mathematical phrase which means that these two ideas are exactly equivalent. Thus, if you have an even integer, you can instantly write it as $2k$ for some other integer $k$. Similarly, if you are trying to show an integer is even, you can do so by showing that it can be written as 2 times some other integer.
Try your hand at writing a few definitions:
\begin{exer} For each term below, formulate a mathematical definition:
\begin{enumerate}
\item odd integer
\item rational number
\item irrational number
\item prime number
\item composite number
\item factor
\item greatest common divisor
\item least common multiple
\item perfect square
\end{enumerate}
\end{exer}
\chapter{Mathematical Proof}
\begin{center}
\small{\em Use punctuation, it's classy.}
\end{center}
\section{What Constitutes Proof?}\label{s:proof?}
In Section \ref{s:word} we spent a fair bit of time convincing one another of the truth or falsity of eight propositions. What followed
in chapter one was all the formalism that we will require for the rest of the term, but we mustn't forget those early days of
argumentation and justification.
There, without naming our actions, the class standard of proof was born. What we demand of ourselves and our peers is
iron-clad reasoning based on religious adherence to agreed-upon definitions, all communicated with cool and unadorned
clarity. We are our own harshest critics and we will accept no substitutes.
Consider, for instance, our proof of Proposition 1.11, restated here as
\begin{theorem}\label{thm:lastletter}
If the list
\[
\{\ \text{\emph{sit}}, \text{\emph{hut}}, \text{\emph{sum}}, W\ \}
\]
is tight and $W$ begins neither with ``s" nor ``h", then the last letter of $W$ is a ``t".
\end{theorem}
\begin{proof}
Suppose that the list $\{\ \text{sit}, \text{hut}, \text{sum}, W\ \}$ is tight and $W$ begins neither with ``s" nor ``h".
If $W$ has a ``u" in its second letter position, $d(\text{sit}, W)\leq 2$ implies that $W$ has a ``t" in its third letter position.
On the other hand, if $W$ does not have a ``u" in its second letter position, $d(\text{hut}, W)\leq 2$ implies that $W$ has a ``t" in its third letter position. In either case, $W$ has a ``t" in its third letter position.
\end{proof}
\newpage
It is instructive to view the proof of Theorem \ref{thm:lastletter} through the lens of formalism provided by chapter one. If we
name the constituent propositions
\begin{center}
\begin{tabular}{c}
$A$ : The list $\{\ \text{sit}, \text{hut}, \text{sum}, W\ \}$ is tight \\
$B$ : $W$ begins neither with ``s" nor ``h" \\
$C$ : The last letter of $W$ is a ``t",\\
\end{tabular}
\end{center}
then the statement of Theorem \ref{thm:lastletter} boils down to
\[
[A \wedge B] \ra C.
\]
According to Definition \ref{d:conditional}, the proposition $P\ra Q$ is automatically true when the antecedent
$P$ is false.
The point is that when we set about proving conditional propositions, we need only concern
ourselves with demonstrating the truth of the consequent \emph{supposing the antecedent is true}.
Here is a template for direct proof of a conditional proposition:
\begin{table}[h]
\begin{center}
\framebox[2.5in]{\begin{tabular}{c c}
\emph{Proof}. Suppose $P$.\\
$\bullet$\\
$\bullet$\\
$\bullet$\\
Therefore, $Q$.$\quad\Box$
\end{tabular}}
\caption{Direct Proof of $P \ra Q$}
\label{t:directstruct}
\end{center}
\end{table}
Consider our proof of Theorem \ref{thm:lastletter} and its underlying structure side by side (note here that the antecedent is
itself the conjunctive proposition $A\wedge B$):
\begin{table}[h]
\begin{center}
\begin{tabular}{l | c}
\(Proof\) & \(Structure\)\\ \hline
{\tiny{Suppose that the list $\{\ \text{sit}, \text{hut}, \text{sum}, W\ \}$ is tight and $W$ begins}} & {\tiny{\emph{Proof}. Suppose $A\wedge B$.}}\\
{\tiny{neither with ``s" nor ``h". If $W$ has a ``u" in its second letter}} & $\bullet$\\
{\tiny{position, $d(\text{sit}, W)\leq 2$ implies that $W$ has a ``t" in its third}} & $\bullet$\\
{\tiny{letter position. On the other hand, if $W$ does not have a ``u"}} & $\bullet$\\
{\tiny{in its second letter position, $d(\text{hut}, W)\leq 2$ implies that}} & $\bullet$\\
{\tiny{$W$ has a ``t" in its third letter position. In either case, $W$ has}} & $\bullet$\\
{\tiny{a ``t" in its third letter position.$\quad\quad\quad\Box$}} & {\tiny{Therefore, $C$.$\quad\Box$}} \\
\end{tabular}
\caption{Proof of Theorem \ref{thm:lastletter} with Corresponding Structure}
\label{t:sidexside}
\end{center}
\end{table}
The devil is in the $\bullet\bullet\bullet$, of course. Sometimes the details of the logical path will be a straightforward matter of
successive application of the definitions, as in Table \ref{t:sidexside}. Often, however, your own creativity and ingenuity will be
necessary. This is the art of proof and it is what we are learning in this class. Practice well to hone your craft.
Theorem \ref{thm:lastletter} is the only theorem in this book where the proof is provided. Henceforth, you will prove
every theorem that arises. You may use only the relevant definitions, exercises and theorems that we have already
established.
\begin{defn}\label{d:divides}
Let $\Z = \{\ldots, -2, -1, 0, 1, 2,\ldots \}$ be the \emph{integers}. We say that the integer $a$ \emph{divides} the integer $b$
if there exists an integer $k$ such that $b=ak$.
\end{defn}
\begin{ex}
The integer $6$ divides the integer $42$ because $42=6\cdot7$. The integer $8$ does not divide the integer $34$ because
there is no integer $k$ such that $34=8k$.\hskip10pt$\Box$
\end{ex}
\begin{theorem}
Let $a$, $b$ and $c$ be integers. If $a$ divides $b$, then $a$ divides $bc$.
\end{theorem}
\begin{theorem}
Let $a$, $b$ and $c$ be integers. If $a$ divides $b$ and $a$ divides $b+c$, then $a$ divides $3c$.
\end{theorem}
\begin{theorem}
If $x$ and $y$ are even integers, then $x+y$ is an even integer.
\end{theorem}
\begin{theorem}
If $x$ and $y$ are odd integers, then $x+y$ is an even integer.
\end{theorem}
\begin{theorem}
If $x$ and $y$ are even integers, then $4$ divides $xy$.
\end{theorem}
\begin{theorem}
If $x$ is an integer, then $x^2+x+3$ is an odd integer.
\end{theorem}
\begin{theorem}
The product of consecutive integers is an even integer.
\end{theorem}
\begin{refer} Write down as much as you can about constructing a direct proof. \end{refer}
\section{Three More Basic Proof Structures}\label{s:proofstructures}
In Section \ref{s:proof?} we used the direct proof structure of Table \ref{t:directstruct} to discuss what we mean
by ``proof". Our answer
\begin{quote}
``What we demand of ourselves and our peers is
iron-clad reasoning based on religious adherence to agreed-upon definitions, all communicated with cool and unadorned
clarity. We are our own harshest critics and we will accept no substitutes."
\end{quote}
is, however, independent of the method of proof. In this section we take note of three more basic proof structures and put
them to use proving some more theorems.
\subsection{Proof of {$P\ra Q$} by Contraposition}
According to Exercise \ref{exer:conandcontra}, the contrapositive $(\sim Q)\ra (\sim P)$ is equivalent to the
conditional proposition $P\ra Q$. Thus, to prove $P\ra Q$ it is equivalent to prove $(\sim Q)\ra (\sim P)$. The resulting
proof structure is called ``Proof by Contraposition" and is illustrated in Table \ref{t:contrastruct}.
\begin{table}[h]
\begin{center}
\framebox[2.5in]{\begin{tabular}{c c}
\emph{Proof}. Suppose $\sim Q$.\\
$\bullet$\\
$\bullet$\\
$\bullet$\\
Therefore, $\sim P$.\\
Thus, $P\ra Q$.$\quad\Box$
\end{tabular}}
\caption{Proof of $P \ra Q$ by Contraposition.}
\label{t:contrastruct}
\end{center}
\end{table}
\begin{theorem}\label{thm:squaredivide}
Let $x$ be an integer. If 4 does not divide $x^2$, then $x$ is odd.
\end{theorem}
\begin{theorem}
Let $x$ be an integer. If 8 does not divide $x^2-1$, then $x$ is even.
\end{theorem}
\begin{theorem}\label{thm:evenprod}
Let $x$ and $y$ be integers. If $xy$ is even, then either $x$ is even or $y$ is even.
\end{theorem}
\begin{refer} Write down as much as you can about proof by contrapositive. Pay particular attention to determining when using a proof by contrapositive is appropriate. \end{refer}
\subsection{Proof of $P\lra Q$}
According to Exercise \ref{exer:twopart}, the biconditional proposition $P\lra Q$ is logically equivalent to $(P\ra Q)\wedge(Q\ra P)$.
Thus, to prove $P\lra Q$ it is equivalent to prove $(P\ra Q)\wedge(Q\ra P)$. The resulting proof structure is a two-part
proof and is illustrated in Table \ref{t:twopartstruct}.
\begin{table}[h]
\begin{center}
\framebox[3.5in]{\begin{tabular}{l c}
\emph{Proof}.\\
(i) Show $P\ra Q$ directly or by contraposition.\\
$\bullet$ $\bullet$ $\bullet$\\
(ii) Show $Q\ra P$ directly or by contraposition.\\
$\bullet$ $\bullet$ $\bullet$\\
Therefore, $(P\ra Q)\wedge(Q\ra P)$.\\
Thus, $P\lra Q$.$\quad\Box$
\end{tabular}}
\caption{Two-part Proof of $P \lra Q$.}
\label{t:twopartstruct}
\end{center}
\end{table}
\begin{theorem}
Let $a$, $b$ and $c$ be positive integers. The integer $ac$ divides $bc$ if and only if the integer $a$ divides $b$.
\end{theorem}
\begin{theorem}
Let $a$ and $b$ be positive integers. The integer $a+1$ divides $b$ and the integer $b$ divides $b+3$
if and only if $a=2$ and $b=3$.
\end{theorem}
\begin{theorem}
Let $x$ be a real number. The quadratic $x^2+2x+1=0$ if and only if $x=-1$.
\end{theorem}
\subsection{Proof by Contradiction}
Imagine we wish to prove some proposition $P$ and we instead prove that
\[
(\sim P) \ra 1=2.
\]
Because we know that the consequent $1=2$ is false, the truth of $(\sim P) \ra 1=2$ implies that the
antecedent $\sim P$ is false. We therefore conclude that the original proposition $P$ is true.
The preceding example illustrates ``Proof by Contradiction", whereby assuming the negation of what we wish
to prove leads logically to absurdity ($1=2$ in the present case). The general structure of proof by contradiction is
illustrated in Table \ref{t:contradict}.
\begin{table}[h]
\begin{center}
\framebox[2.5in]{\begin{tabular}{c c}
\emph{Proof}. Suppose $\sim P$.\\
$\bullet$\\
$\bullet$\\
$\bullet$\\
Therefore, $Q$.\\
But $\sim Q$ is true.\\
Therefore, $P$.$\quad\Box$
\end{tabular}}
\caption{Proof of $P$ by Contradiction.}
\label{t:contradict}
\end{center}
\end{table}
Again, the role of proposition $Q$ is being played by ``$1=2$" in our example above. Generally, the key to proof
by contradiction lies in deciding what proposition will play the role of $Q$ in the structure of Table \ref{t:contradict}.
\begin{exer}\label{exer:pqcontradiction}
Determine what supposition would begin a proof of $P\ra Q$ by contradiction.
\end{exer}
\begin{defn}\label{d:rational}
A real number $r$ is called \emph{rational} if there exist integers $p$ and $q$ (with $q\neq 0$) such that
\[
r =\frac{p}{q}.
\]
A real number that is not rational is called \emph{irrational}.
\end{defn}
The following is a classic. If you believe in the number $\sqrt{2}$, then this theorem says it's irrational.
\begin{theorem}
If $r$ is a real number and $r^2=2$, then $r$ is irrational.
\end{theorem}
The following proposition is not a classic. It's good, though.
\begin{prop}
At any Adelphi basketball game there are at least two people in attendance with the same number of friends in attendance.
\end{prop}
Google ``hardest logic puzzle ever" if you enjoy this next one!
\begin{prop}
Suppose Chip Dibson and Dip Dobson come from a land where each person either always lies or always tells the truth. If Chip says ``Exactly one of us is lying" and Dip says ``Chip is telling the truth", then Chip and Dip are both lying.
\end{prop}
\begin{caut}
Many mathematicians view proofs by contradiction as being less than ideal. One reason for this is that they may
provide less insight by their very nature. For instance, a direct proof of $P\ra Q$ may literally exhibit the \emph{way}
that $P$ implies $Q$, whereas a proof of $P\ra Q$ by contradiction may only demonstrate that $P$ and $\sim Q$ are
incompatible.
Moreover, many proofs by contradiction are in fact nice proofs by contraposition that have been kidnapped and
dressed up in ill-fitting clothes. For example, consider a worse version of our proof of Theorem \ref{thm:squaredivide}:
\begin{proof}
Suppose that $4$ does not divide $x^2$ and $x$ is even. {\bf{Since $x$ is even, there exists an integer $j$ such that $x=2j$,
so $x^2=(2j)^2=4j^2$. Thus, $4$ divides $x^2$.}} But this contradicts the supposition that $4$ does not divide $x^2$.
Thus, if $4$ does not divide $x^2$, then $x$ is odd.
\end{proof}
The bold portion of the proof is our nice tidy proof by contraposition of Theorem \ref{thm:squaredivide}; the rest is just
clumsy and extraneous noise.
In this class, let us strive always to avoid
proof by contradiction and to instead employ another method of proof whenever possible.
\end{caut}
\begin{refer} Write down as much as you can about proof by contradiction. Pay particular attention to determining when using a proof by contradiction is appropriate. \end{refer}
\begin{refer} Both proof by contrapositive and proof by contradiction are indirect proof methods and work heavily with negations of portions of the original statement. Explain how they differ. Pay particular attention to the information that we are allowed to assume true in a proof by contrapositive versus a proof by contradiction. Also, pay attention to the difference between having a conclusion to aim for and not knowing what conclusion to aim for. \end{refer}
\section{Proofs of Quantified Propositions}\label{s:quantproof}
Many of the most fundamental definitions and theorems in advanced mathematics involve the quantifiers
$\forall$ and $\exists$. Facility in proving quantified propositions is critical to future success.
\subsection{Existence Proofs}\label{ss:exist}
\begin{prop}\label{p:exists}
There exists a real number $x$ such that $x^2=4$.
\end{prop}
The statement of Proposition \ref{p:exists} may be symbolized by
\[
(\exists x)( x^2=4 )
\]
in the universe of real numbers. In this instance, the proof consisted of actually producing a specific, concrete value of
$x$ that made the open sentence $x^2=4$ into a true proposition. Such existence proofs are called \emph{constructive}
because the desired object has been constructed and presented to the reader. Table \ref{t:existstruct} illustrates the
structure of such existence proofs.
\begin{table}[h]
\begin{center}
\framebox[2.5in]{\begin{tabular}{c c}
\emph{Proof}. Consider the object $\star$.\\
$\bullet$\\
$\bullet$\\
$\bullet$\\
Therefore, $P(\star)$ is true.\\
Thus, $(\exists x) P(x)$.$\quad\Box$
\end{tabular}}
\caption{Constructive Proof of $(\exists x) P(x)$.}
\label{t:existstruct}
\end{center}
\end{table}
\begin{caut}
Not all existence proofs are constructive. Sometimes, a valid existence proof leaves us certain that \emph{some} object
with particular properties exists, yet leaves us with no idea what \emph{specific} object it is.
\end{caut}
\begin{prop}
There exists a three-digit number less than 400 with distinct digits that sum to 17 and multiply to 108.
\end{prop}
\begin{prop}
There exist irrational numbers $x$ and $y$ such that $x+y$ is rational.
\end{prop}
\begin{prop}\label{p:rootpower}
There exists an irrational number $r$ such that $r^{\sqrt{2}}$ is rational.
\end{prop}
\begin{prop}
There exist integers $m$ and $n$ such that $7m+2n=1$.
\end{prop}
\begin{prop}
Some two grandmothers of past or present U.S. presidents have birthdays within eleven days of one another.
\end{prop}
\subsection{Proofs of Universal Propositions}
In order to prove a universally quantified proposition $(\forall x)P(x)$, we must show that \emph{every} specific
value of $x$ in the universe under consideration yields a true proposition $P(x)$.
\begin{prop}
For every odd integer $n$, $2n^2+3n+4$ is odd.
\end{prop}
Table \ref{t:forallstruct} illustrates the typical structure of a proof of $(\forall x) P(x)$. The key thing is to begin by considering
an \emph{arbitrary} object $x$ from the relevant universe, resisting all temptation to ascribe any characteristics to $x$
beyond those given by the hypotheses and mere membership in the universe.
\begin{table}[h]
\begin{center}
\framebox[2.5in]{\begin{tabular}{c c}
\emph{Proof}. Let $x$ be an arbitrary\\
member of the universe $U$.\\
$\bullet$\\
$\bullet$\\
$\bullet$\\
Therefore, $P(x)$ is true.\\
Thus, $(\forall x) P(x)$.$\quad\Box$
\end{tabular}}
\caption{Proof of $(\forall x) P(x)$ in the Universe $U$.}
\label{t:forallstruct}
\end{center}
\end{table}
\begin{theorem}
For all positive real numbers $x$ and $y$, ${\displaystyle{\frac{x+y}{2}\geq\sqrt{xy}}}$.
\end{theorem}
Commonly, the statement $P(x)$ in some quantified proposition $(\forall x) P(x)$ is itself a quantified proposition. See
Exercises \ref{exer:nest1} and \ref{exer:nest2} to recall what is at stake in such multiply quantified propositions.
\begin{prop}
For every real number $x$ there exists a real number $y$ such that $x < y$.
\end{prop}
\begin{prop}
There exists a real number $y$ such that for every real number $x$, $x < y$.
\end{prop}
\begin{prop}
For each real number $x$ there exists a real number $y$ such that $x + y = 0$.
\end{prop}
\begin{prop}
For every positive real number $x$ there exists a positive real number $y < x$ such that
$(\forall z)(z>0 \ra yz \geq z)$.
\end{prop}
\begin{prop}
For every positive real number $\varepsilon$ there exists a positive integer $N$ such that
$n \geq N \ra 1/n < \varepsilon$.
\end{prop}
\subsection{Unique Existence Proofs}
\begin{prop}\label{p:unique}
There exists a unique real number whose square is $4$.
\end{prop}
Proposition \ref{p:unique} is clearly false. Not because there is no such real number, but because there are too many. The
point is that in order to prove a unique existence proposition $(\exists ! x)P(x)$, \emph{two} things must be done:
(i) an existence proof a la subsection \ref{ss:exist} and (ii) a proof that there is at most one object $x$ such that $P(x)$ is true.
\begin{table}[h]
\begin{center}
\framebox[3.5in]{\begin{tabular}{l c}
\emph{Proof}.\\
(i) Show $(\exists x)P(x)$ by some method.\\
$\bullet$ $\bullet$ $\bullet$\\
(ii) Show $[ P(x_1)\wedge P(x_2) ] \ra [ x_1 = x_2 ]$.\\
$\bullet$ $\bullet$ $\bullet$\\
Thus, $(\exists ! x)P(x)$.$\quad\Box$
\end{tabular}}
\caption{Two-part Proof of $(\exists ! x)P(x)$.}
\label{t:uniquestruct}
\end{center}
\end{table}
Part (ii) of Table \ref{t:uniquestruct} requires we prove the conditional proposition
\[
[ P(x_1)\wedge P(x_2) ] \ra [ x_1 = x_2 ].
\]
All of the techniques we have encountered already (direct proof, proof by contraposition, proof by contradiction) are
potentially viable here and we should treat the proof of this implication as we would any other.
\begin{prop}
There exists a unique positive real number whose square is $4$.
\end{prop}
\begin{defn}
A \emph{queen} is a chess piece that can attack along rows, columns and diagonals. A \emph{truce} is
an arrangement of mutually non-attacking queens.
\end{defn}
\begin{figure}[h]
\centering
\begin{tikzpicture}[scale = .75]
\draw(0,0) grid (8,8);
\draw[fill = gray] (0,0) rectangle (1,1);
\draw[fill = gray] (2,0) rectangle (3,1);
\draw[fill = gray] (4,0) rectangle (5,1);
\draw[fill = gray] (6,0) rectangle (7,1);
\draw[fill = gray] (0,2) rectangle (1,3);
\draw[fill = gray] (2,2) rectangle (3,3);
\draw[fill = gray] (4,2) rectangle (5,3);
\draw[fill = gray] (6,2) rectangle (7,3);
\draw[fill = gray] (0,4) rectangle (1,5);
\draw[fill = gray] (2,4) rectangle (3,5);
\draw[fill = gray] (4,4) rectangle (5,5);
\draw[fill = gray] (6,4) rectangle (7,5);
\draw[fill = gray] (0,6) rectangle (1,7);
\draw[fill = gray] (2,6) rectangle (3,7);
\draw[fill = gray] (4,6) rectangle (5,7);
\draw[fill = gray] (6,6) rectangle (7,7);
\draw[fill = gray] (1,1) rectangle (2,2);
\draw[fill = gray] (3,1) rectangle (4,2);
\draw[fill = gray] (5,1) rectangle (6,2);
\draw[fill = gray] (7,1) rectangle (8,2);
\draw[fill = gray] (1,3) rectangle (2,4);
\draw[fill = gray] (3,3) rectangle (4,4);
\draw[fill = gray] (5,3) rectangle (6,4);
\draw[fill = gray] (7,3) rectangle (8,4);
\draw[fill = gray] (1,5) rectangle (2,6);
\draw[fill = gray] (3,5) rectangle (4,6);
\draw[fill = gray] (5,5) rectangle (6,6);
\draw[fill = gray] (7,5) rectangle (8,6);
\draw[fill = gray] (1,7) rectangle (2,8);
\draw[fill = gray] (3,7) rectangle (4,8);
\draw[fill = gray] (5,7) rectangle (6,8);
\draw[fill = gray] (7,7) rectangle (8,8);
\node at (.5, -.4) {a};
\node at (1.5, -.4) {b};
\node at (2.5, -.4) {c};
\node at (3.5, -.4) {d};
\node at (4.5, -.4) {e};
\node at (5.5, -.4) {f};
\node at (6.5, -.4) {g};
\node at (7.5, -.4) {h};
\node at (-.4, .5) {1};
\node at (-.4, 1.5) {2};
\node at (-.4, 2.5) {3};
\node at (-.4, 3.5) {4};
\node at (-.4, 4.5) {5};
\node at (-.4, 5.5) {6};
\node at (-.4, 6.5) {7};
\node at (-.4, 7.5) {8};
\end{tikzpicture}
\caption{A standard chess board.}
\label{f:board}
\end{figure}
\begin{prop}
There exists a truce of eight queens on the standard chess board.
\end{prop}
\begin{prop}
There does not exist a truce of six queens on a 6x6 chess board in which a corner
of the board is occupied.
\end{prop}
\begin{prop}
There exists a unique truce of six queens on a 6x6 chess board.
\end{prop}
\section{Proof By Induction}\label{s:induction}
Mathematics students tend to fall into one of two camps: the ``Induction is awesome! I hope every problem on the test is induction."-camp or the ``I don't get this induction business!"-camp. Neither camp is ideal. I aim for you to believe that induction is in fact awesome, but you should also take a few trips into the other camp and let it mess with your head a bit. It is easy to end up with only a skin deep level of understanding, and we avoid this by doing some deep thinking, letting our brains hurt, and by the end of this section we will all \emph{grok}\footnote{From Spivak's {\it A Comprehensive Introduction to Differential Geometry}: ``A cult word of the sixties, `grok' was coined, purportedly as a word from the Martian language, by Robert A, Heinlein in his pop science fiction novel {\it Stranger in a Strange Land}. Its sense is nicely conveyed by the definition in {\it The American Heritage Dictionary}: 'To understand profoundly through intuition or empathy'."} induction!
Consider the statement \begin{center} {\it For all integers $n \geq 1$, $\ds{1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}}$.} \end{center}
If this proposition is in fact true, it is actually infinitely many theorems. We could define the open sentence $P(n)$ to be ``$\ds{1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}}$'' and prove that $P(n)$ is true in the universe of natural numbers. Mathematical induction allows to prove all $P(n)$ in one fell swoop, or as one of my favorite physics professors used to say, ``One swell foop!".
\subsection{Just One Step: Weak Induction}
\begin{exer}\label{exer:Induct}
Let $P(1), P(2), \ldots, P(n), \ldots$ be a list of propositions (one for each natural number). Explain why establishing the following two conditions is enough to conclude that \emph{every} proposition on the list is true:
\begin{enumerate}
\item $P(1)$ is true.
\item For each natural number $k$, if $P(k)$ is true, then $P(k+1)$ is true.
\end{enumerate}
\end{exer}
The logical idea encapsulated in Exercise \ref{exer:Induct} is the foundation of mathematical induction. Table \ref{t:inducstruct} gives the typical structure of a proof by induction.
\begin{table}[h]
\begin{center}
\framebox[5in]{\begin{tabular}{l c}
\emph{Proof}.\\
(i) Show $P(1)$.\\
$\bullet$ $\bullet$ $\bullet$\\
(ii) Show $(\forall k \in \N) (P(k) \ra P(k+1))$. \\
$\bullet$ $\bullet$ $\bullet$\\
Therefore $P(n)$ is true for every natural number $n$ by induction.$\quad\Box$
\end{tabular}}
\caption{Weak Induction Proof.}
\label{t:inducstruct}
\end{center}
\end{table}
Part (i) of Table \ref{t:inducstruct} is referred to as the \emph{base case} and the assumption of $P(k)$ in part (ii) is called the \emph{induction hypothesis}. $P(k) \ra P(k+1)$ is an implication that should be treated like all others; use the method you see fit to prove its truthfulness.
\begin{theorem}
For each $n \in \N$, $\ds{1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}}$.
\end{theorem}
\begin{prop}
For each $n \in \N$, $3^n \geq1 + 2^n$.
\end{prop}
\begin{prop}
Let $x$ be a real number with $x \neq 1$. For all natural numbers $n$,
\[1+x+x^2+\ldots+x^n = \frac{1-x^{n+1}}{1-x}.\]
\end{prop}
\begin{exer} Find a formula for the sum of the first $n$ odd integers and prove it is true by induction.
\[1+3+5+\ldots+(2n-1) = ?.\] \end{exer}
\begin{prop}\label{prop:seq} Define a sequence $a_n$ via: $a_1 = 1$ and $a_{n+1} = \sqrt{1+a_n}$. For all $n \geq 1$, $a_n < 2$. \end{prop}
\begin{prop} Each term $a_n$ of the sequence in Proposition \ref{prop:seq} is less than 2. \end{prop}
\subsection{$k$ Steps: Strong Induction}
If you spend some time thinking about the induction that we performed in the last section, you will realize that we aren't employing all of the information that we have available. First, we establish a base case. Then we try to show that if the statement is true for $n = k$, we can deduce that it is true for $n = k+1$. Why should we restrict ourselves to only knowing the truth at $n = k$? To get it to be true at $n = k$, surely we must have shown the truth at $n = k-1$. And to get it true at $n = k-1$, we must have shown the truth at $n = k-2$. In fact, to get truth at $n = k$, we must know truth for $n = 1, 2, \ldots, k-1$ first. That's a whole lot of true statements that we haven't been utilizing in our proofs!
\begin{exer}\label{exer:recursion}
Let $a_1=2$, $a_2=4$ and $a_n=5a_{n-1}-6a_{n-2}$ for $n\geq 3$. Determine an explicit
formula depending on $n$ for the $n$th term $a_n$ and prove that your formula holds for all $n\in\N$.
\end{exer}
\begin{theorem}\label{thm:primefac}
Every integer $p>1$ can be expressed as a product of prime numbers.
\end{theorem}
\section{The Deep Blue Sea}
We have done thirty-four proofs so far in this chapter, which is great. But our experience proving things differs
from reality in one fundamental way: in each of our thirty-four successes we have known in advance what proof
technique to attempt.
In mathematical reality, one encounters a proposition and formulates some feeling for whether it's true or false and
then \emph{decides} on an approach. Sometimes things go smoothly and our first inclination bears fruit; often, we choose poorly and have to go back to the drawing board.
The very best provers share a certain fearlessness and an ability to greet failure with a smile, confident that with
every false step they have added to their unique and priceless personal wisdom.
There is not one shred of
mathematical content in this class that can't be recalled or looked up at a later time, but the conditions assembled
here that have allowed us to see with new eyes cannot be recreated. Your opportunity to start anew has arrived, and
it is singular.
We have the tools. We are fearless. Now into the sea...
% --------------------------------------------------------------
% You don't have to mess with anything below this line.
% --------------------------------------------------------------
\end{document}