\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{}

\begin{document}
\maketitle

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


\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}

\item A strong induction proof.\\
\begin{center}
Show that if $n\in \mathbb{N}$ then $12\mid (n^4 - n^2)$.
\end{center}
\begin{enumerate}
\item \textbf{Base Case:}
\begin{enumerate}
\item $n$ = 1: $1^4-1^2 = 0 = 12*0$ so $P(1)$ is true.
\item $n = 2: 2^4 - 2^2 = 16 - 4 = 12 = 12*1$ so $P(2)$ is true.
\item $n = 3: 3^4 - 3^2 = 81 - 9 = 72 = 12*6$ so $P(3)$ is true.
\item $n = 4: 4^4 - 4^2 = 256 - 16 = 240 = 12*20$ so $P(4)$ is true.
\item $n = 5: 5^4 - 5^2 = 625 - 25 = 600 = 12*50$ so $P(5)$ is true.
\item $n = 6: 6^4 - 6 ^2 = 1296 - 36 = 1260 = 12 * 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 \leq k$ where $m\in \mathbb{N}$.
\item Let $i = k-5$, then we can assume $P(i)$ holds. Clearly $i+6 = k+1$.
\item $(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$
\item Clearly $i^4-i^2 = 12*t$.
\item We can also see that the remaining portion can be rewritten as $12(2i^3 + 15i^2+71i+105)$.
\item Then we have that $(k+1)^4-(k+1)^2 = 12t + 12(2i^3 + 15i^2+71i+105) = 12*(t+2i^3 + 15i^2+71i+105)$
\item Then we have that $12\mid (k+1)^4-(k+1)^2$.
\end{enumerate}
\end{itemize}

\end{document}