Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 3.2 Principle of Mathematical Induction
Axiom 3.1 . Principle of Mathematical Induction.
Let
\(S_{n}\) be an open statement involving a positive integer
\(n\text{.}\) If
\(S_{1}\) is true, and for every positive integer
\(k\text{,}\) the statement
\(S_{k+1}\) is true whenever
\(S_{k}\) is true, then
\(S_{n}\) is true for every positive integer
\(n\text{.}\)
Key Parts of an Inductive Proof.
When trying to prove an open statement \(S_{n}\) is true for all positive integers \(n\) by mathematical induction, the key steps are
Basis Step
Show that
\(S_{1}\) is true.
Inductive step
Show that
if for some
\(k\geq 1\text{,}\) \(S_{k}\) is true, then
\(S_{k+1}\) is true.
PI questions: getting started, after basis step, after IH.
Theorem 3.2 .
For all positive integers
\(n\text{,}\) \(\displaystyle \sum_{i=1}^{n} (4i-3) = n(2n-1)\text{.}\)
Proof.
Activity 3.2.1 .
(a)
Recall that we have defined \(r(n)\) to be the number of regions in the plane determined by \(n\) lines arranged so that (1) each pair of lines intersects and (2) no three lines intersect at a single point and argued that \(r(1) = 2\) and for \(n\geq 2\text{,}\) \(r(n) = r(n-1) + n\text{.}\) Prove that for all positive integers \(n\text{,}\)
\begin{equation*}
r(n) = \binom{n+1}{2}+1\text{.}
\end{equation*}
(b) We say that an integer
\(a\) divides an integer
\(b\) provided that there exists an integer
\(m\) such that
\(b=ma\text{.}\) Prove that for all integers
\(n\geq 1\text{,}\) \(4\) divides
\(5^{n}-1\text{.}\)
(c)
Let \(f(1)=5\text{,}\) \(f(2) = 13\text{,}\) and for all integers \(n\geq 3\text{,}\)
\begin{equation*}
f(n)=5f(n-1)-6f(n-2).
\end{equation*}
Prove that an explict formula for \(f(n)\) is given by \(f(n)=2^{n}+3^{n}\text{.}\)
