Natural Numbers and Induction
Using natural numbers is our first mathematical abstraction as children. Mathematical induction is an important technique of proof.
Discover Bridges
Study Natural Numbers and Induction
The natural numbers are \(\mathbb{N} = \{1,2,3 \ldots \}\).
Using natural numbers is our first mathematical abstraction. We learn this as children in the kindergarden.
What is this abstraction? A number is an abstraction for all finite sets of the same size.
Question 1: When are two sets \(S,T\) of the same size? Have the same cardinality \(|S|=|T|\)? Answer: They have the same size if there is a bijective map \(S\to T\).
Question 2: When is a set \(S\) finite? Answer: It is finite if removing one element changes the cardinality of \(S\).
In mathematical language: “Natural numbers are equivalence classes of finite sets of the same cardinality.”
Mathematical induction
Mathematical induction is an important technique of proof: Proof step by step. It is a close relative to recursion in computer science:
“Assume I can solve a problem of size \(n\). How can I solve one of size \(n+1\)?”
In mathematics:
“If an assertion is true for \(n\), show that it is true for \(n+1\)”
Example 1. What is the sum of the first \(n\) natural numbers? \[s_n := \sum_{k=1}^n k = \,?\]
To make this practical, we need three ingredients:
An idea what the result could be. (Induction hypothesis)
The verification that our hypothesis is true for \(n=1\) (Base case)
A proof, that if it holds for \(n\), then also for \(n+1\). (Induction step)
Ideas? Let’s take the hypothesis \[s_n = \frac{(n+1)n}{2}\qquad \mbox{ (Induction hypothesis). }\] Very good! We can verify our formula for these examples. In particular: \[s_1 = \frac{(1+1)1}{2}=1 \qquad \mbox{ (Base case). }\] Induction step: We have to show \[\frac{(n+2)(n+1)}{2} \mbox{ is equal to } s_{n+1}=s_n + (n+1) = \frac{(n+1)n}{2}+n+1\] where we used the induction hypothesis in the last step. So let us compute: \[\begin{aligned} s_n + (n+1) = \frac{(n+1)n}{2}+n+1&=\frac{n^2+n+2n+2}{2} = \frac{(n+2)(n+1)}{2} \,. \end{aligned}\] This proves that \(s_n = \frac{(n+1)n}{2}\) for all \(n \in \mathbb{N}\).
Rule of Thumb 2 (Mathematical induction). To show that the predicate \(A(n)\) is true \(n \in \mathbb{N}\), we have to show two things:
Show that \(A(1)\) is true.
Show that \(A(n+1)\) is true under the assumption that \(A(n)\) is true.
Sometimes it can happen that a claim \(A(n)\) is indeed false for finitely many natural numbers, but it is eventually true. This means that the base case cannot be shown for \(n=1\) but for some other natural number \(n_0 \in \mathbb{N}\). Then the induction proof shows that \(A(n)\) is true for all natural number \(n \geq n_0\).
Courtesy of Marcus Waurick. Well-defined & Wonderful podcast, marcus-waurick.de.
Discuss your questions by typing below.
Solve the WeBWorK Exercise
The data for the interactive network on this webpage was generated with pntfx Copyright Fabian Gabel and Julian Großmann. pntfx is licensed under the MIT license. Visualization of the network uses the open-source graph theory library Cytoscape.js licensed under the MIT license.