\documentclass{slides}

\setlength{\oddsidemargin}{-.5in}
\setlength{\topmargin}{-1in}
\setlength{\textheight}{7 in}
\setlength{\textwidth}{8.9 in}

\begin{document}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (P(n))$ \\
1. (Base) $P(0)$ 
\> \> \> \> \> There's exactly one empty \\
\> \> \> \> \> \quad string of $0$s and $1$s. \\
2. (Inductive step) $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $P(n)$, that is, there are $2^n$ length $n$ strings. \\
\> 3. $P(n+1)$, that is, there are $2^{n+1}$ length $n+1$ strings. \\
\> \> \> \> \> Every string of length $n$ can \\
\> \> \> \> \> \quad have either a $0$ or a $1$  \\
\> \> \> \> \> \quad attached at the end. \\
\> 4. QED   
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (P(n))$ \\
1. (Base) $P(0)$ \\
2. (Inductive step) 
$\forall n \geq 0 [(\forall i, 0 \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq k (P(n))$ \\
1. (Base) $P(k)$ \\
2. (Inductive step) 
$\forall n \geq k [(\forall i, k \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 12 (P(n))$ \\
1. (Base) $P(12)$ 
\> \> \> \> \> Use 3+3+3+3 \\
2. (Inductive step) 
$\forall n \geq 12 
   [(\forall i, 12 \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
2. (Inductive step) 
$\forall n \geq 12 
   [(\forall i, 12 \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 12$. \\
\> 2. $(\forall i, 12 \leq i \leq n (P(n))) \Rightarrow P(n+1)$ \\
\> \> 1. Assume $\forall i, 12 \leq i \leq n (P(n)$ \\
\> \> 2. $P(n+1))$ \\ 
\> \> \> 1. $n = 12 \Rightarrow P(n+1)$ 
         \> \> Use 7+3+3 \\
\> \> \> 2. $n = 13 \Rightarrow P(n+1)$ 
         \> \> Use 7+7 \\
\> \> \> 3. $n \geq 14 \Rightarrow P(n+1)$ 
         \> \> ??? \\
\> \> \> 4. QED
         \> \> Cases \\
\> \> 3. QED 
      \> \> \> Implication \\
\> 3. QED
   \> \> \> \> UG
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=\=\=XXX\=XXXXXXXXXXXXXXXX\=    \kill
\> \> \> 3. $n \geq 14 \Rightarrow P(n+1)$ \\
\> \> \> \> 1. Assume $n \geq 14$. \\
\> \> \> \> 2. $P(n-2)$
            \> Ind.\ hyp.\ 2.2.1 with \\
\> \> \> \> \> \quad $n-2 \geq 12$ \\
\> \> \> \> 3. $P(n+1)$
            \> Add one block to the tower from \\
\> \> \> \> \> \quad the previous step. \\
\> \> \> \> 4. QED
            \> Implication
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXX\=    \kill
Prove: $\forall n \geq 12 (P(n))$ \\
1. (Base) $P(12)$ \\
2. (Base) $P(13)$ \\
3. (Base) $P(14)$ \\
4. (Inductive step) $\forall n \geq 14
   [(\forall i, 12 \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Very specialized strong induction
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (P(n))$ \\
1. (Base) $P(0)$ 
\> \> \> \> \> $F_0 = 0$, which is even. \\
2. (Inductive step) 
$\forall n \geq 0 [(\forall i, 0 \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
\> \> \> \> \> ??? \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 2 (P(n))$\\
1. (Base) $P(2)$
\> \> \> \> \>  $F_2 = 1 = (\frac{3}{2})^0$ \\
2. (Base) $P(3)$ 
\> \> \> \> \>  $F_3 = 2 \geq (\frac{3}{2})^1$ \\
3. (Inductive step) $\forall n \geq 3 [(\forall  i, 2 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$\\
\> 1. Fix $n \geq 3$ \\
\> 2. Assume $\forall  i, 2 \leq i \leq n (P(i))$ \\
\> 3. $P(n+1)$
   \> \> \> \> ??? \\
\> 4. QED
    \> \> \> \> Implication, UG \\
4. QED
\> \> \> \> \> Strong induction
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 3. $P(n+1)$ \\
\> \> 1. $F_n \geq (\frac{3}{2})^{n-2}$
      \> \> \> Inductive hyp.\ 3.2 \\
\> \> 2. $F_{n-1} \geq (\frac{3}{2})^{n-3}$
      \> \> \> Inductive hyp.\ 3.2 \\
\> \> 3. $F_{n+1} = F_n + F_{n-1}$
      \> \> \> Definition \\
\> \> 4. $F_{n+1}\geq (\frac{3}{2})^{n-2} + (\frac{3}{2})^{n-3}$ 
      \> \> \> Plug inequalities \\
\> \> \> \> \> \quad into equation \\
\> \> 5. QED
      \> \> \> Algebra \\
\> \> \> 1. $\frac{3}{2} + 1 \geq (\frac{3}{2})^2$
         \> \> Arithmetic \\
\> \> \> 2. $(\frac{3}{2})^{n-2} + (\frac{3}{2})^{n-3} \geq (\frac{3}{2})^{n-1}$
         \> \> Algebra \\
\> \> \> 3. $F_{n+1} \geq (\frac{3}{2})^{n-1}$
         \> \> 3.3.4 and 3.3.5.2 \\
\> \> \> 4. QED
         \> \> Def.\ of $P(n+1)$ 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove:  $\forall n \geq 2 (P(n))$ \\
1. $P(2)$
\> \> \> \> \> Use $2$ itself \\
2. $\forall n \geq 2 [(\forall i, 2 \leq i \leq n) (P(i)) \Rightarrow P(n)]$ \\
\> 1. Fix $n \geq 2$ \\
\> 2. Assume $\forall i, 2 \leq i \leq n(P(i))$, that is, all numbers up to \\
\> \qquad and including $n$ can be factored into primes \\
\> 3. $P(n+1)$, that is, $n+1$ can be factored into primes. \\
\>  \> \> \> \> ??? \\
\> 4. QED
     \> \> \> \> Implication, UG \\
3. QED
    \> \> \> \> Strong induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXX\=    \kill
\> 3. $P(n+1)$, that is, $n+1$ can be factored into primes. \\
\> \> 1. If $n + 1$ is prime, then $n+1$ can be factored into primes. \\

\> \> \> \> \> Use $n+1$ itself \\
\> \> 2. If $n+1$ is not prime, then $n+1$ can be factored into primes.
\\
\> \> \> 1. Assume $n+1$ is not prime. \\
\> \> \> 2. $n+1$ can be written as $a \times b$, where $1 < a, b < n+1$
\\
\> \> \> \> \> Def.\ of ``prime'' \\
\> \> \> 3. $a$ can be factored into primes. 
      \> \> Strong ind.\ hyp.\ (2.2) \\
\> \> \> 4. $b$ can be factored into primes. 
         \> \> Strong ind.\ hyp.\ (2.2) \\
\> \> \> 5. $n+1$ can be factored into primes. \\
\> \> \> \> \> Use factors of $a$ and $b$.  \\
\> \> \> 6. QED
            \> \> Implication \\
\> \> 3. QED
        \> \> \> Cases
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 3 (P(n))$ \\
1. (Base) $P(3)$ 
\> \> \> \> \> Trivial by assumption. \\
2. (Inductive step)  $\forall n \geq 3 (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 3$ \\
\> 2. Assume $P(n)$ \\
\> 3. $P(n+1)$ \\
\> \> 1. Fix $T$, a tournament, and $p_1 \rightarrow p_2 \rightarrow \ldots
\rightarrow p_{n+1} \rightarrow p_1$, \\
\> \> \qquad an $n+1$-cycle in $T$. \\
\> \> 2. $T$ contains a $3$-cycle. 
      \> \> \> ??? \\
\> \> 3. QED
      \> \> \> Implication, UG \\
\> 4. QED
   \> \> \> \> Implication, UG \\
3. QED
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXX\=    \kill
\> \> 2. $T$ contains a $3$-cycle. \\
\> \> \> 1. If $p_3 \rightarrow p_1$ then $T$ contains a $3$-cycle. \\
\> \> \> \> \> Use $p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_1$. \\
\> \> \> 2. If $p_1 \rightarrow p_3$ then $T$ contains a $3$-cycle. \\
\> \> \> \> 1. Assume $p_1 \rightarrow p_3$. \\
\> \> \> \> 2. $T$ contains an $n$-cycle. \\
\> \> \> \> \> Use $p_1 \rightarrow p_3 \rightarrow p_4 \rightarrow p_{n+1} \rightarrow p_1$. \\
\> \> \> \> 3. $T$ contains a $3$ cycle. \\
\> \> \> \> \> Inductive hypothesis (2.2) \\
\> \> \> 3. QED
         \> \> Cases
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 (P(n))$ \\
1. (Base) $P(1)$ 
\> \> \> \> \> Obvious \\
2. (Inductive step)
$\forall n \geq 1 [(\forall i, 1 \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 1$ \\
\> 2. Assume $\forall i, 1 \leq i \leq n (P(i))$. \\
\> 3. $P(n+1)$ \\
\> \> 1. Fix any $n+1$-player tournament $T$. \\
\> \> 2. $T$ has a locally fair ranking. \\
\> \> \> 1. Choose $x$ to be any player, \\
\> \> \> \> $B$ the set of players that beat $x$, and \\
\> \> \> \> $L$ the set of players that lose to $x$. \\
\> \> \> 2. $B$ has a locally fair ranking. 
         \> \> Ind.\ hyp.\ (2.2). \\
\> \> \> 3. $L$ has a locally fair ranking. 
         \> \> Ind.\ hyp.\ (2.2). \\
\> \> \> 4. Define a ranking $R$ of all the players by: \\
\> \> \> \> $B$ ranking, then $x$, then $L$ ranking. \\
\> \> \> 5. $R$ is a locally fair ranking for $T$. \\
\> \> \> 6. QED 
         \> \> EG \\
\> \> 3. QED 
      \> \> \> UG \\
\> 4. QED
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 (P(n))$ \\
1. (Base) $P(1)$ 
\> \> \> \> \> Only one possibility. \\
2. (Inductive step) $\forall n \geq 1 [P(n) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 1$. \\
\> 2. Assume $P(n)$. \\
\> 3. $P(n+1)$. \\
\> \> 1. Fix $T$, an $n+1$-player tournament, \\
\> \> \> and $z$, a player with the most wins. \\
\> \> 2. $\exists$ a locally fair ranking of $T$ with $z$ first. 
      \> \> \> ??? \\
\> \> 3. QED 
      \> \> \> UG \\
\> 4. QED   
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $\exists$ a locally fair ranking of $T$ with $z$ first. \\
\> \> \> 1. If $z$ is undefeated in $T$ then $\exists$ a locally fair \\
\> \> \> \qquad ranking of $T$ with $z$ first. \\
\> \> \> \> 1. Assume $z$ is undefeated in $T$. \\
\> \> \> \> 2. Choose $R$ to be a locally fair ranking of all-but-$z$. \\
\> \> \> \> \> Prev.\ thm and EI \\
\> \> \> \> 3. $z$ then $R$ is a locally fair ranking of $T$. \\
\> \> \> \> 4. $\exists$ a locally fair ranking of $T$ with $z$ first. \\
\> \> \> \> \> EG \\
\> \> \> \> 5. QED 
            \> Implication \\
\> \> \> 2. If $z$ is defeated by someone then $\exists$ a locally fair \\
\> \> \> \> ranking of $T$ with $z$ first. 
            \> ??? \\
\> \> \> 3. QED 
         \> \> Cases
\end{tabbing}
\end{slide}

\begin{slide}
\small
\begin{tabbing}
\=\=\=XXX\=XXXXXXXXXXXXX\=    \kill
\> \> \> 2. If $z$ is defeated by someone then $\exists$ a locally fair \\
\> \> \> \qquad ranking of $T$ with $z$ first. \\
\> \> \> \> 1. Assume $z$ is defeated by someone. \\
\> \> \> \> 2. Choose $x$ to be someone who defeated $z$. \\
\> \> \> \> 3. $z$ has the best record in the subtournament involving all-but-$x$.\\
\> \> \> \> \> $z$ has best record in $T$, no wins are removed. \\
\> \> \> \> 4. $\exists$ ranking of subtournament having $z$ first. \\
\> \> \> \> \> Inductive hypothesis, $z$ has best record. \\
\> \> \> \> 5. Choose $R$ to be a ranking of all-but-$x$ having $z$ first. \\
\> \> \> \> \> EI \\
\> \> \> \> 6. In $T$, $x$ is defeated by someone. \\
\> \> \> \> \> $z$ was defeated, and $x$'s record in $T$ is not \\
\> \> \> \> \> better than $z$'s. \\
%\end{tabbing}
%\end{slide}
%
%\begin{slide}
%\begin{tabbing}
%\=\=\=XXX\=XXXXXXXXXXXXX\=    \kill
\> \> \> \> 7. Define ranking $S$ to be $R$, with $x$ inserted right after \\
\> \> \> \> \qquad the lowest-ranked player that beats $x$. \\
\> \> \> \> 8. $S$ is a locally fair ranking of $T$. \\
\> \> \> \> \> $R$ is locally fair, $x$ is beaten by the player\\
\> \> \> \> \> \quad ranked just above it and beats all \\
\> \> \> \> \> \quad players ranked below it. \\
\> \> \> \> 9. $z$ is first in $S$. 
            \> $z$ is first in $R$; $x$ is not inserted at the top. \\
\> \> \> \> 10. $\exists$ a locally fair ranking of $T$ with $z$ first. \\
\> \> \> \> \> $S$ works, EG \\
\> \> \> \> QED 
            \> Implication \\
\end{tabbing}
\end{slide}


\end{document}
