
\section{Recursive Definitions}
A {\em recursive definition} says how to build something from
a simpler version of the same thing. \\

They have two parts:
\begin{itemize}
\item Base case(s) that don't depend on anything else
\item Combination cases that depend on simpler cases
\end{itemize}
Note the relationship to a {\em recursive algorithm.}  We will also
see a close relation to induction.

In our definitions, we will frequently use the symbol ``$=$'' in a
special sense that means what appears on the left is defined to be
what appears on the right\.  We expect you to recognize from context
which use we intend and, in the definitional case, only to use the
statement as a definition and not as an algebraic statement\.  Here
are several examples:

\begin{description}

\item[The Factorial function:]\mbox{}
  \begin{itemize}
  \item $0!=1$
  \item $(n+1)! = (n+1)n!$ for $n \ge 1$.
  \end{itemize}

\item[The Fibonacci numbers:]

  These are interesting numbers that arise, e.g., in biology, where
  they model some types of growth processes (plants, cells, rabbit
  populations, etc.)\.  The Fibonacci numbers are written as $F_i$, $i
  = 0, 1, 2, \ldots$\.  They are defined recursively by: \\ 
  \begin{align*}
    F_0 &= 0\\ 
    F_1 &= 1\\ 
    F_i &= F_{i-1} + F_{i-2} \mbox{ for $i \geq 2$.} 
  \end{align*}
  Note there 2 base cases, since each combination relies on previous two
  values.

  What is $F_4$?  Well, $F_2 = F_0+F_1 = 1$, $F_3 = F_1+F_2 = 2$, so
  $F_4 = 3$.  The sequence starts out $0, 1, 1, 2, 3, 5, 8, 13,
  21,\ldots$.

\item[ $\Sigma$ notation (the traditional style):] (We've been using
  this notation informally already)
  \begin{itemize}
  \item $\Sigma_{i=1}^0 f(i) = 0$ \\
  \item $\Sigma_{i=1}^{n+1} f(i) = \Sigma_{i=1}^n f(i) + f(n+1)$. 
  \end{itemize}

\item[Simultaneous recursive definitions.]

  You can define several things at the same time, in terms of each
  other.  For example, we may define two functions $f$ and $g$ from
  $\naturals$ to $\naturals$, recursively, by:
  \begin{itemize}
  \item
    $f(0) = 1$
  \item
    $g(0) = 1$
  \item
    $f(n+1) = f(n) + g(n)$, $n \geq 0$
  \item
    $g(n+1) = f(n) \times g(n)$, $n \geq 0$
  \end{itemize}

\end{description}


We must take care that concepts defined by recursive definitions are
well-defined\.  Below are some examples that aren't well-defined\.  In
these examples, the notion being defined always appears on the
left-hand side\.
\begin{description}
\item[$f(n)=2+f(n-1)$.]
  This definition has no base case.
\item[\rm $f(1)=1$ and $f(n) = 1+f(n+1)$.]

  This still has no sufficient base case, because $f(n)$ is defined in
  terms of $f(n+1)$\.  So for positive integers $n$ other than 1,
  $f(n)$ is defined in terms of ``more complex'' cases instead of
  simpler ones\.  Note that if we had written $f(n+1) = f(n)-1$, we
  would have meant something different (we would be defining $f(n+1)$
  in terms of $f(n)$) and $f$ would have been well-defined for all
  positive integers\.  Also, note that the first way makes $f$
  well-defined for all integers {\em less than} or equal to 1.

\item[\rm $f(1)=1$ and $f(n) = 3f(n/2)$.]  This doesn't give a definition
  for odd values of $n$, since $n/2$ is not a natural number in this
  case.

\item[\rm A mystery.]  Mathematicians have been wondering about this one
  for a while:
  \begin{itemize}
  \item $f(1) = 1$
  \item If $n$ is even, then $f(n) = f(n/2)$.
  \item If $n$ is odd, then $f(n) = f(3n+1)$.
  \end{itemize}
  If $f$ is well defined, then $f(n)=1$ everywhere.  But nobody knows if
  the recursion always terminates (though it's been checked for many numbers).
\end{description}

\section{Inductive Proofs on Recursive Definitions} 

A recursive definition usually leads to inductive
proofs---the induction follows the definition down to the base case\.
The examples in this section involve functions that are defined
recursively\.  

\subsection{Fibonacci Numbers}

The Fibonacci numbers (defined earlier) satisfy many cute identities,
so they provide lots of fun for mathematicians\.  For example:
\begin{theorem}
  $\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1})$
