\documentclass[12pt]{article}

%Page set up
\setlength{\topmargin}{-0.75in}
\setlength{\textwidth}{7in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\textheight}{9in}

\newtheorem{thm}{Theorem}
\newtheorem{ex}[thm]{Example}
 %Packages
\usepackage{amssymb,amsmath,pstricks}
\usepackage{array}
\usepackage{color}
\usepackage{colortbl,xcolor}
\usepackage{fancybox,framed}
\usepackage{url}

\renewenvironment{framed}[1][\hsize]
  {\MakeFramed{\hsize#1\advance\hsize-\width \FrameRestore}}%
  {\endMakeFramed}

% Start document
\setcounter{page}{1}
\begin{document}
\begin{center}
{\Large \bf Mathematical Induction \\
Recursions}\\
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Induction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Mathematical Induction} 

Many theorems state that a proposition $P(n)$ is true for all possible values on $n$, where $n$ can be a natural number or a positive integer. For example,
we could be asked to show that
\begin{eqnarray*}
\forall n \in \mathbb{N}, \quad \sum_{i=0}^n i = \frac{n(n+1)}{2}
\end{eqnarray*}
We cannot prove such theorems by trying all possible values of $n$! Mathematical induction is a proof technique that often allows us to prove such assertions.

\vspace{0.1in}
\noindent\textbf{\emph{How does it work?}}

\vspace{0.1in}
\noindent Induction is equivalent to a ``cascade" reaction. It works by first proving that the statement is true for a start value, and then by proving that the process used to go from one value to the next is valid. 
If both are true, then the statement is true for all values. Think of it as a ``domino effect". If you have a long row of dominoes and if
\begin{itemize}
\item[a)] The first domino falls
\item[b)] Whenever a domino falls, its next neighbor falls,
\end{itemize}
then all dominoes fall.

\begin{framed}
\noindent A proof by induction that a proposition $P(n)$ is true for every natural number $n$ consists of two steps:
\begin{itemize}
\item \textbf{\emph{Base case:}} The proposition $P(i)$ is true for a start position $i$ (usually $i=0$ or $i=1$)
\item \textbf{\emph{Inductive step:}} The implication $P(k) \to P(k+1)$ is shown to be true for very natural number $k \ge i$
\end{itemize}
\noindent The principle of proof by induction allows then to conclude that:
\begin{eqnarray*}
\forall n \in \mathbb{N}, n \ge i, P(n) \text{ is true}
\end{eqnarray*}
\end{framed}

\vspace{0.1in}
A proof by mathematical induction can in fact be phrased as a rule of inference. Let $n$ and $i$ be natural numbers.
Then the proposition
\begin{eqnarray*}
\left [ P(i) \land \left( \forall k \in \mathbb{N}, k\ge i, P(k)\to P(k+1) \right) \right] \to \left ( \forall n \in \mathbb{N}, n \ge i, P(n) \right)
\end{eqnarray*}
is a tautology.

\vspace{0.1in}
\noindent \textbf{Proof:}
Let us define,
\begin{align*}
Q:& \quad P(i) \land \left( \forall k \in \mathbb{N}, k\ge i, P(k)\to P(k+1) \right) \\
R:&  \quad \forall n \in \mathbb{N}, n \ge i, P(n)
\end{align*}
We want to prove $Q\to R$ is always true. We use a proof by contradiction, i.e. we assume that $Q$ is true AND $R$ is false. 

$R$ is false means that there exists at least one value of $n\ge i$ such that $P(n)$ is not true. Let $S$ be the set of such values $n$ for which $P(n)$ is not true. $S$ is not empty, and $S$ is bounded from below, by $i$. Therefore, $S$ has a least element, $N_S$ (based on the well ordering property), with $N_S > i$. As $N_S$ is the least element of $S$, $N_S-1$ does not belong to $S$. Therefore $P(N_S-1)$ is true. Since $N_S-1 \ge i$ and $P(N_S-1)$ is true, based on the fact that $Q$ is true, $P(N_S)$ is true. We have reached a contradiction: $P(N_S)$ is true, and since $N_S \in S$, $P(N_S)$ is false. Therefore our assumption that $Q\to R$ can be false is false. The method of proof by induction is a valid method of proof.


\vspace{0.1in}
\noindent \textbf{Examples:}

\begin{itemize}
\item \emph{Show that: $\forall n \in \mathbb{N}, \displaystyle \sum_{i=1}^{n}i = \displaystyle\frac{n(n+1)}{2} $}.

\vspace{0.1in}
\noindent \textbf{Proof:}

