Induction

Well Ordering Principle

Given an subset

S \subseteq ℕ_{1}

, if

S \neq \emptyset

then

S

has a minimum value

Taken as an axiom.

Empty Negation Set means True for Everything

Let

P

be a predicate then for any

X \subseteq dom (P)

C : = {x \in X : \neg P (x)} = \emptyset

implies that

\forall x \in X, P (x)

Let

a \in X

, suppose that

\neg P (a)

for a contradiction, but then

a \in C

so that

C \neq \emptyset

which is a contradiction, so we know that

P (a)

as needed.

Triangular Numbers with the Well Ordering Principle

Prove that

1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2}

Let $P (n)$ be the predicate which claims that $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2}$ , and define the set $C = {n \in ℕ_{1} : \neg P (n)}$ , by showing that this set is empty, then it holds true for all $n \in ℕ_{1}$ .

Therefore by contradiction assume that the set $C$ is not empty, thus by the well ordering principle it has a smallest element $m \in C$ , note that $m \geq 2$ because $P (1)$ holds therefore $m - 1 \notin C \cap ℕ_{0}$ which means that $P (m - 1)$ which implies that $1 + 2 + \dots + (m - 1) = \frac{(m - 1) m}{2}$ then by simply adding $m$ to both sides we get that $1 + 2 + \dots + m = \frac{m^{2} - m + 2 m}{2} = \frac{m^{2} + m}{2} = \frac{m (m + 1)}{2}$ so thefore $P (m)$ holds, which is a contradiction so therefore $S = \emptyset$ as needed.

There is Not an Infinitely Strictly Decreasing Sequence of Natural Numbers

There does not exist a sequence

x_{1} > x_{2} > \dots

in the natural numbers.

Suppose for the sake of contradiction that such a sequence did exist, and let

S

be the set of values of the sequence, by definition

S \subseteq ℕ_{0}

we assumed our sequence has at least one value and therefore

S \neq \emptyset

and so by the well ordering principle it has a least element say

x_{k}

for

k \in ℕ_{0}

but then we know that

x_{k} > x_{k + 1}

which is a contradiction, so such as sequence must not exist.

Archimedean Property

For any

x, y \in ℕ_{1}

there is some

n \in ℕ_{1}

such that

n x \geq y

Take

n = y

, since

x \in ℕ_{1}

then

1 \leq x

so that

y = y (1) \leq y x = n x

Induction

Suppose we have a predicate

P : ℕ_{0} \to {T, F}

, then if we know that

$P (0)$
For any $k \in ℕ_{0}, P (k) ⟹ P (k + 1)$

then

P (n)

holds for every

n \in ℕ_{0}

Let $S : = {n \in ℕ_{0} : \neg P (n)}$ if the principle of induction holds true, then this set must be empty, assume for the sake of contradiction that it is non-empty.

If this set is not empty then we have some $a \in ℕ_{0}$ such that $\neg P (a)$ holds true, therefore by the well ordering principle we know that $S$ has a minimal element, which we will denote by $m$ and note that $m \geq 1$ because $P (0)$ holds true , so that so that $m - 1 \in ℕ_{0}$ and it is minimal so that $m - 1 \notin S$ so by definition of $S$ it means that $P (m - 1)$ holds true, but then by the second property of induction we obtain that $P (m)$ holds true, so therefore $m \notin S$ which is a contradiction.

Therefore since by assuming that $S$ is non-empty we get a contradiction, it must mean that $S$ is empty, which means that for every $n \in ℕ_{0}$ we have that $P (n)$ holds true, as needed.

There is a Source and a Sink

Suppose you are in a country where all roads between any two cities are on-way and when you leave a city you cannot return to it again. Prove that there exists a city into which all roads enter and a city from which all roads exit.

Let $P (n)$ be the predicate that the statement holds true on a graph with $n$ vertices. We will show this is true via induction over $ℕ_{2}$ .

