%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{amssymb}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \theoremstyle{plain}    
 \newtheorem*{prop*}{Proposition} 
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{plain}    
 \newtheorem*{conjecture*}{Conjecture} 
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \newenvironment{lyxcode}
   {\begin{list}{}{
     \setlength{\rightmargin}{\leftmargin}
     \setlength{\listparindent}{0pt}% needed for AMS classes
     \raggedright
     \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \item[]}
   {\end{list}}
 \theoremstyle{remark}
 \newtheorem*{rem*}{Remarque}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\chapter{Induction - Recursion}


\section{Introduction}

\begin{defn*}
A \emph{sequence} S is a list of objects, enumerated in some order: 

\[
S(1),S(2),S(3),\ldots,S(k),\ldots\]

\end{defn*}
A sequence can be defined by giving the value of $S(k)$, for all
$k$.

\begin{example*}
$S(k):=2^{k}$ defines the sequence: $2,4,8,16,32,\ldots$
\end{example*}
Imagine instead that I give you the following recipe:

\begin{itemize}
\item (a) $S(1):=1$.
\item (b) If $k>1$, then $S(k):=S(k-1)+k$.
\end{itemize}
Can you compute $S(2)$? $S(3)$ ? $S(4)$ ?

%

%

%

Could you compute any $S(k)$, where $k>0$.

%

%

%

\begin{prop*}
The sequence $S(k)$ is fully and uniquely defined by (a) and (b).
\end{prop*}
\begin{defn*}
We say that S is defined \emph{recursively} by (a) and (b).
\begin{itemize}
\item (a) is the \emph{base case}
\item (b) is the \emph{induction step}
\end{itemize}
\end{defn*}
\begin{example*}
The stair and the baby.
\end{example*}
This is the idea of recursion (or induction), which is very useful
in maths and computer science.

It allows to reduce an infinite process to a finite (small) number
of steps.

\begin{example*}
Define $S(k)$ by $S(1):=4$.

Problem: how to compute S(2) ?
\end{example*}
%

\begin{example*}
Define S(k) by $S(k):=2S(k-1)$

Problem: both the following sequences satisfies this definition!
\begin{itemize}
\item $1,2,4,8,16,\ldots$
\item $3,6,12,24,48,\ldots$
\end{itemize}
\end{example*}
%

\begin{example*}
Proof that any integer is even.
\end{example*}
Pitfall: Both base case and induction step are necessary !

You need to know how to start, and you need to know how to continue.


\section{Proofs by induction}

\begin{problem}
Let S be the sequence defined by:
\begin{itemize}
\item $S(1)=1$
\item $S(k):=S(k-1)+2^{k-1}$
\end{itemize}
Goal: compute $S(60)$
\end{problem}
%

%

%%

\[
\begin{array}{rclcl}
S(1) & = & 1 & =\\
S(2) & = & 1+2 & =\\
S(3) & = &  & =\\
S(4) & = &  & =\\
\vdots & \vdots & \vdots & \vdots & \vdots\\
S(k) & = & 1+\cdots+2^{k} & =\end{array}\]


\begin{conjecture*}
$S(60)=$
\end{conjecture*}
%

%

%%

The formula $S(k)=2^{k}-1$ is called a \emph{closed form formula}
for $S(k)$.

It allows to compute $S(k)$ easily, without computing all the previous
values $S(1),S(2),\ldots\, S(k-1)$. 

So, how to prove this conjecture ?

%

%

%%

\begin{description}
\item [\emph{Introduce~some~notation}]~


Let $P(k)$ be the predicate: $S(k)=2^{k}-1$.

For any positive integer $k$, $P(k)$ is either true or false.

\item [\emph{Look~at~examples}]~
\end{description}
\begin{xca}
Try the following:
\end{xca}
\begin{itemize}
\item Prove $P(1),P(2),P(3)$
\item Assume that $P(27)$ is true. Can you prove that $P(28)$ is true
?
\end{itemize}
%

%

%%

Now, can you prove $P(60)$?


\subsection{First principle of mathematical induction:}

\begin{thm*}
First principle of mathematical induction

Let $P(k)$ be a predicate. If:

(a) $P(1)$ is true

(b) For any $k>1$, $P(k-1)$ true implies $P(k)$ true

Then: $P(k)$ is true for all $k\geq1$.
\end{thm*}
\begin{defn*}
P is the \emph{inductive hypothesis}.

(a) is the \emph{base case.}

(b) is the \emph{induction step.}
\end{defn*}
\begin{example*}
Consider the sequence $S$ defined as above by:

(a) $S(1):=1$.

(b) $S(k):=S(k)+2^{k-1}$.

Let's prove that for all $k$, $S(k)=2^{k}-1$.
\begin{proof}
Let $P(k)$ be the predicate $S(k)=2^{k}-1$.
\begin{enumerate}
\item Base case:


$S(1)=1=2^{1}-1$. So, $P(1)$ is true.

\item Induction step:


Let $k>1$ be an integer, and assume $P(k-1)$ is true: $S(k-1)=2^{k-1}-1$.

Then, $S(k)=S(k-1)+2^{k-1}=2^{k-1}-1+2^{k-1}=2^{k}-1$.

So, P(k) is also true.

Conclusion: by the first principle of mathematical induction,

$P(k)$ is true for all $k\geq1$, i.e. $S(k)=2^{k-1}$.

\end{enumerate}
\end{proof}
\end{example*}
\begin{xca}
Let $S(k):=1+3+5+\cdots+(2k-1)$. Find a closed form formula for $S(k)$.
\end{xca}
%

\begin{xca}
Prove that $k!>2^{k}$ for any $k\geq4$.
\end{xca}
%

\begin{xca}
Prove that for any integer $k$, $2^{2k}-1$ is divisible by $3$.
\end{xca}
%

\begin{xca}
Prove that $a+ar+ar^{2}+\cdots+ar^{n}=\frac{a-ar^{n}}{1-r}$.
\end{xca}
%

\begin{xca}
Find a closed form formula for $S(k):=1^{4}+2^{4}+\cdots k^{4}$.

Hint: the difficulty is to find a suggestion. What tool could you
use for this?

\end{xca}
%

\begin{xca}
The chess board problem.
\end{xca}

\subsection{Other forms of induction:}

\begin{example*}
Define the sequence $F(n)$ by:

$F(1):=1$

$F(2):=1$

$F(k)=F(k-1)+F(k-2)$, for all $k>2$.
\end{example*}
\begin{xca}
Can you compute $F(3),F(4),F(5)$?
\end{xca}
This sequence is the famous and useful \emph{Fibonacci} sequence.

\begin{problem}
To compute $F(k)$, you not only need $F(k-1)$, but also $F(k-2)$.

So that does not fit into the previous induction scheme.
\end{problem}
That's fine, because to compute $F(k)$, you only need to know the
values of $F(r)$ for $r<k$.

\begin{thm*}
Second principle of Mathematical induction: 

Let $P(k)$ be a predicate. If

(a) $P(1)$ is true,

(b) For any $k>1$, {[} $P(r)$ true for any $r$, $1\leq r<k$ {]}
implies $P(k)$ true,

then: $P(k)$ is true for all $k\geq1$.
\end{thm*}
\begin{example*}
Any integer is a product of prime integers
\end{example*}
%

\begin{example*}
The coin problem
\end{example*}
We did not prove that the first (or the second) principle of induction
were valid. 

Let's just give an idea of the proof:

\begin{thm*}
The three following principles are in fact equivalent:
\begin{enumerate}
\item the first principle of induction
\item (b) the second principle of induction
\item (c) the principle of well ordering:


every non empty collection of positive integers has a smallest member.

\end{enumerate}
\end{thm*}
\begin{problem}
Is the principle of well ordering valid for $\Z$ ? $\R$ ? $\C$
?
\end{problem}

\section{Other uses of induction}

Induction is a much more general problem solving principle.

If you have a family of problems such that:

\begin{itemize}
\item There is some measure of the size of a problem
\item You can solve the smallest problems
\item You can breakup each bigger problems in one (or several) strictly
smaller cases, and build from it a solution for the big problem.
\end{itemize}
Then, you can solve by induction any problem in your family.

\begin{example*}
Problem: computation of $F(k)$.

Measure of the problem: $k$.

Value of $F(1)$ is known.

$F(k)$ can be computed from the values of $F(k-1)$ and $F(k-2)$
\end{example*}
%

\begin{example*}
Inductive definition of well formed formulas from formal logic

<basic proposition>: $A$ | $B$ | $C$ | \ldots{}

<binary connective>: $\wedge$ | $\vee$ | $\rightarrow$ | $\leftarrow$
| $\leftrightarrow$

<wff>: <basic proposition> | <wff>$'$ | $($<wff>$)$ | <wff> <binary
connective> <wff>
\end{example*}
This kind of inductive description is called {*}BNF{*} (Backus Naur
form).

\begin{example*}
Recursive proof of a property of wff
\end{example*}
\begin{thm*}
If a wff contains $n$ propositions (counted with repetition: in $A\vee A$,
there are two propositions), then it contains $n-1$ binary connectives.
\end{thm*}
\begin{example*}
Recursive algorithm for the computation of the value of a wff:
\begin{lyxcode}
bool~function~Evaluation($P$,~$C$)

//~Precondition:~$P$~is~a~wff,~$C$~is~the~context,~i.e.

//~the~truth~values~of~all~the~basic~propositions.

//~Postcondition:~returns~the~truth~value~of~$P$~in~the~//~context~$C$



Begin

~~If~$P$~is~a~proposition~(say~$A$)~Then

~~~~Return~the~truth~value~of~$A$;

~~ElseIf~$P$~is~of~the~form~$(Q)$~Then

~~~~Return~Evaluation($Q$,~$C$);

~~ElseIf~$P$~is~of~the~form~$Q'$~Then

~~~~Return~not~Evaluation($Q$,$C$);

~~ElseIf~$P$~is~of~the~form~$Q_{1}\wedge Q_{2}$~Then

~~~~Return~Evaluation($Q_{1}$,~$C$)and~Evaluation($Q_{2}$,~$C$);



~~...~//~Other~binary~operators



~~Else

~~~~Error~$P$~is~not~a~wff;

End;
\end{lyxcode}
\begin{rem*}
There are programming languages that are particularly well adapted
to write this kind of algorithms. Actually, the real program would
almost look like the pseudo-code. See for example CAML \url{ftp://ftp.inria.fr/lang/caml-light/}.
\end{rem*}
\end{example*}
%

\begin{example*}
Bijection between words of parenthesis and forests
\end{example*}

\section{Conclusion}

Induction is a fundamental technique for solving problems, in particular
in computer science.

It's the mathematical formalization of the divide and conquer approach.
\end{document}