\vspace{0.1in}
Let $P(n)$ be the proposition: $\displaystyle\sum_{i=1}^{n} = \displaystyle\frac{n(n+1)}{2}$. Let us also define $LHS(n) = \displaystyle\sum_{i=1}^{n}i$ and $RHS(n)=\displaystyle\frac{n(n+1)}{2}$
\\
\begin{itemize}
\item \emph{Base case:} We show that $P(1)$ is true:
\begin{eqnarray*}
LHS(1) &=&\sum_{i=1}^{1} i = 1\\
RHS(1)&=&\frac{1(1+1)}{2} = \frac{2}{2}=1
\end{eqnarray*}
\\
\item \emph{Inductive step:} Let $k$ be a natural number, and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Let us compute $LHS(k+1)=\displaystyle\sum_{i=1}^{k+1}i$:\\
\begin{eqnarray*}
LHS(k+1) &=& \displaystyle\sum_{i=1}^{k} i + (k+1)\\
&=& \frac{k(k+1)}{2} + (k+1)\\
&=& \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\
&=&\frac{ (k+1)(k+2)}{2}
\end{eqnarray*}
And:
\begin{eqnarray*}
RHS(k+1) = \frac{ (k+1)(k+2)}{2}
\end{eqnarray*}
Therefore $LHS(k+1)=RHS(k+1)$, which validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n$.

\item \emph{Show that: $\forall n \in \mathbb{N}, \displaystyle \sum_{i=1}^{n}i^3 = \left( \displaystyle\frac{n(n+1)}{2} \right) ^2$}.

\vspace{0.1in}
\noindent \textbf{Proof:}

\vspace{0.1in}

Let $P(n)$ be the proposition: $\displaystyle\sum_{i=1}^{n}i^3 = \left( \displaystyle\frac{n(n+1)}{2} \right) ^2$. Let us also define $LHS(n) = \displaystyle\sum_{i=1}^{n}i^3$ and $RHS(n)=\left( \displaystyle\frac{n(n+1)}{2} \right) ^2$
\\
\begin{itemize}
\item \emph{Base case:} We show that $P(1)$ is true:
\begin{eqnarray*}
LHS(1) &=&\sum_{i=1}^{1} i^{3} = 1\\
RHS(1)&=&\left(\frac{1(1+1)}{2}\right)^{2} = \left(\frac{2}{2}\right)^{2}=1
\end{eqnarray*}
\\
\item \emph{Inductive step:} Let $k$ be a natural number, and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Let us compute $LHS(k+1)=\displaystyle\sum_{i=1}^{k+1}i^3$:\\
\begin{eqnarray*}
LHS(k+1) &=& \displaystyle\sum_{i=1}^{k} i^{3} + (k+1)^{3}\\
&=& \left(\frac{k(k+1)}{2}\right)^{2} + (k+1)^{3}\\
&=& \frac{k^{2}}{4}(k+1)^{2} + (k+1)(k+1)^{2}\\
&=& \frac{k^{2} + 4k + 4}{4} (k+1)^{2}\\
&=& \frac{(k+2)^{2}}{4} (k+1)^{2}\\
&=& \left(\frac{(k+1)(k+2)}{2}\right)^{2}
\end{eqnarray*}
And:
\begin{eqnarray*}
RHS(k+1) = \left( \frac{ (k+1)(k+2)}{2} \right)^2
\end{eqnarray*}
Therefore $LHS(k+1)=RHS(k+1)$, which validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n$.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Strong nInduction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Strong Mathematical Induction} 

There is another form of mathematical induction that is used to prove results: the method of strong mathematical induction, also called the second principle of mathematical induction.

\begin{framed}
\noindent A proof by strong induction that a proposition $P(n)$ is true for every natural number $n$ consists of two steps:
\begin{itemize}
\item \textbf{\emph{Basis step:}} The proposition $P(i)$ is true for a start position $i$ (usually $i=0$ or $i=1$)
\item \textbf{\emph{Inductive step:}} The implication $[P(i)\land P(i+1) \land \ldots \land P(k)] \to P(k+1)$ is shown to be true for very natural number $k \ge i$
\end{itemize}
\noindent The principle of proof by strong induction allows then to conclude that:
\begin{eqnarray*}
\forall n \in \mathbb{N}, n \ge i, P(n) \text{ is true}
\end{eqnarray*}
\end{framed}

Why would we need this?  Let us go back to the domino analogy. In the standard induction, we assumed that when domino $k$ falls, domino $k+1$ falls. But there could be situation in which this is not enough: the weight of domino $k$ alone is not enough to knock down domino $k+1$. But if we assume that all dominos up to $k$ have fallen, then the cumulative weight of the domino up to $k$ will lead to domino $k+1$ to fall. This is really an image, though. Strong induction is very much like standard induction, except that we use more information to prove the inductive step.