For the base case, we have two vertices $s, t$ , if there are no edges between them it holds vacuously, note that the only other case is that there is one edge, because if there were two then they could only be formed of the edges $(s, t), (t, s)$ which would contradict that there is no way to return back to a city you were previously at. Therefore without loss of generality assume that the only edge is $(s, t)$ , in that case the statement holds true because $t$ is the city into which all roads enter and $s$ is the city from which all roads exit.

For the induction step assume the prediate holds true for $k \in ℕ_{2}$ and we'll prove that it holds true on $k + 1$ , so supposing we have a graph with $k + 1$ nodes, let's obtain the graph by removing one vertex $x$ and all edges it's involved in, by induction this subgraph has an $s, t$ such that all roads enter $s$ and all roads exit $t$ , specifically note that this implies that the edge $(x, s)$ and $(t, x)$ exist in the original graph that contained $x$ .

Note that by re-adding in $x$ the property would be maintained unless $x$ had an edge $(s, x)$ , but this would be impossible because the graph has the property that when you leave a city you cannot return to it again, but if we have $(x, s), (s, x)$ the path $x - s - x$ contradicts this fact, similarly if an edge $(x, t)$ existed we also get this contradiction, therefore such edges must not exist which shows that the predicate holds true on the graph containing $x$ by using $s$ as the sink and $t$ as the source.

Triangular Number

We define the triangular numbers by

$T_{1} = 1$
$T_{n} = T_{n - 1} + n$

They are called triangular numbers because by stacking dots of consecutive integers it forms a triangle.

Formula for the Triangular Numbers

For any

n \in ℕ_{1}

we have that

T_{n} = \frac{n \cdot (n + 1)}{2}

By definition we know that $T_{1} = 1$ , by the equation we get $\frac{1 \cdot 2}{2} = 1$ , therefore the base case holds true.

Let $k \in ℕ_{1}$ and assume that $T_{k} = \frac{k \cdot (k + 1)}{2}$ , let's show that $T_{k + 1} = \frac{(k + 1) \cdot (k + 2)}{2}$ . $\begin{matrix} T_{k + 1} & a m p; = T_{k} + (k + 1) \\ a m p; = \frac{k^{2} + k}{2} + \frac{2 k 2}{2} \\ a m p; = \frac{k^{2} + 3 k 2 k}{2} \\ a m p; = \frac{(k + 1) (k + 2)}{2} \end{matrix}$

Telescoping Sum

Let

(a_{n})

be a sequence of real numbers, then

\sum_{k = 1}^{n} (a_{k + 1} - a_{k}) = a_{n + 1} - a_{1}

for any

n \in ℕ_{1}

We show this true by induction over $ℕ_{1}$ so for the base case note that $\sum_{k = 1}^{1} (a_{k} - 1 - a_{k}) = a_{2} - a_{1}$ as needed.

Now suppose that it holds true for $j \in ℕ_{1}$ and now let's prove that $\sum_{k = 1}^{j + 1} (a_{k + 1} - a_{k}) = a_{(j + 1) + 1} - a_{1}$ but observe that $\begin{matrix} \sum_{k = 1}^{j + 1} (a_{k + 1} - a_{k}) & a m p; = \sum_{k = 1}^{j} (a_{k + 1} - a_{k}) + (a_{j + 2} - a_{j + 1}) \\ a m p; = (a_{j + 1} - a_{1}) + a_{j + 2} - a_{j + 1} \\ a m p; = a_{j + 2} - a_{1} \end{matrix}$

Formula for n-term arithmetic Progression

Let

a, d \in ℝ

, then

a + (a + d) + (a + 2 d) + \dots + (a + (n - 1) d) = \frac{n (2 a + (n - 1) d)}{2}

for every

n \in ℕ_{1}

By do it by induction, for the base case we need to verify that $a = \frac{1 (2 a + 0 d)}{2}$ which is true because the right hand side simplifies to $a$ .

