\documentclass[12pt]{amsart}

\usepackage{amsmath, amssymb, amsthm}
\usepackage[margin=0.5in]{geometry}
\usepackage[pdflang={en-US}]{hyperref}
\usepackage[shortlabels]{enumitem}

\usepackage{tikz}

\renewcommand{\thesection}{\Alph{section}}

\newcommand{\scs}[1]{\begin{scshape}#1\end{scshape}}
\newcommand{\inv}{^{-1}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\nmod}[1][n]{\left(\text{mod}\ #1\right)}

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem{problem}{}
\newtheorem*{challenge}{Challenge}
\newtheorem*{example}{Example}

\newcommand{\thm}[1]{\begin{theorem}#1\end{theorem}}
\newcommand{\prob}[1]{\begin{problem}#1\end{problem}}
\newcommand{\dfn}[1]{\begin{definition}#1\end{definition}}
\newcommand{\chal}[1]{\begin{challenge}#1\end{challenge}}
\newcommand{\eg}[1]{\begin{example}#1\end{example}}

\newcommand{\abs}[1]{\left| #1 \right|}

\title{Induction II \dots and relations}
\date{November 12, 2018}

\begin{document}

\maketitle

\prob{
Find the flaw in the following proof.

\thm{If $n \in \NN$, then $n$ is odd}

\begin{proof}[Proof by strong induction]

Base case: $n=1$. Then $n$ is clearly odd.

Now suppose that $k \in \NN$ and that if $l \in \NN$ and $l \leq k$, then $l$ is odd.
Consider that $k +1 = (k-1) + 2$ and that $k-1 \leq k$.
By IH $k-1$ is odd.
Hence $k-1 = 2a+1$ for some integer $a$.
We now have \begin{align*}
k+1 &= (k-1)+2 \\
&=(2a+1) +2 \\
&= 2(a+1) + 1.
\end{align*}
Since $a+1$ is an integer, we have shown that $k+1$ is odd.

Therefore, by strong induction, every natural number is odd.
\end{proof}

\vspace{1in}

}

\prob{
Complete any necessary bases cases in the following proof.

\thm{
If $n \in \NN$, then $12|(n^4-n^2)$.
}

\begin{proof}[Proof by strong induction]
We will defy tradition and begin with the inductive step.
Let $k \in \NN$ and suppose that if $l\in \NN$ and $l \leq k$, then $12|(l^4 - l^2)$.
We wish to prove that $12|\left((k+1)^4 - (k+1)^2\right)$.

Let $l = k-5$.
Then $l \leq k$, so by IH $12|(l^4 -l^2)$.
Hence there is an integer $a$ such that $l^4 - l^2 = 12a$.
Then \begin{align*}
(k+1)^4 - (k+1)^2 &= (l+6)^4 - (l+6)^2 \\
&= l^4 + 24l^3 + 216l^2 + 864l + 1296 - (l^2 + 12l + 63) \\
&= (l^4 - l^2) + 24l^3 +216l^2 + 852l + 1260 \\
&= 12a + 24l^3 +216l^2 + 852l + 1260 \\
&= 12(a + 2l^3 + 18l^2 + 71l + 105).
\end{align*} 
It follows that $12|\left((k+1)^4 - (k+1)^2\right)$.

We now must establish the base cases to complete the proof.

\vfill

\end{proof}
}

\newpage

\dfn{
Let $R$ be a relation on a set $A$.
\begin{itemize}
\item $R$ is \textbf{reflexive} if $\forall x \in A,\ xRx$.
\item $R$ is \textbf{symmetric} if $\forall x, y \in A,\ xRy \implies yRx$.
\item $R$ is \textbf{transitive} if $\forall x, y, z \in A,\ (xRy \land yRz) \implies x R z$.
\end{itemize}
}

\prob{
Which of the three properties in the definition does the relation of $<$ (on $\RR$) have?
}

\vfill

\prob{
Which of the three properties in the definition does the relation of divides (on $\ZZ$) have?
}

\vfill

\prob{
Which of the three properties in the definition does the relation of congruence modulo 5 (on $\ZZ$) have?
}

\vfill

\end{document}