\vspace{0.1in}
\noindent \textbf{Examples:}

\begin{itemize}
\item [A)] \emph{A chocolate bar consists of $n$ unit squares arranged in a rectangular grid. You may split the bar into individual unit squares, by breaking along the lines. What is the number of breaks required?}.

\vspace{0.1in}
\noindent \textbf{Proof:}

We will show that the number of breaks needed is $n-1$. Let $P(n)$ be this proposition.
\begin{itemize}
\item [a)] \emph{Base case:} $P(1)$ is true: we need $0$ cuts to split a bar with a single square!
\item[b)] \emph{Inductive step:}

Let $k$ be a natural number, and let us suppose that $P(1)$, $P(2)$, $\ldots$, and $P(k)$ are all true. Let us consider now a chocolate bar with $k+1$ squares. We break it into two bars, one with $m_1$ squares, and one with $m_2$ squares. Note that 
\begin{align*}
m_1 \le k, \\
m_2 \le k, \\
m_1 + m_2 = k+1. 
\end{align*}
\noindent As $m_1 \le k$, $P(m_1)$ is true: to cut this bar we need $m_1-1$ cuts.

\noindent As $m_2 \le k$, $P(m_2)$ is true: to cut this bar we need $m_2-1$ cuts.

Therefore, to cut the bar with $k+1$ squares, we need $m_1-1 + m_2 -1 +1$ cuts (the +1 comes from the first cut!), namely $m_1+m_2 -1$ cuts, i.e. $(k+1)-1$ cuts, which proves $P(k+1)$.
\end{itemize}

\noindent The principle of proof by strong induction allows us to conclude that $P(n)$ is true for all $n$ natural number.

\item [B)] \emph{Consider a country with $n$ cities, such that there is a one way road between any two cities. Show that there is (at least) one path that goes through all cities}.

\vspace{0.1in}
\noindent \textbf{Proof:}

 Let $P(n)$ be this proposition.
\begin{itemize}
\item [a)] \emph{Base case:} $P(1)$ is trivially true!
\item[b)] \emph{Inductive step:}

Let $k$ be a natural number, and let us suppose that $P(1)$, $P(2)$, $\ldots$, and $P(k)$ are all true. Let us consider now that there are $(k+1)$ cities. We divide those cities into three groups:
\begin{itemize}
\item [a)] The city $C_{k+1}$, i.e. the additional city in the case we have $(k+1)$ city
\item [b)] The set of cities $A$, such that each city in $A$ has a one way road that leads to $C_{k+1}$
\item [c)] The set of cities $B$, such that $C_{k+1}$ has a road that leads to each city in $B$
\end{itemize}
This is possible as we know that $C_{k+1}$ has a road connecting it to any other cities, either \emph{from}, or \emph{to}.

\noindent The set $A$ is of size $k_A$. As $k_A \le k$, $P(k_A)$ is true and there is a path $P_A$ going through all the cities in $A$. Let $C_A$ be the city where this path ends.

\noindent The set $B$ is of size $k_B$. As $k_B \le k$, $P(k_B)$ is true and there is a path $P_B$ going through all the cities in $B$. Let $C_B$ be the city where this path starts.

\noindent We can now build a path through all $(k+1)$ cities: start with $P_A$, then connects $C_A$ at the end of this path with $C_{k+1}$ (which is possible based on the definition of $A$), then connects $C_{k+1}$ with $C_B$ (which is possible based on the definition of $B$) and finally follow the path $P_B$ from its start point $C_B$. Therefore $P(k+1)$ is true.

\end{itemize}
\noindent The principle of proof by strong induction allows us to conclude that $P(n)$ is true for all $n$ natural number.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Recursions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Recursive definitions} 

A recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the same set. This applies to sets that
are implicitly defined by a function.

\begin{framed}
\noindent We usually use two steps to define a function recursively:
\begin{itemize}
\item \textbf{\emph{Base case:}} Specify the value of the function at one, or a few start positions
\item \textbf{\emph{Inductive step:}} Give a rule for finding the value of the function at any integer value $n$, given its value at smaller integer values.
\end{itemize}
\end{framed}


\vspace{0.1in}
\noindent \textbf{Examples:}

