Skip to main content
Contents Index Dark Mode Prev Up Next \(\newcommand{\im}{{\mathrm{im}}}
\newcommand{\given}{{\, :\,}}
\newcommand{\hanoi}{\mathrm{hanoi}}
\newcommand{\lcm}{{\mathrm{lcm}}}
\newcommand{\ID}{{\mathrm{ID}}}
\newcommand{\chr}{{\mathtt{chr}}}
\newcommand{\ord}{{\mathtt{ord}}}
\newcommand{\set}[1]{\left\lbrace #1 \right\rbrace}
\newcommand{\seq}[2]{( #1 )_{#2}}
\newcommand{\gr}[1]{\left( #1 \right)}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\size}[1]{\# #1}
\newcommand{\id}[1]{\mathrm{id}_{#1}}
\newcommand{\ip}[1]{\left\langle #1 \right\rangle}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceiling}[1]{\left\lceil #1\right\rceil}
\newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}}
\renewcommand{\implies}{\to}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\lxor}{\oplus}
\newcommand{\cP}{\wp}
\newcommand{\pset}{\cP}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\barr}[1]{\overline{#1}}
\newcommand{\sage}{\textsc{Sage}}
\newcommand{\magma}{\textsc{Magma}}
\newcommand{\bob}{\text{Bob}}
\newcommand{\true}{\text{T}}
\newcommand{\false}{\text{F}}
\newcommand{\ahat}{\hat{a}}
\newcommand{\ah}{\ahat}
\newcommand{\bhat}{\hat{b}}
\newcommand{\abar}{\bar{a}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\todo}[1]{{\color{red} TODO: #1}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\def\dbend{{!!!}}
\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\,}$}}}
\)
Subsection 3.1.1 Propositional functions revisited
We often use propositional functions in our induction proofs. Recall that a propositional function is a function that outputs a proposition for each input. It is important to distinguish the parts of the proposition that is represented by a propositional functions and the values of a propositional function at the elements of its domain. The value of a propositional function evaluated at an element of its domain is always true or false.
Example 3.1.1.1 . Propositional function.
Let \(P(n)\) be the proposition “\(\sum_{i=1}^n i=\frac{n\cdot (n+1)}{2}\) ” where \(n\in\NN\text{.}\)
\(P(2)\) is
\(\sum_{i=1}^2 i=\frac{2\cdot (2+1)}{2}\text{.}\) We have that
\(P(2)\) is true as both sides of the equality evaluate to
\(3\text{.}\)
`
\(P(2)=\sum_{i=1}^2 i\) ’ and `
\(P(2)=\frac{2\cdot (2+1)}{2}\) ’ do not make sense because the right hand sides both evaluate to
\(3\text{,}\)
Mathematical induction can be used to prove statements that assert
\(P(n)\) is true for all positive integers
\(n\text{.}\)
Example 3.1.1.2 . Inductive reasoning.
Let \(P\) be a propositional function with domain \(\NN\text{.}\) We are told that
if
\(k\in\NN\) and
\(P(k)\) is true then
\(P(k+1)\) is true.
For which natural numbers \(n\) do you know that \(P(n)\) is true ? We have
Because
\(P(1)\) is true also
\(P(1+1)=P(2)\) is true by (
Item 2 ).
Because
\(P(2)\) is true also
\(P(2+1)=P(3)\) is true by (
Item 2 ).
Because
\(P(3)\) is true also
\(P(3+1)=P(4)\) is true by (
Item 2 ).
Continuing this pattern we find that by (
Item 2 )
\(P(k)\) is true for all following natural numbers. That is,
\(P(n)\) is true for all
\(n\in\NN\text{.}\)
Example 3.1.1.3 . Inductive reasoning.
Let \(Q(n)\) be a propositional function with domain \(\NN\text{.}\) Suppose
Let
\(k\in\NN\text{.}\) If
\(Q(k)\) is true then
\(Q(k+2)\) is true.
For which \(n\in\NN\) do we know that \(Q(n)\) is true ? We have
Because
\(Q(0)\) is true also
\(Q(0+2)=Q(2)\) is true by (
Item 2 ).
Because
\(Q(2)\) is true also
\(Q(2+2)=Q(4)\) is true by (
Item 2 ).
Because
\(Q(4)\) is true also
\(Q(4+2)=Q(6)\) is true by (
Item 2 ).
Continuing this pattern we find that by (
Item 2 )
\(Q(8)\) is true,
\(Q(10)\) is true,
\(Q(12)\) is true, and so on. So, with the information given we can conclude that
\(Q(n)\) is also true for all following even natural numbers. Thus
\(Q(n)\) is true for all
\(n\in\{0,2,4,6,8,10,12,\dots\}\text{.}\)
