% \documentclass tells what type of document you are preparing.
% ''article'' is the most generic type and works for anything you'll be doing
\documentclass{article}
% \usepackage imports packages with new symbols
% There are LOTS of possible packages, but the ones below cover most everything
% you'll need for math and graphics.
\usepackage{amsmath,amsthm,amssymb,latexsym,graphicx}
% \newtheorem lets you name a few different kinds of theorem environments
% The first argument is what you want the command to be named.
% The second argument is the word that should actually appear in the document.
% The optional third argument tells them all to use the same numbering scheme.
% It will make more sense when you see it in use later in the document.
\newtheorem*{thm}{Theorem}
\newtheorem*{prop}{Proposition}
\newtheorem*{defn}{Definition}
\newtheorem*{lem}{Lemma}
\newtheorem*{cor}{Corollary}
\newtheorem*{conj}{Conjecture}
% Put your title, author, and date information BEFORE \begin{document},
% then call the \maketitle command immediately after \begin{document}
\title{Example Proofs}
\author{Austin Mohr}
\date{\today} % You can specify a date, or just use \today to use today's date.
% \begin{document} and \end{document} mark the beginning and end of the
% part of the document you actually want to be typeset
\begin{document}
\maketitle
% Students kept including definitions
%\begin{defn}
%An integer $n$ is an \emph{odd integer} provided there exists an integer $k$ such that $n = 2k + 1$.
%\end{defn}
\section*{Direct Proof}
\begin{prop}
If $n$ is odd, then $n^3$ is odd.
\end{prop}
\begin{proof}
Since $n$ is odd, we may write $n = 2k + 1$ for some integer $k$. We aim to show that $n^3$ is odd, so we consider
\begin{align*}
n^3 &= (2k + 1)^3\\
&= 8k^3 + 12k^2 + 6k + 1\\
&= 2(4k^3 + 6k^2 + 3k) + 1.
\end{align*}
By the closure of the integers under addition and multiplication, we know that $4k^3 + 6k^2 + 3k$ is an integer. Call this integer $m$, so that we have $n^3 = 2m + 1$. Therefore, $n^3$ is odd.
\end{proof}
\section*{Weak Induction}
\begin{prop}
For all natural numbers $n$, we have the identity
\[
1 + 2 + \dots + n = \frac{1}{2}n(n+1).
\]
\end{prop}
\begin{proof}(by induction)
First observe that when $n=1$, the identity becomes
\[
1 = \frac{1}{2} \cdot 1 \cdot 2,
\]
which is a true statement.
Suppose now that there exists a natural number $k$ such that
\[
1 + 2 + \dots + k = \frac{1}{2}k(k+1).
\]
We aim to show that this implies
\[
1 + 2 + \dots + (k+1) = \frac{1}{2}(k+1)(k+2).
\]
Applying the inductive hypothesis in the first line, we have
\begin{align*}
(1 + 2 + \dots + k) + (k + 1) &= \frac{1}{2}k(k+1) + (k+1)\\
&= (k+1)\left(\frac{1}{2}k + 1\right)\\
&= \frac{1}{2}(k+1)(k+2),
\end{align*}
as desired.
\end{proof}
\section*{Strong Induction}
\begin{prop}
Define the recurrence $a_n = 2a_{n-1} + a_{n-2}$ for $n \geq 2$ with $a_0 = 1$ and $a_1 = 2$. For all natural numbers $n$, we have the inequality $a_n \leq 3^n$.
\end{prop}
\begin{proof} (by strong induction)
First observe that when $n \in \{1, 2\}$, the inequality becomes $1 \leq 3^0$ and $2 \leq 3^1$, both of which are true statements.
Suppose now that there exists a natural number $k \geq 3$ such that $a_{k-1} \leq 3^{k-1}$ and $a_k \leq 3^k$. We aim to show that these together imply $a_{k+1} \leq 3^{k+1}$. To that end, observe
\begin{align*}
a_{k+1} &= 2a_k + a_{k-1} &&\text{(by definition)}\\
&\leq 2 \cdot 3^k + 3^{k-1} &&\text{(by strong inductive hypothesis)}\\
&= 3^{k-1}(2 \cdot 3 + 1)\\
&< 3^{k-1} \cdot 9\\
&= 3^{k+1},
\end{align*}
as desired.
\end{proof}
\section*{Set Algebra}
\begin{prop}
The identity $(A \cup B) - C = (A - C) \cup (B - C)$ holds for all sets $A$, $B$, and $C$.
\end{prop}
\begin{proof}
Observe,
\begin{align*}
(A \cup B) - C &= (A \cup B) \cap C^c && \text{(definition of set difference)}\\
&= (A \cap C^c) \cup (B \cap C^c) &&\text{(distributive law)}\\
&= (A - C) \cup (B - C) && \text{(definition of set difference),}
\end{align*}
thus completing the proof.
\end{proof}
You can also give the appearance of two columns in the following way.
\begin{prop}
The identity $(A \cup B) - C = (A - C) \cup (B - C)$ holds for all sets $A$, $B$, and $C$.
\end{prop}
\begin{proof}
Observe,
\begin{align*}
& (A \cup B) - C\\
= & (A \cup B) \cap C^c && \text{(definition of set difference)}\\
= & (A \cap C^c) \cup (B \cap C^c) &&\text{(distributive law)}\\
= & (A - C) \cup (B - C) && \text{(definition of set difference),}
\end{align*}
thus completing the proof.
\end{proof}
% Here's the end of the document
\end{document}
% Maybe doesn't add anything new
%\begin{defn}
%A nonzero integer $m$ \emph{divides} an integer $n$ provided there is an integer $k$ such that $n = mk$.
%\end{defn}
%
%\begin{prop}
%Let $a, b, c \in \mathbb{Z}$ with $a \neq 0$. If $a \mid b$ and $a \mid c$, then $a \mid (b - c)$.
%\end{prop}
%
%\begin{proof}
%Since $a \mid b$ and $a \mid c$, we may write $b = aj$ and $c = ak$ for some $j,k \in \mathbb{Z}$. It follows that
%\begin{align*}
%b - c &= aj - ak\\
%&= a(j - k).
%\end{align*}
%The integers are closed under subtraction, so $j - k$ is some integer $m$. Thus, we have shown $b - c = am$, which is to say $a \mid (b - c)$.
%\end{proof}