# Real Analysis

Induction

Let $$\mathbb{N} = \{1, 2, 3, \dots\}$$, the natural numbers.

# The Well-Ordering Property

The well-ordering property of $$\mathbb{N}$$: every non-empty subset of $$\mathbb{N}$$ has a least element. It can be taken as an axiom of $$\mathbb{N}$$.

# Principle of Induction

Let $$S \subset \mathbb{N}$$ such that

1. $$1 \in S$$, and
2. if $$k \in S$$ then $$k + 1 \in S$$.

Then $$S = \mathbb{N}$$.

The well-ordering property is equivalent to the principle of induction.

Proof that the well-ordering property implies the principle of induction (by contradiction). Suppose $$S$$ exists with the given properties but $$S \neq \mathbb{N}$$.

Let $$A := \mathbb{N} \setminus S$$, so it is non-empty. Then $$A$$ has a least element by the well-ordering property, call it $$n$$. Notice $$n > 1$$ because $$1 \in S$$ which implies $$1 \notin A$$.

Consider $$n - 1$$. It is not in $$A$$ because $$n$$ is the least element. So $$n - 1 \in S$$. By property (2), $$n - 1 + 1 \in S$$, which implies $$n \in S$$. This is a contradiction because $$n \in A$$.

Therefore, the well-ordering property implies the principle of induction. QED.

Proof that the principle of induction implies the well-ordering property (by induction on the number of elements in the subset). Let $$S$$ be a subset of $$\mathbb{N}$$ and $$n$$ be the number of elements in $$S$$.

For the base case where $$n = 1$$, the least element of any subset $$S$$ is the only element it has, so the base case holds.

For the inductive step, assume for all subsets $$S$$ of $$\mathbb{N}$$ with size $$n$$, each has a least element. Consider a subset $$S$$ of $$\mathbb{N}$$ with size $$n + 1$$ and a subset $$S'$$ of $$S$$ with size $$n$$. By the inductive hypothesis, $$S'$$ has a least element; call it $$a$$. Let $$b$$ is the only element in $$S$$ that is not in $$S'$$. Since $$\mathbb{N}$$ is ordered, either $$a < b$$, $$a = b$$, or $$a > b$$, by law of trichotomy. When $$a < b$$, $$a$$ is a least element of $$S$$. When $$a = b$$, $$a$$ is also a least element of $$S$$. When $$a > b$$, $$b$$ is less than all elements of $$S'$$, so $$b$$ is a least element of $$S$$.

Therefore, the principle of induction implies the well-ordering property. QED.

# Proof by Induction

Let $$P(n)$$ be statements indexed by the natural numbers $$\mathbb{N}$$. To show that $$P(n)$$ is true for all $$n$$, we must show

1. (base case) $$P(1)$$ is true, and
2. (inductive step) if $$P(k)$$ is true then $$P(k + 1)$$ is true.

Then, by the principle of induction, $$P(n)$$ is true for all $$n$$.

The statement $$P(k)$$ is true is called the inductive hypothesis.

# Strong Induction

Let $$P(n)$$ be statements indexed by the natural numbers $$\mathbb{N}$$. To show that $$P(n)$$ is true for all $$n$$, we must show

1. (base case) $$P(1)$$ is true, and
2. (inductive step) if $$P(1)$$ through $$P(k)$$ are true then $$P(k + 1)$$ is true.

Then, by the principle of strong induction, $$P(n)$$ is true for all $$n$$.

For example, every $$2^n \times 2^n$$ chessboard with one square removed can be tiled by L-shaped tiles.

Proof (by induction on $$n$$).

For base case, a $$2 \times 2$$ board