\end{theorem}

Example: $n = 4$: \\
$0^2 + 1^2 + 1^2 + 2^2 + 3^2 = 15 = 3 \cdot 5$\.
\\
Let's try a proof by (standard, not strong) induction\.  The theorem
statement suggests trying it with $P(n)$ defined as:
\[\sum_{i=0}^n F_i^2 = F_n F_{n+1}
\]

\structuredproof{
  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})$ \reason{???}\\
  3. QED               \reason{induction}\\
}

\noindent Now we stare at the gap between $P(n)$ and $P(n+1)$\.
$P(n+1)$ is given by a summation that's obtained from that for $P(n)$
by adding one term; this suggests that, once again, we subtract.  The
difference is just the term $F_{n+1}^2$\.  Now, we are assuming that
the original $P(n)$ summation totals $F_n F_{n+1}$ and want to show
that the new $P(n+1)$ summation totals $F_{n+1} F_{n+2}$\.  So we
would {\em like\/} the difference to be
\[
F_{n+1} F_{n+2} - F_n F_{n+1}
\]

So, the actual difference is $F_{n+1}^2$ and the difference we want is
$F_{n+1} F_{n+2} - F_n F_{n+1}$\.  Are these the same\?  We want to
check that:
\[
F_{n+1}^2 = F_{n+1} F_{n+2} - F_n F_{n+1}
\]
But this is true, because it is really the Fibonacci definition in
disguise: to see this, divide by $F_{n+1}$\.  \forstudents{Here's the complete
proof:

\structuredproof{
  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$ 
  \reason{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})$ \noreason \\
  \> 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$
  \reason{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$
  \reason{Inductive hypothesis (2.2)} \\
  \> \> 3. $F_n F_{n+1} + F_{n+1}^2 = F_{n+1}(F_n + F_{n+1})$
  \reason{Algebra} \\
  \> \> 4. $F_{n+1}(F_n + F_{n+1}) = F_{n+1} F_{n+2}$ 
  \reason{Fibonacci definition} \\
  \> \> 5. QED                         
  \reason{Combining the equations} \\
  \> 4. QED 
  \reason{Implication, UG} \\
  3. QED                           
  \reason{Induction}\\
}
}

\subsubsection{Another false theorem}

Here is another false ``theorem''\.  The fallacy is like the blocks
example---we don't have enough base cases.

\begin{falsethm}
  All Fibonacci numbers are even.
\end{falsethm}

We try strong induction, where $P(n)$ is defined to be ``$F_n$ is
even.'' 
\structuredproof{
  Prove: $\forall n \geq 0 [P(n)]$ \\
  1. (Base) $P(0)$
  \reason{$F_0 = 0$, which is even.} \\
  2. (Inductive step) 
  $\forall n \geq 0 [(\forall i, 0 \leq i \leq n (P(i))) \Rightarrow
  P(n+1)]$
  \reason{???} \\
  3. QED      \reason{Strong induction}\\
}

The inductive step is supposed to prove that $F_{n+1}$ is even, using
the fact that all smaller Fibonacci numbers are even\.
The idea is to express $F_{n+1}$ as usual, as $F_{n-1} + F_n$\.
Then use the strong inductive hypothesis to say that $F_{n-1}$ and $F_n$
are both even\.
The sum is therefore also even\.
\\
What's the error?  We proved:
$P(0)$ \\
$P(0) \wedge P(1) \Rightarrow P(2)$ \\
$P(1) \wedge P(2) \Rightarrow P(3)$, etc. \\
But we never proved $P(1)$.

\subsubsection{A lower bound}

Here's a correct strong-induction proof about Fibonacci numbers\.  It
shows a lower bound on their values.
\begin{lemma}
  $\forall n \geq 2 [F_n \geq (\frac{3}{2})^{n-2}]$
