AC Mathematical Induction

Skip to main content

\(\newcommand{\set}[1]{\{1,2,\dotsc,#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{\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\,}$}}} \)

Section 3.6 Mathematical Induction

Now we move on to induction, the powerful twin of recursion.

Let \(n\) be a positive integer. Consider the following mathematical statements, each of which involve \(n\text{:}\)

\(2n+7 = 13\text{.}\)

🔗
\(3n-5=9\text{.}\)

🔗
\(n^2-5n+9=3\text{.}\)

🔗
\(8n-3 \lt 48\text{.}\)

🔗
\(8n-3 > 0\text{.}\)

🔗
\((n+3)(n+2) =n^2+5n+6\text{.}\)

🔗
\(n^2 -6n + 13 \ge 0\text{.}\)

🔗

Such statements are called open statements. Open statements can be considered as equations, i.e., statements that are valid for certain values of \(n\text{.}\) Statement 1 is valid only when \(n=3\text{.}\) Statement 2 is never valid, i.e., it has no solutions among the positive integers. Statement 3 has exactly two solutions, and Statement 4 has six solutions. On the other hand, Statements 5, 6 and 7 are valid for all positive integers.

At this point, you are probably scratching your head, thinking that this discussion is trivial. But let’s consider some statements that are a bit more complex.

The sum of the first \(n\) positive integers is \(n(n+1)/2\text{.}\)
🔗

🔗
The sum of the first \(n\) odd positive integers is \(n^2\text{.}\)
🔗

🔗
\(n^n \ge n! + 4,000,000,000n2^n\) when \(n\ge 14\text{.}\)
🔗

🔗

How can we establish the validity of such statements, provided of course that they are actually true? The starting point for providing an answer is the following property:

Principle 3.11. Principle of Mathematical Induction.

Let \(S_n\) be an open statement involving a positive integer \(n\text{.}\) If \(S_1\) is true, and if for each positive integer \(k\text{,}\) assuming that the statement \(S_k\) is true implies that the statement \(S_{k+1}\) is true, then \(S_n\) is true for every positive integer \(n\text{.}\)

With a little thought, you should see that the Principle of Mathematical Induction is logically equivalent to the Well Ordered Property of the Positive Integers. If you haven’t already done so, now might be a good time to look over Appendix B on background material.