Now suppose the formula holds true for $k \in ℕ_{1}$ and we'll show it holds true for $k + 1$ . $\begin{matrix} a + (a + d) + (a + 2 d) + \dots + (a + ((k + 1) - 1) d) & a m p; = a + (a + d) + (a + 2 d) + \dots + (a + (k - 1) d) + (a + k d) \\ a m p; = \frac{k (2 a + (k - 1) d)}{2} + (a + k d) \\ a m p; = \frac{k (2 a + (k - 1) d) + 2 a + 2 k d}{2} \end{matrix}$

For a moment let's focus on the numerator, we want to show that the numerator is equal to $(k + 1) (2 a + k d) = k (2 a + k d) + (2 a + k d)$ , towards this goal notice that $\begin{matrix} k (2 a + (k - 1) d) + 2 a + 2 k d & a m p; = 2 k a + k^{2} d - k d + 2 a + 2 k d \\ a m p; = 2 k a + k^{2} d + 2 a + k d \\ a m p; = k (2 a + k d) + 2 a + k d \\ a m p; = (k + 1) (2 a + k d) \end{matrix}$ and so the numerator is correct and the entire formula holds true.

With $a = d = 1$ then we get the sequence $1, 3, 5, 7, \dots$ (the triangular numbers) which recovers the formula for the triangular numbers that was discovered earlier.

Summation of Consecutive Odd Numbers

1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

We have an arithmetic progression where

a = 1

and

d = 2

, therefore its value is given by

\frac{n (2 + (n - 1) 2)}{2} = n^{2}

Sum of the Squares of Consecutive Integers

1^{2} + 2^{2} + 3^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}

Multiplying by a non Negative Constant Retains Inequality

Suppose that

a \geq b \in ℝ

and that

c \in ℝ^{> 0}

then

a c \geq b c

The Square of a Real Number is Non-Negative

For any

x \in ℝ

x^{2} \geq 0

Bernouilli's Inequality

For any

x \in (- 1, \infty)

and

n \in ℕ_{0}

we have

{(1 + x)}^{n} \geq 1 + n x

Let $n = 0$ , then we have that ${(1 + x)}^{0} = 1$ and $1 + 0 x = 1$ so the inequality holds true.

Suppose the inequality holds true for $k \in ℕ_{0}$ , we'd like to show it holds true for $k + 1$ which is to say that $1 + (k + 1) x \leq {(1 + x)}^{k + 1}$ , on the other hand see that: $\begin{matrix} {(1 + x)}^{k} & a m p; = {(1 + x)}^{k + 1} \\ a m p; = {(1 + x)}^{k} (1 + x) \\ a m p; \geq (1 + k x) (1 + x) \\ a m p; = 1 + (k + 1) x + k x^{2} \\ a m p; \geq 1 + (k + 1) x \end{matrix}$ To get the third line we used the induction hypothesis along with this fact because we know that $x + 1 > 0$ since $x \in (- 1, \infty)$ , to get to the last line we used this fact

Strong Induction

Suppose we have a predicate

P : ℕ_{0} \to {T, F}

, then if we know that for every

k \in ℕ_{0}

(P (0) \land \dots \land P (k - 1)) ⟹ P (k)

then for every

n \in ℕ_{0}

we have that

P (n)

holds true.

Let $Q (n)$ be the predicate that $P (j)$ holds true for $0 \leq j \leq n$ . We want to prove that $Q (0)$ holds true, which is equivalent to $P (0)$ being true. Observe that for $k = 0$ the assumption of strong induction states that $(P (0) \land \dots \land P (- 1)) ⟹ P (0)$ but we know that $P (0) \land \dots \land P (- 1)$ holds true, therefore $P (0)$ holds.

Let $k \in ℕ_{0}$ and assume that $Q (k)$ holds true, therefore $P (j)$ holds true for $1 \leq j \leq k$ since $P$ satisfies the property stated in the statement we are trying to prove, we get that $P (k + 1)$ holds, which shows that $Q (k + 1)$ is true.