\end{lemma}
\begin{proof}
  Use strong induction\.
  Let $P(n) = F_n \geq (\frac{3}{2})^{n-2}$
  \begin{structproof}
    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{structproof}

  \noindent
  Now in proving the ??? we are only worrying about $n \geq 3$ and we may
  assume the inequality for all $i$ from $2$ up to $n$, inclusive\.
  Because of the way Fibonacci numbers are defined, it turns out that the
  ones we need are just $n$ and $n-1$\.
  Those are in the range for which we can assume the property. 
  \begin{structproof}
    \> 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. 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}$
    \> \> Algebra (3.3.4 and 3.3.5.2) \\
    \> \> \> 4. QED
    \> \> Definition of $P(n+1)$ 
  \end{structproof}
\end{proof}


\subsection{Double Induction}

Here's a trickier use of recursive definitions and induction, used
twice, in a nested way, in the same proof\.  Define a function of two
natural number variables recursively as follows: \\ 
$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)$. \\ 
\\
Why does this define a function\?  We can see by looking at a table\.
The first two rules fill in the first row and column, respectively\.
For each other entry, you obtain the value by adding the upper and
left neighbors\.  It is left to the reader to see that this defines a
unique function, that is, fills in all the spaces, in exactly one way.
\[
\begin{array}{r|rrrrr}
   & 0   & 1  &  2  &  3  &  4 \\
\hline
0  & 1   & 1  &  1  &  1  &  1 \\
1  & 1   & 2  &  3  &  4  &  5 \\
2  & 1   & 3  &  6  & 10  & 15 \\
3  & 1   & 4  & 10  & 20  & 35 \\
4 & 1 & 5 & 15 & 35 & 70\\
\end{array}
\]
If you turn this rectangle on its corner, you get the famous
``Pascal's triangle.''
We will see these numbers later in the term (around lecture 16)\.  
For now, here is a formula (which we pull out of thin air), giving the 
exact value of the function on any pair of arguments:
\[
f(n,k) = \frac{(n+k)!}{n!\;
  k!}.
\]

Here we are using the factorial function defined earlier.  As an
example, 
\[
f(3,4) = \frac{7!}{3!4!} =
\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{3\cdot 2\cdot
  1\cdot 4\cdot 3\cdot 2\cdot 1} = 35.
\]

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

\noindent We can prove this by induction\.  But there are two
variables, $n$ and $k$\.  So, we will do the proof in 2 levels\.  The
main strategy is by induction on $n$\.  And for each particular $n$,
we work by induction on $k$\.  We are doing induction inside an
induction\.  Let's break up the statement to make the two levels
clearer\.  The specific statement we want to prove is:
\begin{lemma}
  $\forall n [\forall k [f(n,k) = \frac{(n+k)!}{n! k!}]]$
\end{lemma}

\noindent Define $Q(n,k)$ to be the predicate $f(n,k) =
\frac{(n+k)!}{n! k!}$\.  $Q(n,k)$ says that the value in position
$(n,k)$ is correct (satisfies the formula)\.  Define $P(n)$ to be the
statement $\forall k [Q(n,k)]$, that is, $\forall k [f(n,k) =
\frac{(n+k)!}{n!  k!}]$\.  In English, $P(n)$ means that all the
values in row $n$ are correct\.

\forstudents{
Now we use the standard induction pattern: 
\begin{structproof}
  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{structproof}


Expanding this pattern:
\begin{structproof}
  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{structproof}

Now, how to prove 3\?  It involves saying something about the whole
row $n+1$\.  
We use induction to handle all the elements in this row one at a
time\.  
Our goal 3 can be rewritten, using the definition of $P$ in terms of
$Q$\.  
Note that this is all talking just about the particular row $n+1$.

\begin{structproof}
  \> 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{structproof}

\noindent
The base case for the inner induction follows by expanding the
definition of $Q(n+1,0)$:
\begin{structproof}
  \> \> \> 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{structproof}

\noindent
The inductive step involves a little algebra:
\begin{structproof}
  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{structproof}
}

The ``inner'' inductive hypothesis (the one involving $Q(n+1,k)$)
is invoked to get information about the
previous element in the same row, $n+1$\. 
The ``outer'' inductive hypothesis (the one involving $P(n,*)$),
is invoked to get information about element $k+1$ of the previous row\.
(The proof uses UI in the invocation of the outer inductive hypothesis.)
