\documentclass[11pt,twoside]{article}
\usepackage{/a/class/6.042/fall00/newlectures/macros-course-lectures}

\renewcommand{\thepage}{\arabic{page}}

%\makeslides

\begin{document}

\onlystudents

\lecture{notes3}{Proof by Induction, continued}{September 14, 2000}

\section{Inductive Proofs}

\subsection{Fibonacci numbers}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \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}

\noindent
Complete proof:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \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$
      \> \> \> Summation 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 hypothesis (2.2) \\
\> \> 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 the equations \\
\> 4. QED 
   \> \> \> \> Implication, UG \\
3. QED                           
\> \> \> \> \> Induction
\end{tabbing}

\subsection{Double Induction}

Define: \\
$f(0,k) = 1$ for all $k \geq 0$. \\
$f(n,0) = 1$ for all $n \geq 0$.\\
For $n, k \geq 0:$ $f(n+1,k+1) = f(n,k+1) + f(n+1,k)$. 

\begin{lemma}
$\forall n [\forall k [f(n,k) = \frac{(n+k)!}{n! k!}]]$
\end{lemma}

\noindent 
$Q(n,k):$ $f(n,k) = \frac{(n+k)!}{n! k!}$.\\
$P(n):$  $\forall k [Q(n,k)]$, that is, $\forall k [f(n,k) = \frac{(n+k)!}{n! k!}]$\.  

\noindent
Proof skeleton:

\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 (for any $k$) \\
\> 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}

\noindent
Adding some more steps: 
\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 (for any $k$) \\
\> 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)$. \\
\> 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)$ \\
\> 4. QED    
   \> \> \> \> Implication, UG \\
3. QED                           
\> \> \> \> \> Induction 
\end{tabbing}

\begin{tabbing}
XXX\=XXX\=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}

\begin{tabbing}
XXX\=XXX\=XXX\=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, \\
\> \> \> \> \> \> definition of $Q(n+1,k)$. \\
\> \> \> \> \> 3. $f(n,k+1) = \frac{(n+k+1)!}{n!(k+1)!}$ 
               \> Inductive hypothesis 2.2, \\
\> \> \> \> \> \> definition 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)!}$ \\
\> \> \> \> \> \> Combining equations, algebra \\
\> \> \> \> \> 5. QED                   
               \> Definition of $Q(n+1,k+1)$ \\
\> \> \> \> 4. QED
            \> \> Induction
\end{tabbing}

\section{Strong induction}

\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(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}

\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(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}

\section{Strong Induction Proof Examples}

\subsection{Block towers}

$P(n):$  ``We can build a tower of height $n$''\.

\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(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
2. (Inductive step) 
$\forall n \geq 12 
   [(\forall i, 12 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 12$. \\
\> 2. $(\forall i, 12 \leq i \leq n (P(i))) \Rightarrow P(n+1)$ \\
\> \> 1. Assume $\forall i, 12 \leq i \leq n (P(i)$ \\
\> \> 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)$ \\
\> \> \> \> 1. Assume $n \geq 14$. \\
\> \> \> \> 2. $P(n-2)$
            \> By inductive hypothesis 2.2.1 and the fact \\
\> \> \> \> \> that $n-2 \geq 12$ \\
\> \> \> \> 3. $P(n+1)$
            \> Add one block to the tower from the \\
\> \> \> \> \> previous step. \\
\> \> \> \> 4. QED
            \> Implication \\
\> \> \> 4. QED
         \> \> Cases \\
\> \> 3. QED 
      \> \> \> Implication \\
\> 3. QED
   \> \> \> \> UG
\end{tabbing}

\subsection{Fibonacci examples}

\subsubsection{A lower bound}

$P(n):$ $F_n \geq (\frac{3}{2})^{n-2}$

\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)$ \\
\> \> 1. $F_n \geq (\frac{3}{2})^{n-2}$
      \> \> \> Inductive hypothesis 3.2 \\
\> \> 2. $F_{n-1} \geq (\frac{3}{2})^{n-3}$
      \> \> \> Inductive hypothesis 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 the inequalities into the equation \\
\> \> 5. $F_{n+1} \geq (\frac{3}{2})^{n-1}$ \\
\> \> \> 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. QED 
         \> \> Algebra (3.3.4 and 3.3.5.2) \\
\> \> 6. QED
      \> \> \> Definition of $P(n+1)$ \\
\> 4. QED
    \> \> \> \> Implication, UG \\
4. QED
\> \> \> \> \> Strong induction
\end{tabbing}

\end{document}