\documentclass{slides}

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

\begin{document}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\=    \kill
Prove: $\sqrt{2}$ is irrational. \\
1. $\sqrt{2}$ rational $\Rightarrow \textit{false}$ \\
\> 1. Assume $\sqrt{2}$ rational. \\
\> 2. $\textit{false}$ \\
\> \> 1. Choose $a, b \in N^{+}$, $\sqrt{2} = {a \over b}$, lowest terms. \\
\> \> \> \> \> Basic properties of $\textbf{Q}$, EI \\
\> \> 2. $2 b^2 = a^2$       
      \> \> \> Algebra \\
\> \> 3. $a^2$ is even.
      \> \> \> EG, def.\ of ``even'' \\
\> \> 4. $a$ is even.      
      \> \> \> ??? \\
\> \> 5. Choose $c \in N$, $a = 2c$. 
      \> \> \> Def.\ of ``even'', EI \\
\> \> 6. $4 c^2 = a^2 = 2b^2$ 
      \> \> \> Algebra \\
\> \> 7. $2 c^2 = b^2$       
      \> \> \> Algebra \\
\> \> 8. $b^2$ is even.
      \> \> \> EG, def.\ of ``even'' \\
\> \> 9. $b$ is even.
      \> \> \> ??? \\
\> \> 10. $a$ and $b$ not in lowest terms. 
      \> \> \> 1.2.4, 1.2.9 \\
\> \> 11. QED
      \> \> \> 1.2.1, 1.2.10, logic \\
\> 3.  QED                 
   \> \> \> \> Implication. \\
2. QED  
\> \> \> \> \> Contradiction. \\
\end{tabbing}
\end{slide}

\begin{slide}
The proof is by contradiction.  Assume for purpose of contradiction
that $\sqrt{2}$ is rational.  Then we can write $\sqrt{2} = a/b$ where
$a$ and $b$ are integers and the fraction is in lowest terms.
Squaring both sides gives $2 = a^2 / b^2$ and so $2 b^2 = a^2$.  This
implies that $a$ is even; that is, $a$ is a multiple of $2$.  As a
result, $a^2$ is a multiple of 4.  Because of the equality $2 b^2 =
a^2$, $2 b^2$ must also be a multiple of 4.  This implies that $b^2$
is even and so $b$ must be even.  But since $a$ and $b$ are both even,
the fraction $a/b$ is not in lowest terms.  This is a contradiction,
and so the assumption that $\sqrt{2}$ is rational must be false.
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
To prove: $\forall n \geq 0 (P(n))$ \\
It's enough to show:\\
1. (Base) $P(0)$ \\
2. (Inductive step) $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$
\end{tabbing}
\vspace{3in}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
To prove: $\forall n \geq k (P(n))$\\
It's enough to show:\\
1. (Base) $P(k)$ \\
2. (Inductive step) $\forall n \geq k (P(n) \Rightarrow P(n+1))$
\end{tabbing}
\vspace{3in}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2})$ 
\end{tabbing}
\vspace{1in}
\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 (P(n) \Rightarrow P(n+1))$ \\
3. QED                        
\> \> \> \> \> Induction 
\end{tabbing}
\vspace{1in}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2})$.\\
1. (Base) $\sum_{i=1}^0 i = \frac{0(0+1)}{2}$. \\
2. (Inductive step) 
  $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2} 
	\Rightarrow \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})$ \\
3. QED                              
\> \> \> \> \> Induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXX\=    \kill
1. (Base) $\sum_{i=1}^0 i = \frac{0(0+1)}{2}$ ($P(0)$) \\
\> 1. $\sum_{i=1}^0 i = 0$
   \> \> \> \> Def. of sum with no terms \\
\> 2. $\frac{0(0+1)}{2} = 0$
   \> \> \> \> Arithmetic \\
\> 3. QED
   \> \> \> \> By 1.1 and 1.2.
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
2. (Inductive step) $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2}
	\Rightarrow \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. $\sum_{i=1}^n i = \frac{n(n+1)}{2} \Rightarrow 
       \sum_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}$ \\
\> \> 1. Assume $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ \\
\> \> 2. $\sum_{i=1}^{n+1}i= \frac{(n+1)(n+2)}{2}$ 
      \> \> \> ??? \\
\> \> 3. QED   
      \> \> \> Implication \\
\> 3. QED
   \> \> \> \> UG 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXXXXXXXXXXXXXXXXXX\=    \kill
2. $\sum_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}$ \\
\> 1. $\sum_{i=1}^{n+1}i = (\sum_{i=1}^{n}i)  + (n+1)$ 
   \> \> Sum has one extra term. \\
