\documentclass[11pt]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{amsfonts, amscd, amssymb, amsthm, amsmath}
\usepackage{pdfsync}%leaves makers for tex searching
\usepackage{enumerate}

%%%%% Margins %%%%% 
\setlength{\topmargin}{1in} %top/bot margins
\setlength{\oddsidemargin}{\topmargin} %sidemargins

\setlength{\textheight}{11in} \setlength{\textwidth}{8.5in}
\setlength{\hoffset}{-1in} \setlength{\voffset}{-1in} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\textheight}{-2 \topmargin}\addtolength{\textwidth}{-2\oddsidemargin}
\setlength{\headheight}{0pt} \setlength{\headsep}{20pt} \setlength{\footskip}{20pt}
\addtolength{\textheight}{-\footskip} \addtolength{\textheight}{-\headheight} \addtolength{\textheight}{-\headsep}



%%%%% Theorems %%%%% 
\theoremstyle{plain}
	\newtheorem{thm}{Theorem}
	\newtheorem*{thm*}{Theorem}
	\newtheorem{lemma}[thm]{Lemma}
	\newtheorem{prop}[thm]{Proposition}
	\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
	\newtheorem*{defn}{Definition}
	\newtheorem{remark}[thm]{Remark}
\theoremstyle{example}
	\newtheorem*{example}{Example}


%%%%% Pictures %%%%% 
%\usepackage{etex} %fixes the fight that pictex has with every other drawing package
%\usepackage{pictexwd}
\usepackage{tikz}
%\usepackage{graphicx}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\usepackage[pdftex,bookmarks]{hyperref}

\usepgflibrary{shapes.geometric}
\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=1.5pt]
\tikzstyle{over}=[draw=white,double=black,line width=2pt, double distance=.5pt]


