\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amssymb,amsfonts,amsmath,amsthm} 
\usepackage[margin= 1in]{geometry}
\usepackage{url}
\usepackage{halloweenmath}
\usepackage{enumerate}
\usepackage{color}
\usepackage[pdftex]{graphicx}
\usepackage{lastpage}
\usepackage{mathptmx}

\newtheorem{thm}{THEOREM}[]
\newtheorem{lem}[thm]{LEMMA}
\newtheorem{cor}[thm]{COROLLARY}
\newtheorem{prop}[thm]{PROPOSITION}
\newtheorem{as}[thm]{ASSUMPTION}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{claim}[thm]{CLAIM}
\theoremstyle{definition}
\newtheorem{defi}[]{DEFINITION}
\theoremstyle{definition}
\newtheorem{remark}[thm]{REMARK}
\newtheorem{fact}[thm]{Fact}
\newtheorem{ex}[thm]{Example}

\setlength{\parindent}{0cm}

\newcommand{\tab}{\hspace{3ex}}
\newcommand{\R}{\mathbb{R}}

\usepackage{titlesec}
\usepackage{sectsty}
\hyphenchar\font=-1

\sectionfont{  \normalsize	\sectionrule{0pt}{0pt}{-5pt}{0.05pt}
	}

\titleformat*{\section}{ \Large  \center}
\titleformat{\subsection}[runin]
               {\normalfont\bfseries }
               {}{0em}{}[.]
               
\titlespacing{\section}
               {\parindent}{0pt}{5pt}
\titlespacing{\subsection}
               {0pt}{2ex plus .1ex minus .2ex}{5pt} 

               \makeatletter
 \renewcommand{\@evenfoot}{%
   Page \thepage{} of \pageref{VeryLastPage} \hfil
    
 }
 \renewcommand{\@oddfoot}{\@evenfoot}
 \makeatother

\begin{document}

\begin{center}
{\huge  \sc   Worksheet 8} \\
\smallskip
{ Date: 10/20/2021}\\
\smallskip
{Name:  }\\
{\large  }
\end{center}

\begin{center}
    
    {\Huge Induction and its Sisters}
\end{center}
\begin{remark}[The First Principle of mathematical induction] Suppose that for each positive integer $n$ we have a statement $P(n)$. If we prove the following two things
\begin{enumerate}
    \item  $P(1)$ is true;
    \item for all $n$, if $P(n)$ is true then $P(n+1)$ is also true;\newline 
    then $P(n)$ is true for all positive integers $n$. 
\end{enumerate}
\end{remark}
\vspace{1cm}
\begin{remark}[The Second Principle of mathematical induction] Let $k$ be an integer. Suppose that for each integer $n\geq k$ we have a statement $P(n)$. If we prove the following two things
\begin{enumerate}
    \item  $P(k)$ is true;
    \item for all $n\geq k$, if $P(n)$ is true then $P(n+1)$ is also true;\newline 
    then $P(n)$ is true for all positive integers $n\geq k$. 
\end{enumerate}
\end{remark}

\vspace{1cm}

\begin{remark}[The Strong Form of Induction] Suppose that for each integer $n\geq k$ we have statement $P(n)$. If we prove the following two things:
\begin{enumerate}
    \item  $P(k)$ is true; and
    \item for all $k\leq n$, if  $P(k), P(k+1),\ldots P(n)$ are all true,  then $P(n+1)$ is true;\newline 
    then $P(n)$ is true for all $n\geq k$. 

\end{enumerate}
\end{remark}

\vspace{1cm}

What is the distinction of the first principle of mathematical induction, the second principle of mathematical induction and strong induction? (You should be able to answer this question in Wednesday's section.)
 
  \newpage
  
\begin{center}
    
   {\Huge Getting Our Hand's Dirty}
   
   \end{center}
   \vspace{1cm}
   
   Please partition your self's into give groups. \textcolor{red}{One of your group members must know \LaTeX. You will submit your proof to me and I will post it online for your peers to view. }   You can name your group whatever you want, or choose from the following list: Chelsea FC, Dodger Nation, Raider Nation, Chivas, or Team U.S.A. If you choose a team name, it must be appropriate. I will give the approval in section. Write the answers to each question before you start the proof.

   \begin{itemize}
   
 \item What principle of induction are you going to use? Why did you choose this particular induction?
   \vspace{2cm}
       \item What is your induction hypothesis?
       \vspace{4cm}
       \item What are you trying to prove?
       \vspace{4cm}
       \item Give a short paragraph of the strategy regarding your proof. 

   \end{itemize}
   \newpage 

   
   \begin{enumerate}

  

  

        \item Prove that for every nonnegative integer $n$, $(4^{3n}-1)$ is a multiple of 9.
        
        Hint: Use induction.
        
        \vspace{.5cm}
        
        \textit{Proof:}
        
        \vspace{18cm}
        \hspace{16cm} $\mathwitch$

       \newpage

 \item Example: If $\{x_n\}$ is a sequence defined recursively by $x_1=1,x_2=3,$ and $x_n=2x_{n-1}-x_{n-2}$ for $n\geq 3$, then $x_n=2n-1$ for all natural numbers $n$.
 
   \textit{Proof:}
        
        \vspace{18cm}
        \hspace{16cm} $\mathwitch$

\newpage 

\item Define a sequence $\{x_n\}$ recursively by $x_1=1, x_2=4, $ and $x_n=2x_{n-1}-x_{n-2}+2$ for $n\geq 3$. Conjecture a formula for $x_n$ and verify that your conjecture is correct. i.e prove the formula holds by induction. 

  \textit{Proof:}
        
        \vspace{15cm}
        \hspace{16cm} $\mathwitch$
\newpage 

\item 
First, we define $\sum=\bigpumpkin$. Prove that 
\[
\bigpumpkin_{k=1}^n\frac{1}{k^2}<2.
\]
Hint: Prove the stronger statement that the left hand side is less than $2-\frac{1}{n}$.

  \textit{Proof:}
        
        \vspace{15cm}
        \hspace{16cm} $\mathwitch$  
\newpage

\item Assume $n$ is a non negative integer. Prove $3|(n^3-n)$.
\vspace{.25cm}
\newline (Hint: Just because induction is a choice doesn't always mean it is the easiest choice. Note that $n^3-n$ factors to $(n-1)n(n+1)$. So, if you show that the product of three consecutive integers is a multiple of 3 then the statement above is proven. If you approach the problem this way you will need the following lemma: If $3|a$ and $k\in\mathbb{Z}$ then $3|ak$. )

  \textit{Proof:}
        
        \vspace{15cm}
        \hspace{16cm} $\mathwitch$

\end{enumerate}

  

\label{VeryLastPage}
\end{document}