\> 2. $(\sum_{i=1}^{n}i) + (n+1) = \frac{n(n+1)}{2}+ n+1$ \\
 \> \> \> Inductive hypothesis $P(n)$ (2.2.1) \\
\> 3. $\frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}$ 
   \> \> Algebra \\
\> 4. QED 
   \> \> Combine previous 3 equations.
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 \; (P(n))$ \\
1. (Base) $P(0)$ \\
2. (Inductive step) $\forall n \geq 0 \; (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 0$ \\
\> 2. $P(n) \Rightarrow P(n+1)$ \\
\> \> 1. Assume $P(n)$ \\
\> \> 2. $P(n+1)$ 
      \> \> \> ??? \\
\> \> 3. QED
      \> \> \> Implication \\
\> 3. QED 
   \> \> \> \> Universal generalization \\
3. QED 
\> \> \> \> \> Induction
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXX\=    \kill
Prove: $\forall n \in N, n \geq 0 \; (6 | n^3 - n)$ \\
1. (Base) $6 | 0^3 - 0$ \\
2. (Inductive step) 
    $\forall n \geq 0 (6 | n^3 - n \Rightarrow 6 | (n+1)^3 - (n+1))$ \\
\> 1. Fix $n \geq 0$.\\
\> 2. Assume $6 | n^3 - n$ \\
\> 3. $6 | (n+1)^3 - (n+1)$
   \> \> \> \> ??? \\
\> 4. QED     
   \> \> \> \> Implication, \\
\> \> \> \> \> \hspace{.5ex} UG (condensing two steps here) \\
3. QED 
\> \> \> \> \> Induction \\
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXX\=    \kill
Prove: $\forall n \in N, n \geq 0 (6 | n^3 - n)$ \\
1. (Base) $6 | 0^3 - 0$ \\
2. (Inductive step) 
    $\forall n \geq 0 (6 | n^3 - n \Rightarrow 6 | (n+1)^3 - (n+1))$ \\
\> 1. Fix $n \geq 0$. \\ 
\> 2. Assume $6 | n^3 - n$ \\
\> 3. $6 | (n+1)^3 - (n+1)$ \\
\> \> 1. $(n+1)^3 - (n+1) = n^3 - n  + 3(n^2 + n)$ \\
\> \> \> \> \> Algebra \\
\> \> 2. $n^2 + n$ is even 
      \> \> \> Last lecture \\
\> \> 3. $2 | n^2 + n$  
      \> \> \> Definition of $|$ \\
\> \> 4. $6 | 3(n^2 + n)$ 
      \> \> \> Multiplying both sides by $3$ \\
\> \> 5. $6 | (n^3 - n)  + 3(n^2 + n)$ 
      \> \> \> Divides both terms (2.2, 2.3.4), \\
\> \> \> \> \> \quad so divides sum. \\
\> \> 6. QED 
      \> \> \> 2.3.1, 2.3.5 \\
\> 4. QED \\
3. QED \\
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXX\=XXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1})$ \\
1. (Base) $\Sigma_{i=0}^0 F_i^2 = F_0 F_1$ \\
2. (Inductive step) 
    $\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1}$ \\
\> \> \> \> $\Rightarrow \Sigma_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2})$ 
         \> ??? \\
3. QED               
\> \> \> \> \> Induction
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1})$ \\
1. (Base) $\Sigma_{i=0}^0 F_i^2 = F_0 F_1$ 
\> \> \> \> \> Both sides are $0$. \\
2. (Inductive step) 
   $\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1} 
	 \Rightarrow \Sigma_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2})$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $\Sigma_{i=0}^n F_i^2 = F_n F_{n+1}$ \\
\> 3. $\Sigma_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2}$ \\
\> \> 1. $\Sigma_{i=0}^{n+1} F_i^2 = \Sigma_{i=0}^n F_i^2 + F_{n+1}^2$ 
      \> \> \> Sum has one extra term \\
\> \> 2. $\Sigma_{i=0}^n F_i^2 + F_{n+1}^2 = F_n F_{n+1} + F_{n+1}^2$ 
      \> \> \> Inductive hyp. \\
\> \> 3. $F_n F_{n+1} + F_{n+1}^2 = F_{n+1}(F_n + F_{n+1})$ 
      \> \> \> Algebra \\
\> \> 4. $F_{n+1}(F_n + F_{n+1}) = F_{n+1} F_{n+2}$ 
      \> \> \> Fibonacci definition \\