\newcommand\TikZ[1]{\begin{matrix}\begin{tikzpicture}#1\end{tikzpicture}\end{matrix}}


%PARTITIONS
\newcounter{r}
\newcommand\Part[1]{
        \setcounter{r}{1}
	 \foreach \x in {#1}{
 	{\ifnum\value{r}=1
		\draw (0,\value{r}-1)--(\x,\value{r}-1); 
		\fi}
	\draw (0,\value{r}) to (\x,\value{r});
   	\foreach \y in {0, ..., \x} {\draw (\y,\value{r})--(\y,\value{r}-1);}
	\addtocounter{r}{1}
 }}
 \def\PartUNIT{.175}
%Self-contained tikz images for \Part above. 
\newcommand{\PART}[1]{
\begin{matrix}
\begin{tikzpicture}[xscale=\PartUNIT, yscale=-\PartUNIT] 
	\Part{#1}
\end{tikzpicture}
\end{matrix}
}


%BRAIDS:
\def\Over[#1,#2][#3,#4]{ %1,2=start position; 3,4=end position
	\draw[style=over]   (#1,#2) .. controls ++(0,#4*.5-#2*.5) and ++(0,-#4*.5+#2*.5) .. (#3,#4);}
\def\Under[#1,#2][#3,#4]{ %1,2=start position; 3,4=end position
	\draw  (#1,#2) .. controls ++(0,#4*.5-#2*.5) and ++(0,-#4*.5+#2*.5) .. (#3,#4);}
\def\Cross[#1,#2][#3,#4]{%Mimic over, under follows
	\Under[#3,#2][#1,#4]\Over[#1,#2][#3,#4]}
\def\Tops[#1][#2][#3]{%1=pole locations, 2=top, 3=k 
	\foreach\x in {#1}{
		\draw (\x+.1,#2) -- (\x+.1,#2+.15) (\x-.1,#2) -- (\x-.1,#2+.15) ;
		\draw (\x+.1,#2+.15) arc (0:360:1mm and .5mm);}
	%Nodes 
	\foreach \x in {1,...,#3} {\draw (\x,#2)  to (\x,#2+.05) node[V]{};}
	}
\def\Bottoms[#1][#2][#3]{%1=pole locations, 2 = bottom, 3=top 
	\foreach\x in {#1}{
		\draw (\x+.1,#2) -- (\x+.1,#2-.1) (\x-.1,#2) -- (\x-.1,#2-.1) ;
		\draw (\x+.1,#2-.1) arc (0:-180:1mm and .5mm);}
	%Nodes 
	\foreach \x in {1,...,#3} {\draw (\x,#2)  to (\x,#2-.05) node[V]{};}
	}
\def\Caps[#1][#2,#3][#4]{%1=pole locations, 2 = bottom, 3=top, 4=k 
	\Tops[#1][#3][#4]
	\Bottoms[#1][#2][#4]
	}
\def\Pole[#1][#2,#3]{%1=horizontal location, 2 = bottom, 3=top
	\shade[left color=white,right color=white] (#1+.1,#2) rectangle (#1-.1,#3);
	\draw[over] (#1+.1,#2) to (#1+.1,#3) (#1-.1,#2) to (#1-.1,#3) ;}
\def\Label[#1,#2][#3][#4]{%1,2 = top/bot position, 3=i, 4=label
	\node[above] at (#3,#2+.1) {#4};
	\node[below] at (#3,#1-.1) {#4};		}
	
	
%%%%% Color  %%%%% 
\usepackage{color}
\definecolor{dred}{rgb}{.65, 0, 0.15}
\newcommand{\NOTE}[1]{{\color{blue}#1}}
\newcommand{\MOVED}[1]{{\color{gray}#1}}
\newcommand{\blue}[1]{{\color{blue} #1 }}


%%%%% Alphabets %%%%% 
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  

\def\fa{\mathfrak{a}} \def\fb{\mathfrak{b}} \def\fc{\mathfrak{c}} \def\fd{\mathfrak{d}} \def\fe{\mathfrak{e}} \def\ff{\mathfrak{f}} \def\fg{\mathfrak{g}} \def\fh{\mathfrak{h}} \def\fj{\mathfrak{j}} \def\fk{\mathfrak{k}} \def\fl{\mathfrak{l}} \def\fm{\mathfrak{m}} \def\fn{\mathfrak{n}} \def\fo{\mathfrak{o}} \def\fp{\mathfrak{p}} \def\fq{\mathfrak{q}} \def\fr{\mathfrak{r}} \def\fs{\mathfrak{s}} \def\ft{\mathfrak{t}} \def\fu{\mathfrak{u}} \def\fv{\mathfrak{v}} \def\fw{\mathfrak{w}} \def\fx{\mathfrak{x}} \def\fy{\mathfrak{y}} \def\fz{\mathfrak{z}}
\def\fgl{\mathfrak{gl}}  \def\fsl{\mathfrak{sl}}  \def\fso{\mathfrak{so}}  \def\fsp{\mathfrak{sp}}  
\def\GL{\mathrm{GL}} \def\SL{\mathrm{SL}}  \def\SP{\mathrm{SL}}

\def\<{\langle} \def\>{\rangle}
\def\ad{\mathrm{ad}} 
\def\Alg{\mathrm{Alg}}
\def\Aut{\mathrm{Aut}}
\def\dim{\mathrm{dim}} 
\def\End{\mathrm{End}} 
\def\ev{\mathrm{ev}} 
\def\half{\hbox{$\frac12$}}
\def\Hom{\mathrm{Hom}} 
\def\id{\mathrm{id}}
\def\img{\mathrm{img}}
\def\Ind{\mathrm{Ind}}
\def\Irr{\mathrm{Irr}} 
\def\ker{\mathrm{ker}}
\def\Lie{\mathrm{Lie}}
\def\normeq{\unlhd}
\def\qtr{\mathrm{qtr}} 
\def\rad{\mathrm{rad}} 
\def\Res{\mathrm{Res}} 
\def\tr{\mathrm{tr}} 
\def\Tr{\mathrm{Tr}} 
\def\vep{\varepsilon}
\def\wt{\mathrm{wt}}
\pagestyle{empty}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Proof Lab II: Induction}
\author{}
\begin{document}


\maketitle

\noindent{\textbf{Instructions:}}

\smallskip

\begin{center}
\fbox{
  \begin{minipage}{15cm}

\noindent \textbf{Step 1 (Today).} \\
Work together with your group to outline the full set of exercises.\\

\noindent \textbf{Step 2 (This weekend and next week).} \\
Each person: pick 8 $ \star$'s worth of exercises, and write up careful drafts of the proofs. Include key definitions and thorough reasoning---think about writing to convince a student taking Bridge next semester. Make sure a novice could follow and locate all critical components of the proof. \textbf{See portfolio guidelines for further instruction.}\\

\noindent \textbf{Step 3 (11/8 $\pm$ 2 days).} \\
Swap drafts with a peer editor and give/get feedback. (Get a peer's email address and sending them a pdf before class on Thursday.)\\

\noindent Provide written constructive criticism for your partner: Are key definitions included? Is the reasoning mathematically accurate? Are the key components of the proof easy to recognize? Is the notation clear? Would a few additional comments help a novice reader to follow more easily? Can the explanation be made more clean and concise?\\

\noindent \textbf{Step 4 (Thursday 11/15).} \\ 
Turn in your proof second drafts, and comments from at least one peer editor on first drafts. (You will provide two versions of each proof--one first draft with comments, and one rewritten draft. Homework without peer editor comments will not be accepted.)
\end{minipage}}
\end{center}

\vfill

\noindent 
\textbf{Outlining your proof:}
\begin{enumerate}[1.]
\item Define $P(n)$.\\
\emph{\small Rewrite the claim in the best way for you to use induction.}
\item Compute base case(s).\\
\emph{\small Usually $P(0)$ or $P(1)$. You might have to do more than one base case to get the induction step to work.} 
\item Explicitly state your goal.\\
\emph{\small ``Assume $P(n)$ and prove $P(n+1)$, which is\dots''}
\item Do inductive step.\\
\emph{\small This is usually where the real work happens.}
\item State your conclusion.
\end{enumerate} 


\bigskip

\noindent \textbf{Rewrite your proof:} Your final draft should read something like\\
``We will prove this claim by induction on $n$. First, for $n=\NOTE{a}$,\footnote{where $a$ is something like $0$ or $1$ or $5$---whatever the lower end of the domain of the problem is.} we have \NOTE{[COMPUTATION]}. 
Next, fix $n \ge \NOTE{a}$ and assume \NOTE{[STATE THE CLAIM]} for that value of $n$. Then \NOTE{[USE THAT ASSUMPTION TO SHOW CLAIM FOR $n+1$]}\footnote[7]{Don't forget to point out where you use the ``Induction Hypothesis''.}. Thus, by induction, the claim holds for all $n \ge \NOTE{a}$.''




\thispagestyle{empty}

\pagebreak

\noindent{\bf Problems. } Prove each of the following using proof by induction. Assume throughout that $n$ is an integer. 

\vfill

\begin{enumerate}[I.]
\item ($\star$)  If $x_1,x_2,...,x_n$ are odd integers, then their product,
\[ \prod_{i=1}^n x_i \qquad \text{is also odd.}
\]
{[Note that $x_1,x_2,...,x_n$ is an arbitrary list of odd numbers (you don't get to choose what these numbers are!).]}


\vfill

%\item For all $n \ge 1$, we have  $3^{2n} - 1$ is divisible by 8.
%
%
%\vfill

\item ($\star$) For all odd natural numbers $n$, $n^2 - 1$ is divisible by 8.\\
{[Warning: \underline{Do not induct on $n$}. Instead, start by writing what it means for $n$ to be odd.]}

\vfill


\item ($\star\star$) For all $n \ge 1$ and $0 \le x \le \pi$, we have $\sin(nx) \le n\sin(x)$. \\
{[You may use the angle addition formula for $\sin(x)$.]}

\vfill



\item  ($\star\star$) Let $a_n = 2^{2^n}+1$. Then for all $n \ge 2$, the last digit of $a_n$ is 7. \footnote[2]{Fermat conjectured that for $n \ge 1$, $a_n$ is always prime. 
Indeed, $a_1=5, a_2=17, a_3=257, a_4=65,537$ are all prime. However, the conjecture fails for many large values of $n$ (Fermat had a hard time checking because $a_i$ gets really large quickly).}
\\
{[Hint: Rephrase ``last digit is $7$'' in terms of remainders.]}

\vfill

\item ($\star\star\star$) The \emph{Fibonacci Numbers} $F_1, F_2, \dots,$ are defined by the recursive rule
$$F_1=1 \quad F_2 = 1 \quad \text{ and } \quad F_{n+1}=F_n+F_{n-1} \text{ for all $n \ge 3$}.$$
For all $n \ge 1$, $F_{5n}$ is divisible by $5$.\\
{[Hint: For the induction step, let $r$ be the remainder of $F_{5n-1}$ when divided by 5.]}


\vfill

\item ($\star\star\star$) If $u$ and $v$ are differentiable functions of $x$, then 
$$\frac{d^n}{dx^n}  uv = \sum_{k = 0}^n \binom{n}{k} u_k v_{n-k},$$
where $u_i = \frac{d^i}{dx^i}  u$ and $v_i = \frac{d^i}{dx^i}  v$.\\
{[You will need to prove a lemma that shows $\binom{r}{s} + \binom{r}{s+1} = \binom{r+1}{s+1}$ for all $r,s \in \ZZ_{\ge 0}$, to be proven directly.]}

\vfill


\end{enumerate}
\end{document}