\begin{itemize}
\item [A)] \emph{The factorial function $!n$ is often defined recursively, using the following rules:}.
\begin{itemize}
\item [] Base case: $0! = 1 $
\item [] Inductive step:  $(n+1)! = (n+1) \times n!$
\end{itemize}
\item [B)] \emph{The Fibonacci numbers are defined with the following rules:}.
\begin{itemize}
\item [] Base case: $f_0 = 0$ and $f_1 = 1$
\item [] Inductive step: $f_n = f_{n-1} + f_{n-2}$
\end{itemize}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Some proofs on Fibonacci
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Examples of proofs related to Fibonacci numbers} 

\begin{itemize}
\item [A)] \emph{Let $n$ be a natural number. Show that the proposition}
\begin{align*}
 P(n): f_1 + f_3 + \ldots + f_{2n-1} = f_{2n}
 \end{align*}
 \emph{is true for all $n$}.

\noindent Let us define:
\begin{eqnarray*}
LHS(n) &=&f_1 + f_3 + \ldots + f_{2n-1} \\
RHS(n) &=& f_{2n}
\end{eqnarray*}
we want to show that
\begin{eqnarray*}
\forall n \in \mathbb{N}, LHS(n) = RHS(n)
\end{eqnarray*}
We use an induction proof.
\begin{itemize}
\item [i)] Base case: $LHS(1) = f_1 = 1$ and $RHS(1) = f_2 = f_1 + f_0 = 1$. Therefore $LHS(1) = RHS(1)$.
\item [ii)] Inductive step:  Let $k \ge 1$ and let us assume that $LHS(k) = RHS(k)$. Then,
\begin{eqnarray*}
LHS(k+1) &=& f_1 + f_3 + \ldots + f_{2k-1} + f_{2k+1} \\
&=& LHS(k) + f_{2k+1} \\
&=& RHS(k) + f_{2k+1} \\
&=& f_{2k} + f_{2k+1} \\
&=& f_{2k+2}
\end{eqnarray*}
and $RHS(k+1) = f_{2k+2}$. Therefore $LHS(k+1) = RHS(k+1)$.
\end{itemize}
\noindent The principle of proof by induction allows us to conclude that $LHS(n)=RHS)n)$ is true for all $n$ natural number.

\item [B)] \emph{Let $n$ be a natural number. Show that the proposition}\\
\begin{align*}
P(n): f_{n-1}f_{n+1} - f_n^2 =(-1)^n
 \end{align*}
 \emph{is true for all $n$}.
 
\noindent Let us define:
\begin{eqnarray*}
LHS(n) &=& f_{n-1}f_{n+1} - f_n^2 \\
RHS(n) &=& (-1)^n
\end{eqnarray*}
we want to show that
\begin{eqnarray*}
\forall n \in \mathbb{N}, LHS(n) = RHS(n)
\end{eqnarray*}
We use an induction proof.
\begin{itemize}
\item [i)] Base case: $LHS(1) = f_0f_2 - f_1^2 = 0\times 1 - 1^2 = -1$ and $RHS(1) = (-1)^1= -1$. Therefore $LHS(1) = RHS(1)$.
\item [ii)] Inductive step:  Let $k \ge 1$ and let us assume that $LHS(k) = RHS(k)$. Then,
\begin{eqnarray*}
LHS(k+1) &=& f_{k}f_{k+2} - f_{k+1}^2
\end{eqnarray*}
We know that $f_{k+2} = f_{k+1} + f_k$:
\begin{eqnarray*}
LHS(k+1) &=& f_k ( f_{k+1}+f_k ) - f_{k+1}^2 \\
&=& f_k f_{k+1} + f_k^2 - f_{k+1}^2 \\
\end{eqnarray*}
We know that $LHS(k) = RHS(k)$:
\begin{eqnarray*}
f_{k-1}f_{k+1} - f_{k}^2 = (-1)^k
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
 f_{k}^2 = f_{k-1}f_{k+1} - (-1)^k
\end{eqnarray*}
Replacing above,
\begin{eqnarray*}
LHS(k+1) &=& f_k f_{k+1} + f_{k-1}f_{k+1} - (-1)^k - f_{k+1}^2 \\
&=& f_{k+1} ( f_k + f_{k-1} -f_{k+1} ) -(-1)^k
\end{eqnarray*}
The first term on the right is equal to 0, based on the inductive definition of Fibonacci numbers. Therefore $LHS(k+1) = -(-1)^k = (-1)^{k+1}$.
Since $RHS(k+1) = (-1)^{k+1}$, we have shown that $LHS(k+1) = RHS(k+1)$.
\end{itemize}
\noindent The principle of proof by induction allows us to conclude that $LHS(n)=RHS)n)$ is true for all $n$ natural number.

\end{itemize}
\end{document}