\> \> 5. QED                         
      \> \> \> Combining equations \\
\> 4. QED 
   \> \> \> \> Implication, UG \\
3. QED                           
\> \> \> \> \> Induction
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 3$ (Sum of interior angles of any $n$-sided \\
\> \> \> \> convex polygon is $(n-2)180$ degrees) \\
1. (Base) Sum of angles in any triangle is $180$. 
\> \> \> \> \> Basic geometry \\
2. (Inductive step) $\forall n \geq 3 \; (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 3$. \\
\> 2. Assume sum of angles of any $n$-sided convex poly is $(n-2) 180$. \\
\> 3. Sum of angles of any $n+1$-sided convex poly is $(n-1) 180$. \\
\> \> 1. Fix any $n+1$-vertex convex poly $X$, \\
\> \> \> say with vertices $x_1,x_2,\ldots,x_{n+1}$ \\
\> \> 2. Let $Y$ be poly with vertices $x_1,x_2,\ldots,x_n$
(cut out a vertex). \\
\> \> 3. $Y$ is a convex poly with at least 3 vertices. \\
\> \> 4. Sum of angles of $Y$ is $(n-2)180$. 
       \> \> \> Inductive hyp.  \\
\> \> 5. Sum of angles of triangle $T = x_n, x_{n+1}, x_1$ is $180$. \\
%      \> \> \> Basic geometry \\
\> \> 6. Sum of angles in $X$ = sum in $Y$ + sum in $T$ \\
\> \> \> \> $= (n-2)180 + 180 = (n-1)180$. 
            \> Basic geometry, \\
\> \> \> \> \> \quad arithmetic. \\
\> \> 7. QED
      \> \> \> UG \\
\> 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)$ \\
\> 1. $\forall k (f(0,k) = \frac{(0+k)!}{0!k!})$
   \> \> \> \> Both sides are 1 \\
\> 2. QED 
   \> \> \> \> Definition of $P(0)$ \\
2. (Inductive step) $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $P(n)$, that is, row $n$ is correct. \\
\> 3. $P(n+1)$, that is, row $n+1$ is correct.      
   \> \> \> \> ??? \\
\> 4. QED    
   \> \> \> \> Implication, UG \\
3. QED                           
\> \> \> \> \> Induction 
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXX\=    \kill
\> 3. $P(n+1)$ \\
\> \> 1. $\forall k (Q(n+1,k))$ \\
\> \> \> 1. (Base) $Q(n+1,0)$ \\
\> \> \> 2. (Inductive step) $\forall k \geq 0 (Q(n+1,k) \Rightarrow Q(n+1,k+1))$. \\
\> \> \> 3. QED  
         \> \> Induction \\
\> \> 2. QED
      \> \> \> Definition of $P(n+1)$
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 1. (Base) $Q(n+1,0)$ \\
\> \> 1. $f(n+1,0) = \frac{(n+1+0)!}{n+1! 0!}$ 
      \> Both sides are 1 \\
\> \> 2. QED
      \> Definition of $Q(n+1)$
\end{tabbing}
\end{slide}

\begin{slide}
\begin{tabbing}
XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
2. (Inductive step) $\forall k \geq 0 (Q(n+1,k) \Rightarrow Q(n+1,k+1))$. \\
\> 1. Fix $k \geq 0$. \\
\> 2. Assume $Q(n+1,k)$. \\
\> 3. $Q(n+1,k+1)$ \\
\> \> 1. $f(n+1,k+1)= f(n,k+1) + f(n+1,k)$ \\
\> \> \> Definition of $f(n+1,k+1)$ \\
\> \> 2. $f(n+1,k) = \frac{(n+1+k)!}{(n+1)!k!}$ 
      \> Inductive hypothesis 2.3.1.2.2, \\
\> \> \> \quad def. of $Q(n+1,k)$. \\
\> \> 3. $f(n,k+1) = \frac{(n+k+1)!}{n!(k+1)!}$ 
      \> Inductive hypothesis 2.2, \\
\> \> \> \quad def. of $P(n,k+1)$. \\
\> \> 4. $f(n+1,k+1)=\frac{(n+k+1)!}{n!(k+1)!}+\frac{(n+1+k)!}{(n+1)!k!}
         =\frac{(n+1+k+1)!}{(n+1)!k+1!}$ \\
\> \> \> Combine equations, algebra \\
\> \> 5. QED                   
      \> Definition of $Q(n+1,k+1)$ \\
\> 4. QED
   \> \> Induction
\end{tabbing}
\end{slide}


\end{document}
