\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}

\title{Recitation 9}
\author{Taylor Spangler}

\begin{document}
\maketitle

\begin{itemize}
\item (3 min max) Questions about last week's quiz?
\item Questions about lecture / homework so far?

\item Given the Poset: $(\{\{1\},\{2\},\{4\},\{1,2\},\{1,4\},\{2,4\},\{3,4\},\{1,3,4\},\{2,3,4\}\},\subseteq)$
\begin{enumerate}
\item Find the maximal elements:$\{1,2\}, \{1,3,4\},\{2,3,4\}$ (because these are not subsets of any other sets in the relation right?)
\item Find the minimal elements$: \{1\},\{2\},\{4\}$ (again, there are no subsets of these sets in the relation)
\item Is there a greatest element?: No
\item Is there a least element?: No
\item Find all of the upper bounds of $\{\{2\},\{4\}\}$: $\{\{2,4\},\{2,3,4\}\}$
\item Find the least upper bound of $\{\{2\},\{4\}\}$: $\{2,4\}$
\item Find all lower bounds of $\{\{1,3,4\},\{2,3,4\}$: $\{\{3,4\},\{4\}\}$
\item Find the greatest lower bound of $\{\{1,3,4\},\{2,3,4\}\}$: \{3,4\}
\end{enumerate}


\item Induction: Example using triominoes for $2^{n}\times2^{n}$ checkerboard missing one corner, see page 326.

\item Now, problem 5.1.5, using induction prove: $1^2+3^2+...+(2n+1)^{2} = \frac{(n+1)(2n+1)(2n+3)}{3}$ for nonnegative $n$.
\begin{enumerate}
\item Here we can see the base case is 0 (we want $n$ to be nonnegative and an integer, note not the same as positive), what is $P(0)$? $P(0) = 1 = \frac{(1)(1)(3)}{3}$
\item Show that P(0) is true:1 = 1.$ \frac{1*1*3}{3} = 1$. Therefore P(0) is true.
\item What is the inductive hypothesis? $P(k)$ is true, that is $1^2+ 3^2+...+(2k+1)^{2} = \frac{(k+1)(2k+1)(2k+3)}{3}$.
\item We want to prove: $P(k+1)$ that is $1^2+ 3^2+...+(2k+3)^{2} = \frac{(k+2)(2k+3)(2k+5)}{3}$
\item So we have that $P(k)$ is true, $P(k+1)$ is really just $1^2+ 3^2+...+(2k+1)^2+(2k+3)^2$. By our inductive hypothesis, we have that this is really $ \frac{(k+1)(2k+1)(2k+3)}{3}+(2k+3)^2$.
This equals $(2k+3)*(\frac{(k+1)(2k+1)+6k+9}{3})$ = $(2k+3)*(\frac{2k^2+9k+10}{3})$ = $\frac{(k+2)(2k+3)(2k+5)}{3}$...this is what we were trying to prove, therefore, by induction,  $1^2+3^2+...+(2n+1)^{2} = \frac{(n+1)(2n+1)(2n+3)}{3}$ for nonnegative $n$.
\end{enumerate}

\item Now, prove the following: $3\mid 2^{2n}-1$ for $n\geq1$.
\begin{enumerate}
\item Base case is $n$ = 1. So $P(1)$ = $3\mid 2^{2(1)}-1$.
\item Well clearly $2^{2(1)}-1 = 4-1 = 3$. And it is obvious that $3\mid3$, so the base case is proven.
\item What is our inductive hypothesis? $P(k)$ so $3\mid 2^{2k}-1$.
\item We want to prove that $3\mid 2^{2k+2}-1$.
\item Well, $P(k+1) = 3\mid2^{2k+2}-1$. We also can see $2^{2k+2}-1 = 4*2^{k}-1 = 4*(2^{k}-1+1)-1$.
\item  But we know, by our inductive hypothesis that this equals $4*(3t+1)-1 = 12t+4-1 = 12t+3 = 3(4t+1)$.
\item Clearly this is divisible by 3, therefore $P(k+1) = 3\mid 2^{2k+2}-1$ is true.
\end{enumerate}
\end{itemize}

\end{document}