%% Created by Maple V Release 4 (APPLE_PPC_MAC)
%% Source Worksheet: Induction.mws
%% Generated: Sat Nov  2 09:14:21 1996
%\documentclass{article}
%\usepackage{maple2e}
%\DefineParaStyle{Heading 1}
%\DefineParaStyle{Heading 2}
%\DefineParaStyle{Maple Output}
%\DefineParaStyle{Title}
%\DefineCharStyle{2D Comment}
%\DefineCharStyle{2D Math}
%\DefineCharStyle{2D Output}
%\DefineCharStyle{Hyperlink}
%\begin{document}

\begin{maplegroup}
\begin{Title}
\QTR{Hyperlink}{Real Analysis with Maple}
\end{Title}

\end{maplegroup}

\setcounter{section}{1}
\section{The Principal of Mathematical Induction}

One of the most powerful techniques of proof is Mathematical
Induction.

\textbf{Theorem.} Let 
\mapleinline{inert}{2d}{P(n)}{%
${\rm P}(n)$%
} be a statement about the positive integer 
\mapleinline{inert}{2d}{n}{%
$n$%
} such that\\
\hspace*{1.1in}\textit{Basis}:       
\mapleinline{inert}{2d}{P(1)}{%
${\rm P}(1)$%
} is true\\
\hspace*{1.1in}\textit{Induction}: If 
\mapleinline{inert}{2d}{P(k)}{%
${\rm P}(k)$%
} is true, then 
\mapleinline{inert}{2d}{P(k+1)}{%
${\rm P}(k + 1)$%
} must also be true.\\
\hspace*{0.9in}Then 
\mapleinline{inert}{2d}{P(n)}{%
${\rm P}(n)$%
} is true for every positive integer 
\mapleinline{inert}{2d}{n}{%
$n$%
}.

Each Induction proof contains two main sections. The Basis Step is
where the statement P(n) is validated for a specific positive integer,
typically, but not necessarily, for n=1. The Induction Step is where
the conditional �If P(k) is true, then P(k+1) must also be true� is
shown to be valid. The first application of Mathematical Induction
considered is usually formulas for sums.

\subsection{Summation Formulas}

Summation formulas follow the standard template for induction proofs:
Esablish the Basis. Algebraically verify the Induction.

Define the proposition.

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{P := n -> 
  Sum(k^2, k=1..n) = sum(k^2, k=1..n);}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
P := n\rightarrow {\displaystyle \sum _{k=1}^{n}} \,k^{2}=
{\displaystyle \sum _{k=1}^{n}} \,k^{2}
\]
\end{maplelatex}

\end{maplegroup}
First, the Basis.

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{P(1), evalb(value("));}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\displaystyle \sum _{k=1}^{1}} \,k^{2}=1, \,{\it true}
\]
\end{maplelatex}

\end{maplegroup}
Now for the Induction.

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{P(n) + ((n+1)^2=(n+1)^2);}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
({\displaystyle \sum _{k=1}^{n}} \,k^{2}) + (n + 1)^{2}=
{\displaystyle \frac {1}{3}} \,(n + 1)^{3} + {\displaystyle 
\frac {1}{2}} \,(n + 1)^{2} + {\displaystyle \frac {1}{6}} \,n + 
{\displaystyle \frac {1}{6}} 
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{factor(");}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
({\displaystyle \sum _{k=1}^{n}} \,k^{2}) + n^{2} + 2\,n + 1=
{\displaystyle \frac {1}{6}} \,(2\,n + 3)\,(n + 2)\,(n + 1)
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{factor(P(n+1));}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\displaystyle \sum _{k=1}^{n + 1}} \,k^{2}={\displaystyle 
\frac {1}{6}} \,(2\,n + 3)\,(n + 2)\,(n + 1)
\]
\end{maplelatex}

\end{maplegroup}
So the Induction holds. That is, by the PMI,

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{factor(P(n));}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\displaystyle \sum _{k=1}^{n}} \,k^{2}={\displaystyle \frac {1}{
6}} \,n\,(n + 1)\,(2\,n + 1)
\]
\end{maplelatex}

\end{maplegroup}
is true for all for all positive integers 
\mapleinline{inert}{2d}{n}{%
$n$%
}.

\subsection{Binomial Coefficients}

Pascal's Triangle shows many relations between sums and binomial
coefficients.

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{matrix(10,10, (i,j) -> binomial(i-1,j-1));}{%
}
\end{mapleinput}

\end{maplegroup}
\textbf{Proposition}. 

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{Sum(k, k=1..n-1) = binomial(n,2);}{%
}
\end{mapleinput}

\end{maplegroup}
\textbf{Proposition}. 

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{Sum(k^2, k=1..n-1) =
  binomial(n,2) + 2*binomial(n,3)}{%
}
\end{mapleinput}

\end{maplegroup}

\subsection{Additional Activities}

Students can be asked to investigate inequalities. E.g.:

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{P := n -> 3^n < n!;}{%
}
\end{mapleinput}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{P := n -> 1+n*x < (1+x)^n;}{%
}
\end{mapleinput}

\end{maplegroup}
Or, for the adventurous,

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{P := n -> 
1+sum(a[i],i=1..n)<=product(1+a[i],i=1..n);}{%
}
\end{mapleinput}

\end{maplegroup}
%\end{document}
%% End of Maple V Output
