Using natural numbers is our first mathematical abstraction as children. Mathematical induction is an important technique of proof.

Click on an **arrow** to get a description of the connection!

Click on an **arrow** to get a description of the connection!

__Show requirements__

Concept |
Content |

Sets |
Sets are the basic building blocks for a lot of mathematics. In order to rigorously define numbers and doing real analysis, we need to know how to work with sets. |

__Show consequences__

Concept |
Content |

Sums and Products |
An important shorthand notation for calculations. |

Sequences |
These object are needed to define limits later on. |

Countable Sets |
A notion of cardinality that covers finite sets and those that can be enumerated via the natural numbers. |

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\).

#### Discuss your questions by typing below.