\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

\title{Recitation 10}
\author{Created by Taylor Spangler, Adapted by Beau Christ}
\date{\today}

\begin{document}
\maketitle

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


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

\item Problem 5.1.5: Using induction, prove:
\[\forall n \geq 0\; 1^2+3^2+\ldots +(2n+1)^{2} = \frac{(n+1)(2n+1)(2n+3)}{3}\]
We prove the property using mathematical induction:
\begin{enumerate}
\item Let's state the property to prove:
\[ P(n): 1^2+3^2+\ldots +(2n+1)^{2} = \frac{(n+1)(2n+1)(2n+3)}{3}\]
\item We take $n_0 =0$ and prove $P(0)$:
\[P(0) = 1 = \frac{(1)(1)(3)}{3}\]
We show that P(0) holds: 1 = 1.$ \frac{1\cdot 1\cdot 3}{3} = 1$. Therefore, P(0) is true.
\item What is the inductive hypothesis? 
\[P(k): 1^2+ 3^2+\ldots +(2k+1)^{2} = \frac{(k+1)(2k+1)(2k+3)}{3}\]
\item Assuming the base case and the inductive hypothesis, we want to prove: 
\[P(k+1): 1^2+ 3^2+\ldots +(2k+3)^{2} = \frac{(k+2)(2k+3)(2k+5)}{3}\]
\item We start from $1^2+ 3^2+\ldots +(2k+1)^2+(2k+3)^2$.\\
$1^2+ 3^2+\ldots +(2k+1)^2+(2k+3)^2$ \\
= $(1^2+ 3^2+\ldots +(2k+1)^2)+ (2k+3)^2$  \\
= $\frac{(k+1)(2k+1)(2k+3)}{3} + (2k+3)^2$  \hfill{\em using the inductive hypothesis}\\
= $(2k+3)\cdot(\frac{(k+1)(2k+1)+6k+9}{3})$ \\
= $(2k+3)\cdot(\frac{2k^2+9k+10}{3})$ \\
= $\frac{(k+2)(2k+3)(2k+5)}{3}$ \\
Thus, $P(k+1)$ holds.
\end{enumerate}
Consequently, by the PMI, $\forall n \geq 0\; 1^2+3^2+\ldots +(2n+1)^{2} = \frac{(n+1)(2n+1)(2n+3)}{3}$

\item Now, prove the following: $3\mid 2^{2n}-1$ for $n\geq1$.
\begin{enumerate}
\item First, we state the property to prove: $P(n): 3\mid 2^{2n}-1$.
\item Base case is $n_0$ = 1. So $P(1)$ = $3\mid 2^{2(1)}-1$.
Clearly, $2^{2(1)}-1 = 4-1 = 3$, $3\mid3$, which is obvious.  So, $P(1)$ holds.
\item Next, we state the inductive hypothesis: $P(k): 3\mid 2^{2k}-1$ and assume that $P(k)$ holds.
\item Now, we have to prove that $ P(k+1): 3\mid 2^{2k+2}-1$ holds.  We start from $2^{2k+2}-1$.\\
$2^{2k+2}-1 = 4\cdot 2^{k}-1 = 4 \cdot (2^{k}-1+1)-1$. \\
The inductive hypothesis gives that $3\mid 2^{2k}-1$ This, there is an integer $t$ such that 
$2^{2k}-1 = 3t$.  Thus,\\
$2^{2k+2}-1 = 4 \cdot (3t+1) - 1 = 12t + 4 - 1 = 12t+3= 3\cdot(4t+1)$.\\
Thus, $2^{2k+2}-1$ is a multiple of 3.  Hence, $P(k+1)$ holds.
\end{enumerate}
Consequently, by the PMI, $\forall n\geq 1,\; 3\mid 2^{2n}-1$.


\item A proof by strong induction.
\begin{center}
Show that $\forall n\in \mathbb{N},\; 12\mid (n^4 - n^2)$.
\end{center}
\begin{enumerate}
\item  First, we state the property:
\[P(n): 12\mid (n^4 - n^2)\]
\item \textbf{Base Case:}
\begin{enumerate}
\item For $n= 1$: $1^4-1^2 = 0 = 12\cdot 0$, so $P(1)$ is true.
\item For $n=2$: $2^4 - 2^2 = 16 - 4 = 12 = 12\cdot 1$, so $P(2)$ is true.
\item For $n= 3$: $3^4 - 3^2 = 81 - 9 = 72 = 12\cdot 6$, so $P(3)$ is true.
\item For $n= 4$: $4^4 - 4^2 = 256 - 16 = 240 = 12\cdot 20$, so $P(4)$ is true.
\item For $n= 5$: $5^4 - 5^2 = 625 - 25 = 600 = 12\cdot 50$, so $P(5)$ is true.
\item For $n= 6$: $6^4 - 6 ^2 = 1296 - 36 = 1260 = 12 \cdot  105$, so $P(6)$ is true.
\end{enumerate}
\item \textbf{Strong Inductive Hypothesis} Let $k \geq 6 \in \mathbb{N}$ and assume that $12\mid (m^4 - m^2)$ for $1\leq m < k$ where $m\in \mathbb{N}$.
\item We need to estalish $P(k)$.\\
 Let $i = k-5$.  Because $i<k$, we can assume that $P(i)$ holds. \\
Clearly $i+6 = k+1$.\\
$(i+6)^4 - (i+6)^2$\\
$= (i^4 + 24i^3+180i^2 + 864i + 1296) - (i^2 +12i + 36)$\\
$= (i^4-i^2) + 24i^3+180i^2 + 852i+1260$\\
Because $P(i)$ holds, we have  $i^4-i^2 = 12\cdot t$.\\
Further, $ 24i^3+180i^2 + 852i+1260 = 12(2i^3 + 15i^2+71i+105)$.\\
Thus, $(i+6)^4 - (i+6)^2 = 12\cdot t + 12(2i^3 + 15i^2+71i+105) = 12 (t + 2i^3 + 15i^2+71i+105)$.\\
Hence, $(i+6)^4 - (i+6)^2$ is a multiple of 12 and $12\mid (k+1)^4-(k+1)^2$.
\end{enumerate}
\end{itemize}
We can finally state that by the principle of strong induction, $\forall n\in \mathbb{N},\; 12\mid (n^4 - n^2)$.

\end{document}