Therefore by the principle of induction we see that $Q (n)$ holds true for every $n \in ℕ_{0}$ , this implies that $P (n)$ holds true for every $n \in ℕ_{0}$ as well, therefore the statement of strong induction is proven.

Strong Induction Implies The Well Ordering Principle

Strong induction implies the well ordering principle

Assume the strong induction holds, we want to prove that given any non-empty set $S \subseteq ℕ_{0}$ then it has a minimum element, we will show this is true by the contrapositive, so assume that $S$ has no min element and we'll show that $S$ is empty.

Let $P (n)$ be the predicate which claims that $n \notin S$ . Since $S$ is bounded below by $0$ then if $0 \in S$ then it would be the least element, so $0 \notin S$ , which shows that $P (0)$ holds.

Let $k \in ℕ_{0}$ and that $p (0) \land \dots \land p (k)$ hold true, note that this means that $0, 1, \dots k \notin S$ , we'll show that $p (k + 1)$ is true. For contradiction suppose that it does not, which means that $k + 1 \in S$ , but since nothing before it is in the set, then that would make it the minimum element, but $S$ has no minimum element, given this contradiction we know that $k + 1 \notin S$ and therefore $P (k + 1)$ is true, thus by strong induction, we know that $P (n)$ holds true for all $n \in ℕ_{0}$ and therefore since no element is in $S$ is it empty, as needed.

The Well Ordering Principle, Induction and Strong Induction are Equivalent

As per title.

Let

A

be the statement of the well ordering principle,

B

that of induction and

C

of strong induction. Since we've proven

A ⟹ B

B ⟹ C

and

C ⟹ A

, then this induces a connected directed graph, and thus all statements are equivalent.

Finite Induction

Suppose we have a predicate

P : ℕ_{0} \to {T, F}

, then if

$P (0)$
For any $k \in {0, \dots j - 1}, P (k) ⟹ P (k + 1)$

then

P (n)

holds for every

n \in {0, \dots, j}

Upward Downward Induction

Let

P : ℕ_{0} \to {T, F}

be a predicate such that:

$P (n)$ is true for infinitely many $n \in ℕ_{0}$ ; and
For every $n \geq 1$ the implication $P (n) ⟹ P (n - 1)$ is true

then

\forall n \in ℕ \cdot P (n)

Note that if $P (0) \land P (1) \land \dots \land P (l)$ holds true for $l \in ℕ_{0}$ then we would be able to conclude that $P (n)$ for all $n \in ℕ_{0}$ , let's prove that this statement is true.

Let $l \in ℕ_{0}$ since $P (n)$ holds true for infinitely many values then there exists some $l^{'} \in ℕ_{0}$ such that $l^{'} > l$ such that $P (l^{'})$ . Now consider the new predicate defined by $Q (n) : = P (l^{'} - n)$ , note that if $Q (n)$ holds true for values ${l^{'}, l^{'} - 1, \dots 0}$ then $P (n)$ holds true on the values ${0, \dots l^{'}}$ which is what we're trying to prove.

Therefore we'll prove that $Q$ holds on ${0, \dots l^{'}}$ via finite induction. Note that $Q (0)$ holds true as it is $P (l^{'} - 0) = P (l^{'})$ , let $k \in {0, \dots, l^{'} - 1}$ and assume $Q (k)$ holds true, which is to say that $P (l^{'} - k)$ is true, let's prove that $Q (k + 1)$ holds true, which is to say that we must prove that $P (l^{'} - k - 1)$ holds true.

Since $l^{'} - k \geq l^{'} - (l^{'} - 1) = 1$ then by the second property of $P$ since we know that $P (l^{'} - k)$ holds true, then we know that $P (l^{'} - (k + 1)) = P (l^{'} - k - 1)$ holds true, so that $Q (k + 1)$ holds true, therefore by finite induction, see that $Q (n)$ holds on the set ${0, \dots, l^{'}}$ and therefore $P$ holds on the set ${0, \dots, l^{'}}$ as well, which is what we were trying to show, and thus $P (n)$ holds true for all $n \in ℕ_{0}$ .