1  Peano’s Axioms

Peano’s Axioms \(\mathbb{N}\) is a set with the following properties.

We call such a set \(\mathbb{N}\) to be the set of natural numbers and elements of this set to be natural numbers.

Theorem 1.1 If \(n\in\mathbb{N}\) and \(n\neq 1\), then there exists a unique \(m\in \mathbb{N}\) such that \(s(m)=n\).

Proof. Consider the subset \[\begin{equation} S=\{n\in \mathbb{N} \mid n=1 \text{ or } n=s(m), \text{ for some } m\in \mathbb{N}\}. \end{equation}\] By definition, \(1\in S\). If \(n\in S\), clearly \(s(n)\in S\), again by definition of \(S\). Thus by induction, we see that \(S=\mathbb{N}\). Further injectivity of \(s\) implies uniqueness as claimed.

1.1 Addition

By \(\ref{wdef}\), the following definition of addition is well-defined.

Definition 1.1 Let be the operation \(+:X\times X\to X\) recursively defined on \(y\) by \[\begin{equation} x+y:= \begin{cases} x & \text{if $y=0$} \\ s(x+z) & \text{if $y\in s(X)$ and $y=s(z)$} \\ \end{cases} \end{equation}\]

Notice \(0+0=0\) and that \(x+0=x\), for all \(x\in X\).

Lemma 1.1 For all \(x\in X\), \(x+1=s(x)\).

Proof. Let \(x\in X\). Immediately, \(x+1=x+s(0)=s(x+0)=s(x)\).

Lemma 1.2 For all \(x\in X\), \(0+x=x\).

Proof. We use induction on \(x\). First, \(0+1=0+s(0)=s(0+0)=s(0)=1\). Assume that \(0+y=y\). We must show that \(0+s(y)=s(y)\). We have \(0+s(y)=s(0+y)=s(y)\). Therefore, \(0+x=x\), for all \(x\in X\).

Lemma 1.3 For all \(x,y\in X\), \(s(x+y)=s(x)+y\).

Proof. Let \(x\in X\). We use induction on \(y\). First, \(s(x+0)=s(x)=s(x)+0\). Let \(z\in X\) and assume that \(s(x+z)=s(x)+z\). We must show that \(s(x+s(z))=s(x)+s(z)\). We have \(s(x+s(z))=s(s(x+z))=s(s(x)+z)=s(x)+s(z)\). Therefore, \(s(x+y)=s(x)+y\), for all \(x,y\in X\).

Lemma 1.4 For all \(x,y\in X\), \(x+y=y+x\).

Proof. Let \(x\in X\). We use induction on \(y\). The case \(y=0\) follows from \(\ref{prop2}\). Let \(z\in X\) and assume that \(x+z=z+x\). We must show that \(x+s(z)=s(z)+x\). We have \(x+s(z)=s(x+z)=s(z+x)=s(z)+x\), where the last equality follows by \(\ref{prop3}\). Therefore, \(x+y=y+x\), for all \(x,y\in X\).

Lemma 1.5 For all \(x,y,z\in X\), \((x+y)+z=x+(y+z)\).

Proof. Let \(x,y\in X\). We use induction on \(z\). First, \((x+y)+0=x+y=x+(y+0)\). Let \(w\in X\) and assume \((x+y)+w=x+(y+w)\), we must show \(s(w)\) has the same property. In fact, \((x+y)+s(w)=s((x+y)+w)=s(x+(y+w))=x+s(y+w)=x+(y+s(w))\) as we needed. Therefore, \((x+y)+z=x+(y+z)\), for all \(x,y,z\in X\).

Lemma 1.6 For all \(x,y,z\in X\), \[\begin{equation} \label{canadd} x+y=z+y\implies x=z. \end{equation}\]

Proof. Let \(x,z\in X\). We use induction on \(y\). If \(y=0\), then \(\eqref{canadd}\) holds. Let \(w\in X\) and assume that \(\eqref{canadd}\) holds for \(w\).
We must show that \(x+s(w)=z+(w)\) implies \(x=z\). Notice \(x+s(w)=z+s(w)\) is equivalent to \(s(x+w)=s(z+w)\). Since \(s\) is injective, this implies \(x+w=z+w\) as needed.

1.2 Multiplication

By \(\ref{wdef}\), the following definition of multiplication is well-defined.

Definition 1.2 We define \(x\cdot y\), recursively on \(y\), by \[\begin{equation} x\cdot 0=0, \qquad x\cdot s(y)=x\cdot y +x. \end{equation}\]

Lemma 1.7 For all \(x\in X\), \(x\cdot 1=x\).

Proof. Let \(x\in X\). Immediately, \(x\cdot 1=x\cdot s(0)=x\cdot 0+x=0+x=x\).

Lemma 1.8 For all \(y\in X\), \(0\cdot y=0\).

Proof. We use induction on \(y\). First, \(0\cdot 0=0\). Let \(z\in X\) and assume \(0\cdot z=0\). We must show that \(0\cdot s(z)=0\). We have \(0\cdot s(z)=0\cdot z +0=0+0=0\). Therefore, \(0\cdot y=0\), for all \(y\in X\).

Lemma 1.9 For all \(x,y\in X\), \(s(x)\cdot y=x\cdot y+y\).

Proof. Let \(x\in X\). We use induction on \(y\). First, \(s(x)\cdot 0=0=0+0=x\cdot 0+0\). Let \(z\in X\) and assume \(s(x)\cdot z=x\cdot z+z\). We must show that \(s(x)\cdot s(z)=x\cdot s(z)+s(z)\). We have \(s(x)\cdot s(z) =s(x)\cdot z +s(x) =x\cdot z+z +(x+1) =x\cdot z+x +(z+1)=x\cdot s(z)+s(z)\). Therefore, \(s(x)\cdot y=x\cdot y+y\), for all \(x,y\in X\).

Lemma 1.10 For all \(x,y\in X\), \(x\cdot y = y\cdot x\).

Proof. Let \(x\in X\). We use induction on \(y\). First, \(x\cdot 0 =0= 0\cdot x\). Let \(z\in X\) and assume \(x\cdot z = z\cdot x\). We must show that \(x\cdot s(z) = s(z)\cdot x\). We have \(x\cdot s(z) = x\cdot z+x=z\cdot x+x=s(z)\cdot x\). Therefore, \(x\cdot y = y\cdot x\), for all \(x,y\in X\).

Lemma 1.11 For all \(x,y,z\in X\), \((x+y)\cdot z=x\cdot z+y\cdot z\).

Proof. Let \(x,y\in X\). We use induction on \(z\). Clearly, \((x+y)\cdot 0=x\cdot 0+y\cdot 0\). Let \(w\in X\) and assume \((x+y)\cdot w=x\cdot w+y\cdot w\). We must show that \((x+y)\cdot s(w)=x\cdot s(w)+y\cdot s(w)\). We have \[\begin{align*} (x+y)\cdot s(w) & =(x+y) \cdot w+(x+y) = x\cdot w+y \cdot w+(x+y) \\ & = (x\cdot w+x)+(y \cdot w+y) =x\cdot s(w)+y\cdot s(w) \end{align*}\] which follow by the commutative and associative laws for addition. Therefore, \((x+y)\cdot z=x\cdot z+y\cdot z\), for all \(x,y,z\in X\).

Lemma 1.12 For all \(x,y,z\in X\), \((x\cdot y)\cdot z=x\cdot (y\cdot z)\).

Proof. Let \(x,y\in X\). We use induction on \(z\). Clearly, \((x\cdot y)\cdot 0=x\cdot (y\cdot 0)\). Let \(w\in X\) and assume \((x\cdot y)\cdot w=x\cdot (y\cdot w)\). We must show that \((x\cdot y)\cdot s(w)=x\cdot (y\cdot s(w))\). We have \[\begin{align*} (x\cdot y)\cdot s(w) & =(x\cdot y)\cdot w+(x\cdot y) =x\cdot (y\cdot w)+(x\cdot y) \\ & =x\cdot (y\cdot w+ y) =x\cdot (y\cdot s(w)) \end{align*}\] which follow from the commutative law of multiplication and the distributive law. Therefore, \((x\cdot y)\cdot z=x\cdot (y\cdot z)\), for all \(x,y,z\in X\).

Lemma 1.13 For all \(x,y\in X\), \[\begin{equation} \label{greadd} x> y \text{ if and only if } x=y+u \text{ for some } 0\neq u\in X. \end{equation}\]

Proof. We use induction on \(y\). The case for \(y=0\) is clear. Let \(z\in X\). Assume \(\ref{greadd}\) holds for \(z\), for all \(x\in X\). We will prove that \[ t>s(z) \Leftrightarrow t=s(z)+v \text{ for some } 0\neq v\in X. \] Assume \(t>s(z)\). Then \(t>s(z)>z\) and so by hypothesis, there exists \(0\neq v\in X\) such that \(t=z+v\). Since \(s\) is onto, let \(v=s(u)\). Then \(t=z+v=z+s(u)=s(z+u)=s(z)+u\). If \(u=0\), then \(t=s(z)\) contrary to hypothesis.

To prove conversely, assume \(t=s(z)+v\) for some nonzero element \(v\). If \(t=s(z)\), then \(v=0\) contrary to hypothesis. Suppose \(t<s(z)\). Case: \(t>z\). Then \(z<t<s(z)\) which can not happen. Case: \(t=z\). Then \(z=s(z)+v\) and so \(s(z)=z+1=s(z)+v+1\). Hence \(0=v+1=v+s(0)=s(v+0)=s(v)\) which implies \(v=1\) since \(s\) is injective. Hence \(0=1+1\), this absurdity implies that this case can not happen. Case: \(t>z\). Then \(s(z)+v<z\) and so \(x=z+v<s(z+v)=s(z)+v<z\). By induction hypothesis \(x>z\). Therefore, this case cannot happen either. All cases considered, it now follows that \(t>s(z)\). Whence, \(\ref{greadd}\) holds for all \(x,y\in X\).

Lemma 1.14 For all \(w,x,y,z\in X\), if \(w<x\) and \(y<z\), then \(w+y<x+z\).

Proof. Assume \(w<x\) and \(y<z\). Then there exists nonzero \(s\) and \(t\) such that \(x=w+s\) and \(z=y+t\). Then \(x+z=w+y+(s+t)\) and so by \(\ref{lemorder}\), \(w+y<x+z\).

Lemma 1.15 For all \(x,y,z\in X\), \[\begin{equation} \label{canmult} x\cdot y=x\cdot z, x\neq 0 \implies y=z. \end{equation}\]

Proof. Assume \(x\cdot y = x\cdot z.\) If \(y<z\) then there exists \(w>0\) such that \(z=y+w\). Then \(x\cdot y=x\cdot z=x\cdot (y+w)=x\cdot y+x\cdot w\). By \(\ref{addcan}\), we have \(x\cdot w=0\). Since \(x\neq0\) and \(w\neq 0\), let \(x=s(u)\) and \(w=s(t)\). Then \(x\cdot w=x\cdot s(t)=x\cdot t+s(u)=s(x\cdot t+u)\neq 0\). Hence, we find that \(y<z\) cannot happen. Similarly, the case for \(y>z\) cannot happen, and thus \(y=z\).

Lemma 1.16 For all \(x,y,z\in X\), if \(x<y\) and \(0<z\), then \(xz<yz\).

Proof. Assume \(x<y\) and \(0<z.\) Then there exist nonzero \(s\) such that \(y=x+s\). Then \(yz=(x+s)z=xz+sz\) If \(sz=0\), then \(yz=xz\). By \(\ref{canlemma}\), we have \(y=x\), contrary to hypothesis. Therefore, \(sx\neq 0\) and so we have \(xz<yz\).

1.3 Mathematical Induction

Now it’s time to take a closer look at the principle of mathematical induction and see how it works. Then we’ll explore some examples so that you can get a better understanding of this important principle.

Mathematical induction is a principle that allows us to prove a theorem by assuming that the theorem is true for a certain value of a variable and then demonstrating that the theorem holds for all larger values of the variable. This principle is incredibly important in mathematics and can be used to solve problems both big and small.

But, mathematical induction is challenging, especially for beginners. That’s why I made this article and video series so you can become skilled. So let’s start learning about mathematical induction.

The idea behind mathematical induction (or just induction) is simple: we prove that the statement holds for the first element in a well-ordered set (this is called the base case), and then we prove that if the statement holds for any given element in the set, it must also hold for the next element in the set (this is called the inductive step). By showing these two steps, the base case and the inductive step, it follows by mathematical induction that the statement holds for all elements in the set.

This process can be used to prove statements involving natural numbers, integers, rational numbers, and real numbers; and is basically used throughout mathematics.

The most basic form of mathematical induction is called natural induction. This type of induction can be used to prove statements involving the natural numbers \[\mathbb{N}=\{0,1,2,3,\ldots\}.\] To use natural induction, we first need to prove the statement for the first natural number, which is 0. This is called the base case.

On the other hand, we also use mathematical induction to prove statements involving the positive integers \[\mathbb{Z}^+ =\{1,2,3,\ldots\}.\] In using this method, the base case is at 1. Now whichever of these two methods you wish to use, the next step is the same.

Next, we assume that the statement is true for some number \(n.\) This is called the induction hypothesis. Finally, we must prove that the statement is also true for the next number, \(n+1.\) This is called the induction step. If we can successfully complete these two steps (base case) and inductive step), then we have written a mathematical proof based on the principle of mathematical induction. For more on mathematical induction see (Davenport 2008, 6–8).

Does this sound confusing yet? Well, we have just begun. So let’s go into more detail.

What is mathematical induction and why is it useful in proofs? Mathematical induction is a method of mathematical proof that is used to establish a given statement for all natural numbers. In other words, it allows us to prove statements about infinitely many objects (such as natural numbers) by proving them for just one object, and then using that result to prove the statement for the next object, and so on. Here is the full statement of mathematical induction (Burton 2006, 2–6):

Mathematical Induction. If \(P\) is a subset of the natural numbers with the following properties:

  1. \(0 \in P,\) and
  2. for all \(k\in \mathbb{N},\) \(k \in P\) implies \(k+1 \in P,\)

then \(P\) is the set of natural numbers.

Notice that this statement is an implication, containing two sub-statements, the second of which is an implication.

To use mathematical induction to prove a statement, we first need to prove two things:

  1. The statement is true for the first natural number.
  2. If the statement is true for some natural number \(k\), then it is also true for \(k+1.\)

If both of these things can be proven, then the statement is true for all natural numbers. Notice that the second statement is where the difficulty lies, mostly because it is an implication. More on this in a moment.

Here are three examples where a proof by mathematical induction can be used.

  1. Proof that \(1 + 2 + 3 + ... + n = n(n+1)/2\) for all natural numbers \(n.\) (see dasmith2021_2?)
  2. Proof that every natural number greater than 1 is either a prime number or can be written as a product of prime numbers. (see Rosen 2005, 108 – 110)
  3. Proof that the Fibonacci sequence \(F(n)\) satisfies the formula \[F(n+1) F(n-1) - F(n)^2 = (-1)^n\] for all natural numbers \(n\). (see asmith2022Fib?)

We will begin proving statements using mathematical induction after mentioning a few applications, in the next lecture.

One of the most important applications of mathematical induction is in combinatorics, where it is used to prove statements about counting objects (such as the number of ways to choose \(k\) objects from a set of \(n\)). To be clear though, mathematical induction is used throughout sciences, engineering, and humanities, i.e. (see William 2016).

  1. In computer science, mathematical induction is used to design algorithms that work for all inputs of a certain size or larger.
  2. In physics and engineering, mathematical induction is used to derive formulas for the sum of infinitely many terms in a series.
  3. In mathematics, induction is used to prove statements about sets of numbers, such as integers or real numbers.
  4. In economics, induction is used to study optimal behavior in situations where agents have incomplete information.
  5. Induction is also used in philosophy, for example, to justify the belief that the future will be like the past.
  6. In linguistics, mathematical induction is used to study the structure of language.
  7. In biology, mathematical induction is used to study the behavior of populations over time.

This list is just a few applications, to be clear, mathematical induction is ubiquitous.

Now in order to understand mathematical induction we need to work out some examples. Lots of examples and exercises.

Mathematical induction (induction) is important because it allows us to prove statements that are true for all natural numbers. This means that we can use induction to prove statements about infinite sets, which is something difficult to do. To be clear, mathematical induction provides a rigorous method of proving mathematical statements involving infinite sets of numbers.

Mathematical induction is the following statement:

If \(P\) is a subset of the natural numbers with the properties:

  • \(0 \in P\), and
  • for all \(k\in \mathbb{N}\), \(k \in P\) implies \(k+1 \in P\),

then \(P\) is the set of the natural numbers.

The advantage of mathematical induction is that it gives us a procedure to change the is a subset in the hypothesis to is the set in the conclusion. Before understanding the foundations of mathematical induction (later in this series), let’s work through some examples and see how it works.

We will now look at some examples of how to use mathematical induction.

Example 1.1 Prove that for all natural numbers \(n\),
\[\begin{equation} \label{addsum} \sum_{i=0}^n i =\frac{n(n+1)}{2}. \end{equation}\]

Solution. Let \(P\) be the set of natural numbers for which \(\eqref{addsum}\) is true. Since \(0=0=0(1)/2\) we see that \(0\in P.\) Assume \(k\in P.\) Then we find,

\[\begin{align} \sum_{i=0}^{k+1} i & =\sum_{i=0}^{k} i+(k+1) \label{twostep}\\[8pt] & =\frac{k(k+1)}{2} +(k+1) \label{threestep} \\[8pt] & =\frac{(k+1)(k+2)}{2} \end{align}\]

which shows \(k+1\in P.\) By mathematical induction \(P=\mathbb{N}\) as desired. \(\square\)

Notice that the induction hypothesis is used in moving from steps \(\eqref{twostep}\) to \(\eqref{threestep}\).

In the next example, I leave out the reference to the set \(P\). Also notice that I start the base case at 1 and use the set of positive integers.

Example 1.2 Prove that \[\begin{equation}\label{squares} \sum _{i=1}^n i^2=\frac{n(2n+1)(n+1)}{6} \end{equation}\] for all positive integers \(n.\)

Solution. For \(n=1,\) \[\begin{equation} 1=\sum _{i=1}^1 i^2=\frac{1(2+1)(1+1)}{6}=1 \end{equation}\] and so the base case holds. Assume that \(\eqref{squares}\) is true for some positive integer \(k,\) we need to show that \[\begin{equation} \sum _{i=1}^{k+1} i^2=\frac{(k+1)(2k+2)(k+2)}{6} \end{equation}\] holds. We have

\[\begin{align} \sum _{i=1}^{k+1} i^2 & =(k+1)^2+\sum _{i=1}^k i^2 \\[8pt] & =(k+1)^2+\frac{k(2k+1)(k+1)}{6} \\[8pt] & =\frac{(k+1)(2k+2)(k+2)}{6}. \end{align}\]

Therefore, by mathematical induction \(\eqref{squares}\) holds for all positive integers \(n.\) \(\square\)

The next example also demonstrates how to use mathematical induction.

Notice in this example, that we define a set of numbers with the intent of showing that this subset of natural numbers is in fact the entire set of natural numbers. We do this in two steps. First, we verify the base case. For the second step, using an induction hypothesis, we verify the needed implication. The final statement is simply the conclusion that this subset of natural numbers \(P\) is in fact the entire set of natural numbers.

Example 1.3 Prove that, for all natural numbers \(n\), \(2^n>n.\)

Solution. Let \(P\) be the set of all natural numbers for which \(2^n>n\) is true. Since \(2^0=1>0\) is true, \(0\in P.\) Assume \(k\in P\) and \(k>0\). Then \(2^k>k\) is true and since

\[\begin{align} 2^{k+1} & = 2^k\cdot 2 \\[8pt] & > k \cdot 2 \\[8pt] & = k+k \\[8pt] & > k+1 \end{align}\]

it follows \(k+1\in P.\) Thus, for all \(k\in P\), \(k\in P\) implies \(k+1\in P\) is true and so by mathematical induction \(P=\mathbb{N}\) as desired. \(\square\)

And there we have it our first three examples. We will have several more examples to come.

But first you should checkout the well-ordering principle.

1.4 The Well-Ordering Principle

The well-ordering principle (also called the well-ordering axiom) for the natural numbers is important because it provides a way to order the natural numbers. This ordering can be used to prove mathematical statements about the natural numbers. For example, the well-ordering principle can be used to show that every natural number has a unique successor. This fact can then be used to prove that there are no infinite descending sequences of natural numbers.

One answer is to simply use the order in which they are defined, so that \(0 < 1 < 2 < 3 < 4\) and so on. However, we are looking for an ordering in the sense of being antisymmetric and transitive.

Definition 1.3 The relation \(\leq\) defined on \(\mathbb{N}\) by, for all \(m,n\in \mathbb{N}\),
\[\begin{equation} m\leq n \Longleftrightarrow \exists p \in \mathbb{N}: \, m+p=n. \end{equation}\]

We call \(\leq\) an ordering because it is reflexive, antisymmetric, and transitive.

Let’s see why. If \(m\in \mathbb{N}\), then \(m +0 = m\) and so \(m\leq m\) by definition of \(\leq\). In other words \(p=0\) and so \(\leq\) is reflexive.

Notice the ordering is antisymmetric also. To see this suppose that \(m\leq n\) and \(n\leq m\). Then there exists \(p_1\) and \(p_2\) such that \(m+p_1 = n\) and \(n+p_2 = m\). From this we see that \(m=n\) because

\[\begin{align} m+p_1 & = (n+p_2)+p_1 \\[8pt] & = n + (p_1+p_2) \\[8pt] & = n \end{align}\]

which yields that \(p_1=p_2=0\).

Finally to show that \(\leq\) is transitive just assume that \(r\leq s\) and \(s\leq t\) where \(r,s,t\) are natural numbers. Then there exists \(p_1\) and \(p_2\) such that \(r+p_1 = s\) and \(s+p_2 = t\). From this we see that

\[\begin{align} r + (p_1 + p_2) & = (r+p_1) +p_2 \\[8pt] & = s + p_2 \\[8pt] & = t \end{align}\]

which yields that \(r\leq t\).

The well-ordering principle is the simple claim that:

every nonempty set of positive integers has a least element.

This sometimes overlooked and obvious statement will be proven to be logically equivalent to mathematical induction, in a later tutorial. To be clear, though, it can not be proven using the familiar properties satisfied by the integers under addition and multiplication.

For now, let’s consider some examples.

Example 1.4 Find the smallest element in each subset of \(\mathbb{N}\).

  1. \(A=\\{n\in \mathbb{N}\mid n \text{ is prime }\\}\)
  2. \(B=\\{n\in \mathbb{N} \mid \text{ $n$ is a multiple of 7}\\}\)
  3. \(C=\\{n\in \mathbb{N} \mid \text{ $n=110-7m$ for some $m\in \mathbb{Z}$}\\}\)
  4. \(D=\\{n\in \mathbb{N} \mid \text{ $n=12s+18t$ for some $s,t\in \mathbb{Z}$}\\}\)

Solution. The smallest prime is 2. The smallest positive multiple of 7 is 7. As \(m\) takes on the values \(1,2,3,\ldots\), then values of \(n\) form the sequence \[ 93, 76, 59, \ldots, 8, -9 ,\ldots \] Hence the smallest element of \(C\) is 8. Notice that \(12s+18t=6(2s+3t)\) and so elements of \(D\) are multiples of \(6\). In fact, \(6=(12)(-1)+18(1)\) and so \(6\) is in \(D\). Since 6 is the smallest positive multiple of 6, we see that \(6\) is the least element of \(D\). \(\square\)

In other words, no matter how a subset of natural numbers is defined, as long as it is nonempty, the Well-Ordering Principle guarantees us, that it must have a least element.

On the one hand, the Well-Ordering Principle seems like an obvious statement, and on the other hand, the Principal of Mathematical Induction is an incredibly useful method of proof. In a later article we’ll be proving this theorem here.

Theorem 1.2 The following statements are equivalent.

  1. (Well-Ordering Axiom) Every nonempty set of positive integers has a least element.
  2. (Mathematical Induction) If \(P\) is a subset of the positive integers with the following properties: 1) \(0 \in P\), and 2) for all \(k\in \mathbb{N}\), \(k \in P\) implies \(k+1 \in P\), then \(P\) is the set of positive integers.

Notice in the proof of the following theorem, that the well-ordering principle is used. 

Theorem 1.3 If \(a\) and \(b\) are positive integers, then there exists a positive integer \(n\) such that \(n a \geq b.\)

Proof. Assume for a contradiction that \(a\) and \(b\) do not satisfy the statement; that is, assume there exists positive integers \(a\) and \(b\) such that \(n a< b\) for every positive integer \(n.\) Consider the set,

\[S=\{b-n a \, | \, n \text{ is a positive integer}\}\]

which consists only of positive integers. By the well-ordering principle, \(S\) possess a least element, say \(b-m a\) for some positive integer \(m.\) However, \(b-(m+1)a\) is in \(S\) and \(b-(m+1)a\) is less than \(b-m a\) by

\[ b-(m+1)a=(b-m a)-a<b-m a.\]

Therefore, for positive integers \(a\) and \(b\) there must exist a positive integer \(n\) such that \(n a\geq b.\) \(\square\)

Remark. Can the reader prove that the Archimedean Property implies the Well-Ordering Principle?

Later, we will use the Well-Ordering Principle to prove the Division Algorithm and the Fundamental Theorem of Arithmetic. Before, we get to these theorems though, let’s practice using mathematical induction.

When proving a statement by mathematical induction, you should look for a pattern in the statement that can be used to create a base case and an inductive case. The base case is the simplest version of the statement, and the inductive case is a more complicated version of the statement that builds on the base case. You can then use mathematical induction to justify that the statement holds true for all cases.

In our first example, we are proving that

\[\sum_{i=1}^n (2i-1)=n^2\]

for all positive integers \(n\). For example, notice that

\[\sum_{i=1}^1 (2i-1) = 1 = 1^2\]

so the base case holds for \(n=1\) (i.e. the first positive integer). However, to demonstrate that sometimes a change in the index is desired, we show how to accomplish this. 

Example 1.5 Prove that for all natural numbers \(n\), \[\sum_{i=0}^n (2i+1)=(n+1)^2. \qquad(1.1)\]

Solution. Let \(P\) be the set of natural numbers for which (Equation 1.1) is true, that is

\[P=\left\{n\in \mathbb{N} \mid \sum_{i=0}^n (2i+1)=(n+1)^2 \right\}.\]

The basis step is easily verified by

\[\sum_{i=0}^0 (2i+1) = 1 = 1^2\]

and so we see \(0\in P\). For an induction hypothesis, assume \(k\in P\). Then

\[\sum_{i=0}^k (2i+1)=(k+1)^2\]

is true and thus,

\[\begin{align} \sum_{i=0}^{k+1} (2i+1) & =\sum_{i=0}^{k} (2i+1)+(2(k+1)+1) \\ & =(k+1)^2+2k+3 \\ & =(k+2)^2 \end{align}\]

which shows \(k+1\in P\). By mathematical induction, \(P=\mathbb{N}\) as desired. \(\square\)

In our next example, we work with an alternating sum.

Example 1.6 Prove that for all positive integers \(n\), \[ \sum_{i=1}^n (-1)^i \, i = \frac{(-1)^n (2n+1)-1}{4} \qquad(1.2)\]

Solution. Let \(P\) be the set of positive integers for which (Equation 1.2) is true. The basis step is easily verified by

\[\sum_{i=1}^1 (-1)^i \, i = -1 = \frac{(-1)^1 (2(1)+1)-1}{4}\]

and so we see \(1\in P\). For an induction hypothesis, assume \(k\in P\). Then

\[\sum_{i=1}^k (-1)^i \, i = \frac{(-1)^k (2k+1)-1}{4}\]

is true and thus,

\[\begin{align} \sum_{i=1}^{k+1} (-1)^i \, i & = \sum_{i=1}^k (-1)^i \, i + (-1)^{k+1} (k+1) \\ & =\frac{(-1)^k (2k+1)-1}{4} + (-1)^{k+1} (k+1) \\ & = \frac{(-1)^{k+1} (2(k+1)+1)-1}{4} \end{align}\]

which shows \(k+1\in P\). By mathematical induction \(P=\mathbb{Z}^+\) as desired. \(\square\)

In this next example, we work with an inequality, showing that exponential growth is greater than linear growth.

Example 1.7 Prove that for all positive integers \(n\), \(3^n > 3n-1\).

Solution. If \(n=1\), then \(3^1 = 3 > 2 = 3(1)-1\) so the base case holds. Let \(k\) be a positive integer and assume that \(3^k > 3k-1\). Then

\[3^{k+1} = 3^k \cdot 3 > (3k-1) \cdot 3 \geq 3k+2 = 3(k+1) -1.\]

So the result follows by mathematical induction. \(\square\)

Now let’s generalize the previous example.

Example 1.8 Let \(x\) be any real number greater than \(-1\). Use mathematical induction to prove that \[\begin{equation}\label{polyind} (1+x)^n \geq 1 + nx \end{equation}\] for all positive integers \(n\).

Solution. If \(n=1\), then \((1+x)^1\geq 1 + (1) x\) and so the base case holds. Let \(k\) be a positive integer and assume that \((1+x)^k \geq 1+kx\). Then

\[\begin{align} (1+x)^{k+1} & = (1+x)^{k} (1+x) \\ & \geq (1+kx)(1+x) \\ & = 1+x+k x +k x^2 \\ & = 1+ (k+1)x +kx^2 \\ & \geq 1+ (k+1)x \end{align}\]

because \(x^2\geq 0\) and \(k\geq 0\). So the result follows by mathematical induction. \(\square\)

In our fifth example, we have a sum of the reciprocals of squares involved with an inequality. These types of inequalities can be very useful in other subjects such as analysis.

Example 1.9 Prove that for all integers \(n\geq 1\), \[\begin{equation}\label{squarerec} \sum_{i=1}^n \frac{1}{i^2} \leq 2 -\frac{1}{n}. \end{equation}\]

Solution. If \(n=1\), then \(\sum_{i=1}^1 \frac{1}{1^2} = 1\leq 2 -\frac{1}{1}\) and so the base case holds. Let \(k\) be a positive integer and assume that \(\sum_{i=1}^k \frac{1}{i^2} \leq 2 -\frac{1}{k}\). Then

\[\begin{align} \sum_{i=1}^{k+1} \frac{1}{i^2} & = \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \\ & \leq 2 - \frac{1}{k} + \frac{1}{(k+1)^2} \\ & \leq 2 -\frac{1}{k+1} \end{align}\]

So the result follows by mathematical induction. \(\square\)

Now that we’ve seen some examples, let’s go for a deeper understanding of mathematical induction.

Now we will demonstrate the usefulness of mathematical induction by providing rigorous proofs for the summation formulas for finite sums of arithmetic and geometric progressions.

Arithmetic progressions are found all around us in nature and in everyday life. The temperature on a day might rise steadily from morning until evening, for instance. Or the population of a town might grow gradually over time. The study of arithmetic progressions has many practical applications. Businesses use them to forecast future sales, for example. And mathematicians use them to solve problems in physics and other areas of mathematics.

Definition 1.4 A sequence of the form \(a, a+d, a+2d, \ldots, a+nd, \ldots\) where \(a,d\in \mathbb{R}\) is called an arithmetic progression.

For example, if \(a=0\) and \(d=1\), then the sequence is \(0,1,2,3,4,\ldots\), in other words the natural numbers. Or let’s say, \(a=1/2\) and \(d=-2\), then the sequence is \(1/2, -3/2, -7/2, -11/2, -15/2,\) and so on.

In the following example, we prove a wonderful formula for the sum of the terms in arithmetic progression. 

Example 1.10 Let \(a,d\in \mathbb{R}\). Prove that for every positive integer \(n\), that \[\begin{equation} \label{arithprog} a+(a+d)+\cdots + (a+nd) =\frac{(n+1)(2a+nd)}{2}. \end{equation}\]

Solution. Let \(P\) be the set of positive integers for which \(\eqref{arithprog}\) holds. Since

\[a+(a+d)=[(1+1)(2a+d)]/2,\]

we see that \(1\in P\). Assume \(k\in P\). We find

\[\begin{align} & a+(a+d)+\cdots + (a+kd) + (a+(k+1) d) \\ & \qquad = \frac{(k+1)(2a+kd)}{2} + (a+(k+1) d) \\ & \qquad = \frac{(k+1)(2a+kd)+ 2(a+(k+1) d)}{2} \\ & \qquad = \frac{(k+2)(2a+(k+1)d)}{2} \end{align}\]

Therefore, \(k+1\in P\) and thus \(\eqref{arithprog}\) holds for \(n\geq 1\), by mathematical induction. \(\square\)

A geometric progression is a sequence of numbers in which each term after the first is found by multiplying the previous term by a fixed number, called the common ratio. In other words, each number in the sequence is determined by multiplying the previous number by a (fixed) certain amount. Let’s now explore geometric progressions.

Definition 1.5 Recall a sequence of the form \(a, ar, ar^2, \ldots, a r^n, \ldots\) where \(a,r\in \mathbb{R}\) and \(r\geq 1\) is called a geometric progression.

For example, if \(a=1\) and \(r=2\), the sequence is \(1,2,4,8,16,32,\ldots\). Or let’s say, \(a=1/2\) and \(r=-2\), then the sequence is \(1/2, -1, 2, -4, 8,\cdots\) and so on.

Example 1.11 Let \(a,r\in \mathbb{R}\) and suppose \(r\geq 1\). Prove that, for each positive integer \(n,\) that \[\begin{equation} \label{geopro} a+ar+\cdots +a r^n =a\left(\frac{r^{n+1}-1}{r-1}\right). \end{equation}\]

Solution. Let \(P\) be the set of positive integers for which \(\eqref{geopro}\) holds. Since \(a+ar=a (r^2-1)/(r-1),\) we see that \(1\in P.\) Assume \(k\in P.\) We find

\[\begin{align*} & a+ar +ar^2+\cdots +a r^k+a r^{k+1} \\ & \qquad =a\left(\frac{r^{k+1}-1}{r-1}\right)+a r^{k+1} \\ & \qquad =\frac{a r^{k+1}-a+(r-1)a r^{k+1} }{r-1} \\ & \qquad =a\left(\frac{r^{k+2}-1}{r-1}\right). \end{align*}\]

Therefore, \(k+1\in P\) and thus \(\eqref{geopro}\) holds for \(n\geq 1\), by mathematical induction. \(\square\)

The mathematical induction principle is analogous to an infinite string of equally spaced dominos set up in a single line arranged so that if one falls down then so does the next one. Imagine you knock down the first domino, and then after some time has passed you check back and the dominos are still falling. Would you believe that this will continue indefinitely?

The method of proof of using the principle of mathematical induction is frequently useful in the theory of numbers. Familiarity with this type of argument is essential to subsequent work.

In any proof by induction, we must not forget to show that \(0\) is in \(P\). Even if we show that the truth of \(k\) in \(P\) implies that \(k+1\) is in \(P\), if \(0\) is not in \(P,\) then we cannot conclude that \(P\) is the set of natural numbers. For example, let \(P\) be the set of all natural numbers that satisfy:

\[n+(n+1)=2n. \qquad(1.3)\]

Suppose \(k\) satisfies, (Equation 1.3). Using this we have

\[\begin{align*} (k+1)+(k+2) & =k+(k+1)+2 \\ & =2k+2 \\ & = 2(k+1) \end{align*}\]

and thus \(k+1\) also satisfies (Equation 1.3). So, if \(1\) satisfies (Equation 1.3) then, it would follow that (Equation 1.3) is true for all natural numbers \(n\). However, \(0\) does not satisfy (Equation 1.3). In fact, obviously, (Equation 1.3) is false for all natural numbers \(n\). We conclude that the basis step is a necessary part of any proof by mathematical induction.

The assumption that the statement is true for some number \(n=k\) will often be referred to as the induction hypothesis. Sometimes the role that 1 plays in the principle of mathematical induction will be replaced by some other integer, say \(a,\) in such instances mathematical induction establishes the statement for all integers \(n\geq a.\)

The method of mathematical induction has its limitations in that it consists of testing a known (or conjectured) formula. All that the induction process enables us to do is to show that any special case can be proved on the assumption that all the preceding cases have been verified.

1.5 The Mathematical Induction Equivalence

In the hypothesis of mathematical induction, the statement \(0\in P\) is called the base case. Mathematical induction can be thought of as a collection of principles, for example, the base case may start at \(0\), or \(1\), or \(2\), etc. instead of \(0\). In each of these scenarios, the goal is to prove a collection of statements is true, for all \(n\) greater than some initial value which must be verified (base case).

Now that we have established that a base case is required when using mathematical induction. It is now natural to ask: does the base case need to start at the first natural number 0. We have seen previous examples where that base case starts at 1 when proving a statement holds for all positive integers. So let’s make this formal.

Let \(a\) be a natural number. Consider the set defined by

\[\mathbb{N}_a = \{k\in \mathbb{N}:k\geq a\}.\]

In other words,

\[\mathbb{N}_a = \{a,a+1,a+2,a+3, \ldots \}.\]

Using this set notation we can formalize variations of mathematical induction as follows.

Mathematical Induction is the following statement:

Let \(a\) be a natural number. If \(P\) is a subset of \(\mathbb{N}_a\) with the properties:

  1. \(a \in P\), and
  2. for all \(k\in \mathbb{N}_a\), \(k \in P\) implies \(k+1 \in P\),

then \(P\) is the set \(\mathbb{N}_a\).

Notice that whenever \(a=0\), we have the Principle of Mathematical Induction as stated previously.

For example, while \(n!>n\) is not true for $n=0, 1, 2 $, it is true for all \(n\geq 3\). So our base case is \(n=3\). Let’s prove that \(n!>n\) for all \(n\geq 3\). Since \(3!=1\cdot 2\cdot 3=6>3\) we see that the base case holds. Now assume that for some positive integer \(k\) greater than 3, that \(k!>k.\) Then we see that

\[\begin{align*} (k+1)! & =k!(k+1) \\ & >k(k+1) \\ & >k+1 \end{align*}\]

Therefore, by mathematical induction, \(n!>n\) for all \(n\geq 3\).

Example 1.12 Prove that \(2^{n-1}>n\) for all positive integers \(n\geq 3.\)

Solution. Since \(4=2^{3-1}=2^2=4>3\) the statement is true for \(n=3.\) Assume that the result is true for a positive integer \(n,\) we need to show that \(2^{(n+1)-1}>n+1\) holds. Starting from \(2^{n-1}>n\) we multiply by 2 to obtain \(2^n>2n.\) But \(2n=n+n>n+1\) since \(n\geq 3.\) Therefore by mathematical induction, \(2^{(n+1)-1}>2n>n+1\) for all positive integers \(n\geq 3\) as desired. \(\square\)

Now let’s turn our attention to another variation of mathematical induction called strong induction.

The principle of strong (mathematical) induction is also a method of proof and is frequently useful in the theory of numbers. This principle can also be used to prove statements about arays, sequences, and many other structures. Familiarity with this type of argument is essential to subsequent work.

Strong induction was invented by the mathematician, logician, and philosopher Bertrand Russell.

Theorem 1.4 A set of positive integers that contains the integer 1, and that has the property: for every positive integer \(n,\) if the set contains \(1,2,\ldots,n,\) then it also contains the integer \(n+1\); must be the set of all positive integers.

Proof. Let \(P\) be the set with the stated properties and let \(S\) be the set consisting of all positive integers not in \(P.\) Assuming that \(S\) is nonempty, we can choose \(n\) to be the least integer in \(S\) by the Well-Ordering Principle. Since \(1\) is in \(P\) and \(n\) is not in \(P\), we know that \(n>1\). Further, notice that none of the integers \(1,2,3,\ldots,n-1\) lies in \(S\), so that in fact, they are in \(P\). Then by the second property, \(n=(n-1)+1\) is in \(P,\) which contradicts \(n\) is not in \(P\). Thus, \(S\) is empty and \(P\) must be the set of all positive integers. \(\square\)

While the hypothesis is stronger, both statements are actually logically equivalent to each other, as the next theorem states.

Theorem 1.5 (Induction Principles) The following statements are logically equivalent.

  1. (Mathematical Induction) If \(P\) is a subset of the natural numbers with the following properties: a) \(0 \in P\), and b) for all \(k\in \mathbb{N}\), \(k \in P\) implies \(k+1 \in P\), then \(P\) is the set of natural numbers.
  2. (Strong Induction) If \(P\) is a subset of the natural numbers with the following properties: a) \(0 \in P\), and b) for all \(k\in \mathbb{N}\), \(0,1,..., k \in P\) implies \(k+1 \in P\), then \(P\) is the set of natural numbers.

Which one you choose is often a matter of convenience. Some statements are much easier to work with using one or the other. Can you tell which version is used in the next example?

Example 1.13 Let \(a\) be a real number. Prove that for all \(n\geq 1\),

\[a^n-1=(a-1)\left(a^{n-1}+a^{n-2}+a^{n-3}+\text{...}+a+1\right).\]

Solution. For \(n=1,\) \(a-1=a-1\) is obvious. Suppose that the equation is true for \(k\) namely,

\[\left(a^k-1\right)=(a-1)\left(a^{k-1}+a^{k-2}+a^{k-3}+\cdots+a+1\right).\]

Then for \(k+1\) we have

\[\begin{align*} \left(a^{k+1}-1\right) & =\left(a^{k+1}-a^k+a^k-1\right) \\ & =a^k(a-1)+(a-1)\left(a^{k-1}+a^{k-2}+a^{k-3}+\cdots+a+1\right) \end{align*}\]

and so

\[\left(a^{k+1}-1\right)=(a-1)\left(a^k+a^{k-1}+a^{k-2}+a^{k-3}+\cdots+a+1\right).\]

as desired. \(\square\)

We can also rely on the strong principle of induction, by considering the formula:

\[a^{n+1}-1=(a+1)\left(a^n-1\right)-a\left(a^{n-1}-1\right)\]

if desired.

Now in order to understand the difference between strong induction and mathematical induction, we will consider the Lucas numbers. The following example illustrates when strong induction might be the preferred method.

To illustrate the strong form of induction we will discuss the Lucas numbers. Numbers in the sequence \(1, 3, 4, 7, 11, 18, \ldots\) are called Lucas numbers. They are defined inductively by, \(L_1=1\), \(L_2=3,\) and

\[L_n=L_{n-1}+L_{n-2} \quad \text{for all $n\geq 3$}. \]

The Lucas numbers have a number of interesting mathematical properties, and they can be used to generate a variety of different patterns and sequences. They also show up in a surprising number of real-world applications, from financial markets to computer algorithms.

Example 1.14 Prove that for all positive integers \(n\),

\[L_n < \left(\frac{7}{4}\right)^n. \qquad(1.4)\]

Solution. For the basis step notice that

\[L_1=1< \left(\frac{7}{4}\right)^1=\frac{7}{4}. \]

Now assume (strong induction hypothesis) that (Equation 1.4) holds true for \(n=1, \dots, k-1\). Then we find,

\[\begin{align*} L_k = L_{k-1}+L_{k-2} & < \left(\frac{7}{4}\right)^{k-1}+\left(\frac{7}{4}\right)^{k-2} \\[5pt] & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}+1\right) \\[5pt] & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{11}{4}\right) \\[5pt] & < \left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}\right)^{2} \\[5pt] & = \left(\frac{7}{4}\right)^{k}. \end{align*}\]

Because the inequality is true for \(n=k\) whenever it is true for the integers \(1, 2, \dots, k-1\), we conclude, by Strong Induction, that \(L_n < (7/4)^n\) for all \(n\geq 1\). \(\square\)

When first studying mathematical induction a student often runs into solving the postage stamp problem.

Example 1.15 Show that any amount of postage more than 1-cent can be formed just using 2-cent and 3-cent stamps.

Solution. Notice that 2-cent and 3-cent stamps can be formed using 2-cent and 3-cent stamps, so the base case is obvious. Let \(k\) be a positive integer with \(k\geq 1\). For an induction hypothesis (strong), assume that any amount of postage up to \(k\)-cents can be formed using 2-cent and 3-cent stamps. Then using \(k+1 = k-1+ 2\), and the fact that \(2\) is a 2-cent stamp and \(k-1\) can be formed using 2-cent and 3-cent stamps, we see that \(k+1\) can be formed using 2-cent and 3-cent stamps. Hence by strong induction, any amount can be formed using 2-cent and 3-cent stamps. \(\square\)

For our next example, let’s use a new function. Define a function recursively, for all positive integers \(n\) by \(f(1)=1,\) \(f(2)=5\) and

\[f(n+1)=f(n)+2f(n-1).\]

For example, \(f(1)=1\), \(f(2)=5\), \(f(3)=7\), \(f(4)=17\), and so on. We can (exhaustively) search for patterns until we find this gem:

Example 1.16 Prove that \(f(n)=2^n+(-1)^n\) for all positive integers \(n\).

Solution. For \(n=1\) and \(n=2\), we have \(f(1)=1=2^1+(-1)^1\) and \(f(2)=5=2^2+(-1)^2\), so the base case holds. Let \(k\) be a positive integer with \(k\geq 1\). Assume \(f(n)=2^n+(-1)^n\) holds for \(n=0,.\ldots, k\). Then

\[\begin{align} f(k+1) & = f(k)+2f(k-1) \\ & = 2^k+(-1)^k +2 ( 2^{k-1}+(-1)^{k-1}) \\ & = 2^k +2^k +(-1)^k + 2((-1)^{k-1}) \\ & = 2^{k+1} + (-1)^{k+1} \end{align}\]

Therefore, the result follows by strong induction. \(\square\)

If you haven’t seen these examples on mathematical induction you should work through them before moving on to the Mathematical Induction Equivalence.

In this video, you’ll learn the Mathematical Induction Equivalence, the equivalence of the well-ordering principle, mathematical induction, and strong induction. You’ll see that if the well-ordering principle holds then induction must also hold. Then we’ll prove that if induction holds, then strong induction must also hold. Finally, then we prove that if strong induction holds, then the well-ordering principle must also hold. Proving these three statements is the same as proving all three of them are logically equivalent. Effectively, what this means is that if you assume one of them is true, then all three of them must be true.

The Mathematical Induction Equivalence is the statement that all three of these statements:

  1. The Well-Ordering Principle
  2. The Principle of Mathematical Induction
  3. The Strong Form of Induction

are all equivalent to each other.

Now in order to prove the Mathematical Induction Equivalence, let’s review what these three statements are.

Theorem 1.6 (Well-Ordering Principle) Every nonempty set of natural numbers has a least element.

Theorem 1.7 (Mathematical Induction) If \(P\) is a subset of the natural numbers with the following properties: 1) \(0 \in P\), and 2) for all \(k\in \mathbb{N}\), \(k \in P\) implies \(k+1 \in P\), then \(P\) is the set of natural numbers.

Theorem 1.8 (Strong Induction) If \(P\) is a subset of the natural numbers with the following properties: 1) \(0 \in P\), and 2) for all \(k\in \mathbb{N}\), \(0,1,..., k \in P\) implies \(k+1 \in P\), then \(P\) is the set of natural numbers.

Let’s use WOP, PMI, and SFI for the abbreviations for these three statements, respectively.

Our goal is to prove the equivalence of these three statements.

Mathematical induction is a technique used to prove that a certain property holds for all natural numbers. The well-ordering principle states that every non-empty set of natural numbers contains a smallest element. We will now prove that the well-ordering principle implies mathematical induction.

Theorem 1.9 \(WOP\Rightarrow PMI\)

Proof. Let \(P\) be a subset of natural numbers with \(0\in P\) and the property, for all natural numbers \(k\), \(k\in P\) implies \(k+1\in P\). Assume, for a contradiction, there exists a nonempty set \(S\) containing the natural numbers not in \(P\). By the Well-Ordering Principle, \(S\) has a least natural number, \(s\). Since \(0\in P\), \(s\neq 0\). Thus there exists a natural number \(t\) such that \(t+1=s\). Notice \(t\mathbb{N}ot\in S\) since \(t<s\). Thus \(t\in P\) and so \(s=t+1\in P\). This contradiction shows \(S\) cannot exist, meaning \(P=\mathbb{N}\) as desired. \(\square\)

As a fun exercise for the reader, you should try proving that \(PMI\Rightarrow WOP\). After trying that, read on.

In case you’ve heard of terms like weak induction or strong induction, we will now see they are actually equivalent. The advantage of having different mathematical induction variations though is to have flexibility when writing proofs.

Theorem 1.10 \(PMI\Rightarrow SFI\)

Proof. Let \(S\) be a set of natural numbers with \(0\in S\) and the property, for all natural numbers \(k\), \(0,1,2...,k\in S\) implies \(k+1\in S\). Let \(P\) be the set of natural numbers for which \(0,2, ..., n\in S\) is true. Notice \(0\in P\) since \(0\in S\). Assume \(k\in P\). Then \(0,1,2, ..., k\in S\). Thus \(0,1,2,3,..., k , k+1\in S\) meaning \(k+1\in P\). By I, \(P=\mathbb{N}\). By definition of \(P\), \(S=\mathbb{N}\) as desired. \(\square\)

Notice that only \(PMI\Rightarrow SFI\) was proven above. The converse statement, namely \(SFI\Rightarrow PMI\) is left for the reader.

One of the most important statements in number theory is the well-ordering principle. This principle states that every non-empty set of natural numbers contains a smallest element. In other words, there is no infinite sequence of natural numbers in which each number is smaller than the one before it. The well-ordering principle is often used to prove results by contradiction. This makes it a very powerful tool for mathematical reasoning. Now it’s time to show that strong induction implies the well-ordering principle.

Theorem 1.11 \(SFI\Rightarrow WOP\)

Proof. Assume, for a contradiction, there exists a nonempty set of natural numbers \(S\) with no least element. Let \(P\) be the set of natural numbers for which \(n\mathbb{N}otin S\) is true. Because \(0\) is the least element of all natural numbers, \(0\mathbb{N}otin S\) and so \(0\in P\). Assume \(0,1,...,k\in P\). If \(k+1\in S\) then \(k+1\) is the least element of \(S\). However, \(S\) has no least element and thus \(k+1\mathbb{N}otin S\). Thus, \(k+1\in P\) and so by Strong Induction, \(P=\mathbb{N}\). This contradiction shows \(S\) can not exist. Therefore, \(S=\mathbb{N}\). \(\square\)

Notice that only \(SFI\Rightarrow WOP\) was proven above. The converse statement, namely \(WOP\Rightarrow SFI\) is left for the reader.

Okay, so we have proven that \(WOP\Rightarrow PMI \Rightarrow SFI \Rightarrow WOP\). This means, logically speaking that, \(WOP\Leftrightarrow PMI \Leftrightarrow SFI\), and so all three theorems above are proven.

As discussed above, there are several variations of mathematical induction. Now we would like to show that these are equivalent also. Recall we use the notation \[N_a = \{k\in \mathbb{N}: k\geq a\}\] where \(a\) is a natural number.

Theorem 1.12 (Mathematical Induction Equivalence**)) Let \(a\) be a fixed natural number. The following statements are logically equivalent.

  1. Every nonempty set of \(\mathbb{N}_a\) has a least element.
  2. If \(a\in P\subseteq\mathbb{N}_a\) and for all \(k\in \mathbb{N}_a\), \(k \in P\) implies \(k+1 \in P\), then \(P=\mathbb{N}_a\).
  3. If \(a\in P\subseteq\mathbb{N}_a\) and for all \(k\in \mathbb{N}_a\), \(a,a+1,\ldots,a+k \in P\) implies \(a+k+1 \in P\), then \(P=\mathbb{N}_a\).

Proof. \((1)\Rightarrow (2)\): Let \(P\subseteq \mathbb{N}_a\) with \(a\in P\) and the property, for all natural numbers \(k\), \(k\in P\) implies \(k+1\in P\). Assume, for a contradiction, there exists a nonempty subset \(S\) of \(\mathbb{N}_a\) containing the natural numbers not in \(P\). By the Well-Ordering Principle, \(S\) has a least natural number, \(s\). Since \(a\in P\), \(s\neq a\). Further, since \(s\in S\subseteq \mathbb{N}_a\) we know that \(s>a\). Thus there exists a natural number \(t\) such that \(t+1=a\). Notice \(t\mathbb{N}ot\in S\) since \(t<s\). Thus \(t\in P\) and so \(s=t+1\in P\). This contradiction shows \(S\) cannot exist, meaning \(P=\mathbb{N}_a\) as desired.

\((2)\Rightarrow (3)\): Let \(S\) be a set of natural numbers with \(a\in S\) and the property, for all natural numbers \(k\), \(a,a+1,\ldots,a+k\in S\) implies \(a+k+1\in S\). Let \(P\) be the set of natural numbers for which \(a,a+1, \ldots, a+n\in S\) is true. Notice \(a\in P\) since \(a\in S\). Assume \(k\in P\). Then \(a,a+1, \ldots, a+k\in S\). Thus \(a,a+1,\ldots, a+k, a+k+1\in S\) meaning \(a+k+1\in P\). Hence, \(P=\mathbb{N}_a\). By definition of \(P\), \(S=\mathbb{N}_a\) as desired.

\((3)\Rightarrow (1)\): Assume, for a contradiction, there exists a nonempty subset \(S\) of \(\mathbb{N}_a\) with no least element. Let \(P\) be the set of natural numbers for which \(n\mathbb{N}otin S\) is true. Because \(a\) is the least element of all elements in \(\mathbb{N}_a\), \(a\mathbb{N}otin S\) and so \(a\in P\). Assume \(a,a+1,\ldots,a+k\in P\). If \(a+k+1\in S\) then \(a+k+1\) is the least element of \(S\). However, \(S\) has no least element and thus \(a+k+1\mathbb{N}otin S\). Thus, \(a+k+1\in P\) and so \(P=\mathbb{N}_a\). This contradiction shows \(S\) can not exist. \(\square\)

There are many other forms of mathematical induction. We are only limited by our imagination. But for now, let’s work through more exercises on mathematical induction.

Mathematical induction is one of the most powerful techniques in mathematics. It allows us to prove a statement for a certain set of numbers, and then use that proof to show that the statement is true for all natural numbers. In this section, we will give some exercises on mathematical induction to help you understand the technique better. We will also provide solutions to these exercises so that you can check your work. Let’s get started!

Example 1.17 Prove that

\[\sum _{k=1}^n k^3=\left(\frac{n(n+1)}{2}\right)^2\]

for all positive integers \(n.\)

Solution. For \(n=1,\)

\[ 1=\sum _{k=1}^1 k^3=\left(\frac{1(1+1)}{2}\right)^2=1. \]

Assume that the result is true for a positive integer \(n,\) we need to show that

\[ \sum _{k=1}^{n+1} k^3=\left(\frac{(n+1)(n+2)}{2}\right)^2 \]

holds. We have

\[\begin{align*} \sum _{k=1}^{n+1} k^3 & =(n+1)^3+\sum _{k=1}^n k^3 \\ & =(n+1)^3+\left(\frac{n(n+1)}{2}\right)^2 \\ & =\left(\frac{(n+1)(n+2)}{2}\right)^2. \end{align*}\]

Therefore by mathematical induction

\[\sum _{k=1}^{n+1} k^3=\left(\frac{(n+1)(n+2)}{2}\right)^2\]

holds true for all positive integers \(n.\) \(\square\)

Example 1.18 Prove that \(2\cdot 6 \cdot 10 \cdot 14 \cdots (4n-2) = \frac{(2n)!}{n!}\) for all positive integers \(n.\)

Solution. For \(n=1\) we have \(2 = \frac{2!}{1!} = \frac{2}{1}\) so the base case holds. Assume that

\[2\cdot 6 \cdot 10 \cdot 14 \cdots (4k-2) = \frac{(2k)!}{k!}\]

for some positive integer \(k\). Then

\[\begin{align*} & 2\cdot 6 \cdot 10 \cdot 14 \cdots (4k-2) \cdot (4k+2) \\[8pt] & \qquad = \frac{(2k)!}{k!} \cdot (4k+2) \\[8pt] & \qquad = \frac{(2k)! (2)(2k+1)(k+1)}{(k+1)!} \\[8pt] & \qquad = \frac{1\cdot 2 \cdots (2k)(2k+1)(2k+2)}{(k+1)!} \\[8pt] & \qquad = \frac{(2k+2)!}{(k+1)!} \end{align*}\]$$

as desired. The result follows by mathematical induction. \(\square\)

1.6 The Fibonacci Sequence

Fibonacci numbers have been found to occur in many areas of mathematics, as well as in nature. For example, the proportions of many spiral shells can be expressed as Fibonacci numbers.

Fibonacci numbers were highlighted by the Italian mathematician Leonardo of Pisa (Fibonacci), who was investigating the growth of rabbit populations. He realized that the Fibonacci sequence could be used to model the way in which rabbits reproduce.

Fibonacci numbers also appear in the DNA molecule and in the arrangement of leaves on a stem. It seems that Fibonacci numbers are ubiquitous in both mathematics and nature!

The Fibonacci numbers start with 0 and 1, and then the next Fibonacci number is 1 \((0+1),\) and the next Fibonacci number is 2 \((1+1),\) and so on. As a result, the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,…

Fibonacci numbers play an important role in mathematics and have a wide range of applications. They are also closely related to the golden ratio, which is often found in nature. Fibonacci numbers can be generated by starting with 0 and 1, and then adding the two previous numbers to get the next number in the sequence. This relationship is known as the Fibonacci recurrence.

The Fibonacci numbers are also related to each other by a plethora of (Fibonacci identities) identities. These identities can be proved using mathematical induction. How? First, the base case must be proven true for \(n=0.\) Then, the inductive step, it must be shown that if the Fibonacci identities are true for \(n=k\), then they are also true for \(n=k+1.\) By following this process, it can be shown that a Fibonacci identity holds. As a result, these identities provide a powerful tool for understanding and manipulating Fibonacci numbers.

After having studied mathematical induction the Fibonacci numbers are a good topic to test ones abilities to perform induction. There are two obvious reasons for this. Firstly, many of the results (exercises) for are relatively straight-forward. Secondly, many of the results obtain are quite surprising. For instance, the sum of the squares of the first \(n\) Fibonacci numbers is the same as the product of the \(n\)-th and the \(n+1\)-th. This fact is easily provable by mathematical induction. We now study the Fibonacci Numbers and the Euler-Binet Formula.

Fibonacci numbers are defined as a recursive sequence by starting with \(0\) and \(1,\) and then adding the previous two integers together. It has long been noticed that the Fibonacci numbers arise in many places throughout the natural world. Fibonacci numbers have many special mathematical properties.

Definition 1.6 Fibonacci numbers are the positive integers defined by \(f_0=0,\) \(f_1=1,\) and

\[f_{n}=f_{n-1}+f_{n-2}\]

for \(n\geq 2.\)

The first 21 Fibonacci numbers are

\[\begin{array}{ccccccc} 1 & 1 & 2 & 3 & 5 & 8 & 13 \\ 21 & 34 & 55 & 89 & 144 & 233 & 377 \\ 610 & 987 & 1597 & 2584 & 4181 & 6765 & 10946 \end{array}\]

Here we prove several identities involving Fibonacci numbers. The idea is to provide several interesting examples on how mathematical induction can be applied to give rigorous arguments on (perhaps) experimentally found identities.

Example 1.19 Prove that for all positive integers \(n\),

\[\sum_{i=0}^n f_{i}^2 = f_n f_{n+1}. \qquad(1.5)\]

Solution. Let \(P\) be the set of positive integers for which (Equation 1.5) is true. Since \(f_0^2 =0=f_0 f_1\) we see \(0\in P\). Assume \(k\in P\). It follows \(k+1\in P\) by

\[\begin{align} \sum_{i=0}^{k+1} f_i^2 & =\sum_{i=0}^{k} f_i^2+ f_{k+1}^2 \\[8pt] & =f_k f_{k+1}+f_{k+1}^2 \\[8pt] & =f_{k+1}(f_k+f_{k+1}) \\[8pt] & =f_{k+1} f_{k+2}. \end{align}\]

By mathematical induction \(P=\mathbb{N}\) as desired. \(\square\)

Example 1.20 Prove that for all positive integers \(n,\)

\[\sum_{j=1}^n f_{2j}=f_{2n+1}-1. \qquad(1.6)\]

Solution. For \(n=1,\) \(f_2=1= f_3-1\) so the base case holds. Assume, for some positive integer \(k,\) that (Equation 1.6) holds. Then we find

\[\begin{align} \sum_{j=1}^{k+1} f_{2j} & = \sum_{j=1}^k f_{2j}+f_{2k+2} \\[8pt] & = f_{2k+1}-1+f_{2k+2} \\[8pt] & = f_{2k+3}-1. \end{align}\]

By mathematical induction, (Equation 1.6) holds for all positive integers \(n.\) \(\square\)

Example 1.21 Prove that for all positive integers \(n\),

\[\sum_{i=1}^n f_{2i-1} = f_{2n}. \qquad(1.7)\]

Solution. Since \(f_1=1=f_2\) we see the base case holds. Assume, for some positive integer \(k\), that (Equation 1.7) holds. Then we find

\[\begin{align} \sum_{i=1}^{k+1} f_{2i-1} & = \sum_{i=1}^k f_{2i-1} +f_{2(k+1)-1} \\[8pt] & = f_{2k}+f_{2k+1} \\[8pt] & = f_{2k+2} \\[8pt] & = f_{2(k+1)}. \end{align}\]

By mathematical induction, (Equation 1.7) holds for all positive integers \(n.\) \(\square\)

Example 1.22 Prove that for all positive integers \(n,\)

\[\sum_{i=1}^n f_i = f_{n+2}-1. \qquad(1.8)\]

Solution. For \(n=1,\) \(f_1=1=f_3-1\) so the bases case holds. Assume, for some positive integer \(k\), that (Equation 1.8) holds. Then we find

\[\begin{align} \sum_{j=1}^{k+1} f_j & =\sum_{j=1}^k f_j+f_{k+1} \\[8pt] & = f_{k+2}-1+f_{k+1} \\[8pt] & = f_{k+1}+f_{k+2}-1 \\[8pt] & = f_{k+3}-1. \end{align}\]

By mathematical induction, (Equation 1.8) holds for all positive integers \(n.\) \(\square\)

Example 1.23 Prove that for all positive integers \(n,\)

\[f_{n+1}f_{n-1}-\left(f_n\right){}^2=(-1)^n. \qquad(1.9)\]

Solution. For \(n=1,\) \(f_2f_0-\left(f_1\right)^2=(-1)^1\) so the base case holds. Assume, for some positive integer \(k\), that (Equation 1.9) holds. Then we find

\[\begin{align} f_{k+2}f_k-\left(f_{k+1}\right){}^2 & =\left(f_{k+1}+f_k\right)f_k-\left(f_{k+1}\right)\left(f_{k-1}+f_k\right) \\[8pt] & =f_{k+1}f_k+\left(f_k\right){}^2-f_{k+1}f_{k-1}-f_{k+1}f_k \\[8pt] & =(-1)\left(-\left(f_k\right){}^2+f_{k+1}f_{k-1}\right) \\[8pt] & =(-1)(-1)^k \\[8pt] & =(-1)^{k+1}. \end{align}\]

By mathematical induction, (Equation 1.9) holds for all positive integers \(n.\) \(\square\)

From our previous video, we recall the definition of the Fibonacci numbers.

Definition 1.7 Fibonacci numbers are the positive integers defined by \(f_0=0,\) \(f_1=1,\) and

\[f_{n}=f_{n-1}+f_{n-2}\]

for \(n\geq 2.\)

The first 21 Fibonacci numbers are

\[\begin{array}{ccccccc} 1 & 1 & 2 & 3 & 5 & 8 & 13 \\ 21 & 34 & 55 & 89 & 144 & 233 & 377 \\ 610 & 987 & 1597 & 2584 & 4181 & 6765 & 10946 \end{array}\]

In our previous lecture we also proved the following 5 Fibonacci identities.

Example 1.24 Prove that for all positive integers \(n\),

\[\sum_{i=0}^n f_{i}^2 = f_n f_{n+1}.\]

Example 1.25 Prove that for all positive integers \(n\),

\[\sum_{j=1}^n f_{2j}=f_{2n+1}-1.\]

Example 1.26 Prove that for all positive integers \(n\),

\[\sum_{i=1}^n f_{2i-1} = f_{2n}.\]

Example 1.27 Prove that for all positive integers \(n,\)

\[\sum_{i=1}^n f_i = f_{n+2}-1.\]

Example 1.28 Prove that for all positive integers \(n,\)

\[f_{n+1}f_{n-1}-\left(f_n\right){}^2=(-1)^n.\]

Now let’s see what this infamous formula is all about.

The Fibonacci numbers also have an interesting relationship to the golden ratio. This relationship is expressed by a formula called the Euler-Binet formula. And this simple equation has surprising implications, and it has been used to derive many other results in mathematics. The Fibonacci numbers and the golden ratio continue to fascinate mathematicians and laypeople alike, and they are sure to continue to yield new insights in the future.

Firstly, we notice that the Euler-Binet formula gives us a closed form for calculating the \(n\)-th Fibonacci number. In fact, the formula is in terms of the golden ratio \(\phi.\) To prove the formula we first need the following lemma involving the golden ratio.

Lemma 1.17 For any solution \(x\) of \(x^2-x-1=0\) and any positive integer \(n\), \[x^n=x f_n+f_{n-1}.\]

Proof. Proof by mathematical induction. Clearly, \(x^1= x f_1+f_{0}=x (1)+0=x\) so the base case holds. Assume now that, for some positive integer \(k\), that

\[ x^k=x f_k+f_{k-1}. \]

We wish to prove that

\[x^{k+1}=x f_{k+1}+f_{k}.\]

To this end, multiply the identity by \(x\) to obtain

\[\begin{align} x^{k+1} & =x^2 f_k+ x f_{k-1} \\[8pt] & = (x+1) f_k+x f_{k-1} \\[8pt] & = x(f_k+f_{k-1})+f_k \\[8pt] & = x f_{k+1}+f_k \end{align}\]

as needed.

The golden ratio is the positive root of the quadratic equation \(x^2-x-1=0,\) that is,

\[\phi=\frac{1+\sqrt{5}}{2}.\]

The conjugate of \(\phi\) is denoted using \(\tau\) and is

\[\tau=\frac{1-\sqrt{5}}{2}.\]

It is easily verified that \(\phi\tau=-1\) and \(\phi-\tau=\sqrt{5}\). We now give a closed formula to compute the \(n\)-th Fibonacci number.

Theorem 1.13 (Euler-Binet Formula) For all positive integers \(n\),

\[f_n=\frac{1}{\sqrt{5}}(\phi^n-\tau^n).\]

Proof. By (Lemma 1.17),

\[ \phi^n=\phi f_n+f_{n-1} \quad \text{ and } \quad \tau^n=\tau f_n+f_{n-1}. \]

It follows that \(f_n=\frac{\phi^n-\tau^n}{\phi-\tau}\). Now observe that (Theorem 1.13) follows since \(\phi-\tau=\sqrt{5}\).

The first 75 Fibonacci numbers.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050

The next example shows that the Fibonacci numbers grow exponentially fast.

Example 1.29 Prove that \(f_n>\left(\frac{3}{2}\right)^{n-1}\), for all \(n\geq 6\).

Solution. We verify that

\[f_6=8>\left(\frac{3}{2}\right)^5\approx 7.59375.\]

We also must verify \[f_7=13>\left(\frac{3}{2}\right)^6\approx 11.390625.\]

Now let \(k>7\), and assume (the inductive hypothesis) that \(f_i >(3/2)^{i-1}\) for \(i=k-1\) and \(i=k-2\). Then we have

\[\begin{align*} f_k & = f_{k-1}+f_{k-2} \\[8pt] & > \left(\frac{3}{2}\right)^{k-2}+\left(\frac{3}{2}\right)^{k-3} \\[8pt] & = \left(\frac{3}{2}\right)^{k-3}\left(\frac{3}{2}+1\right) \\[8pt] & = \left(\frac{3}{2}\right)^{k-3}\left(\frac{5}{2}\right) \\[8pt] & > \left(\frac{3}{2}\right)^{k-3}\left(\frac{9}{4}\right) \\[8pt] & = \left(\frac{3}{2}\right)^{k-3}\left(\frac{3}{2}\right)^2 = \left(\frac{3}{2}\right)^{k-1} \end{align*}\]

as desired.

The golden ratio \(\phi\) is approximately, 1.61803398875. We can use the golden ratio to improve our understanding of the growth rate of the Fibonacci sequence.

Example 1.30 Prove that \(f_n>\phi^{n-2}\), for all \(n\geq 3\).

Solution. We verify that

\[f_3=3>\phi^1\approx 1.618 \qquad \text{and}\qquad f_4=5>\phi^2\approx 2.618.\]

Now let \(k>4\), and assume (the inductive hypothesis) that \(f_i >\phi^{i-2}\) for \(i=k-1\) and \(i=k-2\). Now using \(\phi^2=\phi+1\), we have

\[\begin{align*} f_k & =f_{k-1}+f_{k-2} \\[8pt] & > \phi^{k-3}+\phi^{k-4} \\[8pt] & =\phi^{k-4}\left(\phi+1\right) \\[8pt] & =\phi^{k-4}\phi^2 \\[8pt] & =\phi^{k-2} \end{align*}\]

as desired.

This may seem like a slight improvement (i.e. the base has increased from 1.5 to \(\phi\)), but this small change in base means much more growth in the long term.

1.7 Universal Property of Natural Numbers

Theorem 1.14 (Universal Property of Natural Numbers) Let \(S\) be any set, \(f:S\to S\) be any function, and let \(x_0\in S\). Then there exists a unique function \(\phi:\mathbb{N}\to S\) such that \(\phi(1)=x_0\) and \(\phi\circ s=f\circ \phi\).

Proof. We will rely upon the set-theoretic principle that a subset \(\Gamma\subseteq A\times B\) is the graph of a function from \(A\) to \(B\) if and only if \(p:\Gamma\to A\) is a bijection. We wish to construct a mapping \(\phi:\mathbb{N}\to S\) and so \(p:\Gamma \to \mathbb{N}\) must be a bijection with graph \(\Gamma\subseteq \mathbb{N}\times S\). We also insist that \(\phi(1)=x_0\) which means \((1,x_0)\in \Gamma\). Since \(\Gamma\) is expected to be the graph of the yet unconstructed function \(\phi\), for any \(n\in \mathbb{N}\), we must have elements of the form \((n, \phi(n)) \in \Gamma\). So, if \((n, t) \in \Gamma\), then \(t\) is expected to be \(\phi(n)\). Then, the second condition says that \(\phi(s(n)) = f(\phi(n))\) and hence \((s(n),f(t)) \in \Gamma\). This says, if we prescribe \(\theta : \mathbb{N}\times S \to \mathbb{N}\times S\) as \(\theta(n,t) = (s(n),f(t))\), then \(\theta(\Gamma) \subseteq \Gamma\). So let \(\theta\) be so prescribed, we see that these three conditions ensure what we need:

  • \(p:\Gamma\to A\) is a bijection
  • \((1,x_0)\in \Gamma\)
  • \(\theta(\Gamma) \subseteq \Gamma\).
Let \(\mathcal{C}\) be the set of all subsets of \(\mathbb{N} \times S\) satisfying \((ii)\) and \((iii)\). Notice that \((1,x_0)\in \mathbb{N}\times S\), and so \(\mathbb{N}\times S\) satisfies \((ii)\). If \((s(n),f(t))\in \theta(\mathbb{N}\times S)\), then by the definitions of \(s\) and \(f\) we see that \((s(n),f(t))\in \mathbb{N}\times S\), and so \(\mathbb{N}\times S\) satisfies \((iii)\). Then \(\mathbb{N} \times S \in \mathcal{C}\), and hence this collection is nonempty. \(b)\) and \(c)\): Let \(\Gamma\) be the intersection of all elements in \(\mathcal{C}\). First let us check that \(\Gamma\in\mathcal{C}\). This is easy, since \((1, x_0) \in X\) for all \(X \in \mathcal{C}\) and \(\Gamma\) being the intersection of such sets, \((1,x_0) \in\Gamma\). Similarly, for any \(X \in\mathcal{C}\), \(\theta(\Gamma) \subseteq \theta(X) \subseteq X\) and thus \(\theta(\Gamma) \subseteq X\) for all \(X \in \mathcal{C}\). So, by definition of \(\Gamma\), \(\theta(\Gamma) \subseteq \Gamma\). So, \(\Gamma\) satisfies \(b)\) and \(c)\), and hence \(\Gamma \in \mathcal{C}\). \(a)\): First, consider the set \(G = \theta(\Gamma) \cup \{(1, x_0)\}\). Then clearly \(G \subseteq \Gamma\). On the other hand, \((1,x_0) \in G\) and \[ \theta(G) \subseteq \theta(\theta(\Gamma))\cup \theta(\{(1,x_0)\} \subseteq \theta(\Gamma) \subseteq G. \] So, \(G \in \mathcal{C}\) and thus by definition of \(\Gamma\), we get \(\Gamma \subseteq G\). This shows that \[\begin{equation} \label{gisgam} \theta(\Gamma) \cup \{(1, x_0)\} = G = \Gamma. \end{equation}\] We prove that \(p : \Gamma \to\mathbb{N}\) is a bijection by applying induction to the set, \[ T = \{n \in \mathbb{N} \mid p^{-1}(n) \subseteq \Gamma \text{ has exactly one element}\}. \] Notice that if \(T = \mathbb{N}\), then \(p\) is a bijection. We have \(p(1,x_0) = 1\) and we wish to show that \(p^{-1}(1) = \{(1,x_0)\}\). If not, say \((1,t) \in p^{-1}(1)\) with \(t\neq x_0\). By \(\eqref{gisgam}\), we see that \((1, t) \in \theta(\Gamma)\). So, there exists an element \((n, u) \in \Gamma\) such that \((1, t) = \theta(n, u) = (s(n), f (u))\). This says in particular, \(1 = s(n)\) contradicting Peano’s axiom. This proves that \(p^{-1}(1) = \{(1,x_0)\}\) and hence \(1 \in T\).

Next, assume that \(n \in T\). Then by definition, we have \(p^{-1}(n) = \{(n, w)\}\). Since \((n, w) \in \Gamma\), we know that \(\theta(n, w) = (s(n), f(w)) \in \Gamma\), since \(\theta(\Gamma) \subseteq \Gamma\). Thus \(p^{-1}(s(n))\) contains \((s(n),f(w))\). If we can show this is the only element in this set, we would have shown \(s(n) \in T\) and then by induction, we would be done. So, assume that \((s(n),x) \in \Gamma\) and we want to show that \(x = f(w)\). By Peano’s axiom, \((s(n),x)\neq (1,x_0)\) and hence, from \(\eqref{gisgam}\), we see that \((s(n),x) \in \theta(\Gamma)\) and thus there is an element \((m, y) \in \Gamma\) with \(\theta(m, y) = (s(n), x)\). Then \(s(m) = s(n)\) and \(f(y) = x\). By injectivity of \(s\), we get \(m = n\). Since \((m,y)=(n,y)\in \Gamma\) and \(n \in T\) implies \(y=w\). Then \(x=f(w)\) and thus \((s(n), x) = (s(n), f(w))\) proving what we set out to prove. Thus \(T = \mathbb{N}\) and hence \(p\) is a bijection.

1.8 Exercises

Exercise 1.1 Conjecture a formula for the sum of the first \(n\) even positive integers. Prove your result using mathematical induction.

Exercise 1.2 Show that the sum of consecutive odd natural numbers beginning with 1 is a square.

Exercise 1.3 Prove that \(2^{n+1}> n+2\) for every positive integer \(n\).

Exercise 1.4 Prove that a set with \(n\) elements has exactly \(2^n\) subsets.

Exercise 1.5 Prove that, for all positive integers \(n\),

\[\sum _{j=1}^n (-1)^{j-1}j^2=(-1)^{n-1}\frac{n(n+1)}{2}.\]

Exercise 1.6 Prove that, for all positive integers \(n\),

\[\sum _{j=1}^n j\cdot j! =(n+1)!-1.\]

Exercise 1.7 Use mathematical induction to show that the sum of the first \(n\) odd cubes is \(n^2\left(2n^2-1\right).\)

Exercise 1.8 Use mathematical induction to prove that \(2^n<n!\) for \(n\geq 4.\)

Exercise 1.9 Use mathematical induction to prove that \(3^n>3n-1\) for every positive integer \(n.\)

Exercise 1.10 Prove that \(0<a<b\) then \(0<a^n<b^n\) for all positive integers \(n\).

Exercise 1.11 Use mathematical induction to prove that \(3^n > n^3\) for \(n>4\).

Exercise 1.12 Use the strong form of mathematical induction to establish that for all \(n\geq 1,\)

\[ a^n-1=(a-1)\left(a^{n-1}+a^{n-2}+a^{n-3}+\cdots+a+1\right).\]

Exercise 1.13 Show that any amount of postage that is an integer number of cents greater than 53 cents can be formed using just 7-cent and 10-cent stamps.

Exercise 1.14 Use mathematical induction to prove that \(x-y\) is a factor of \(x^n-y^n,\) where \(x\) and \(y\) are variables.

Exercise 1.15 Use mathematical induction to prove the inequality. For all \(n\geq 1\),

\[ \frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots +\frac{n}{2^n}\leq 2-\frac{n+2}{2^n}. \]

Exercise 1.16 Use mathematical induction to prove that \(2^n > n^2\) for \(n>4\).

Exercise 1.17 Use mathematical induction to show that for every positive integer \(n,\)

\[\sum _{i=1}^n 2^k=2^{n+1}-2.\]

Exercise 1.18 You have a supply of \(32\) cent stamps and \(21\) cent stamps. You need to mail a package which requires \(1.48\) dollars in postage. How many of each type of stamp should you use? Can you prove it?

Exercise 1.19 Prove \(2 n<7^n\) whenever \(n\) is a positive integer.

Exercise 1.20 Find the Fibonacci numbers \(f_{24}\), \(f_{32}\), and \(f_{44}\).

Exercise 1.21 Write out the first 50 Fibonacci numbers.

Exercise 1.22 Show that \(f_{n+3}+f_n=2f_{n+2}\) whenever \(n\) is a positive integer.

Exercise 1.23 Show that \(f_{n+3}-f_n=2f_{n+1}\) whenever \(n\) is a positive integer.

Exercise 1.24 Show that \(f_{n-2}+f_{n+2}=3f_n\) whenever \(n\) is a positive integer with \(n\geq 2.\)

Exercise 1.25 Show that \(f_{2n}=f_{n}^2+2f_{n-1}f_n\) whenever \(n\) is a positive integer with \(n\geq 2.\)

Exercise 1.26 Show that \(f_{2n+1}=f_{n+1}^2+f_{n}^2\) whenever \(n\) is a positive integer.

Exercise 1.27 Show that \(f_{2n}=f_{n+1}^2-f_{n-1}^2\) whenever \(n\) is a positive integer.

Exercise 1.28 Show that for all positive integers \(n,\)
\[f_1 f_2 + \left(f_2 f_3 + f_3 f_4 \right) + \cdots + \left( f_{2n-2} f_{2n-1} + f_{2n-1} f_{2n} \right) = \left( f_{2n} \right)^2.\]

Exercise 1.29 Prove that \(f_{n+2}^2-f_{n+1}^2=f_n f_{n+3}\) , for all \(n\geq 1\).

Exercise 1.30 Prove that \(f_{n+1}f_n-f_{n-1}f_{n-2}=f_{2n-1}\) for every positive integer \(n\), \(n>2\).

Exercise 1.31 Prove that \(f_1 f_2+f_2f_3+\cdots +f_{2n-1}f_{2n}=f_{2n}^2\) for every positive integer \(n\).

Exercise 1.32 Prove that \(f_{m+n}=f_m f_{n+1}+f_n f_{m-1}\) for every positive integer \(n\).

Exercise 1.33 Prove that \(f_n>\left(\frac{5}{3}\right)^{n-1}\), for all \(n\geq 2\).

Exercise 1.34 Show that for \(n\geq 2\), \[ f_n=\frac{f_{n-1}+\sqrt{5 f_{n-1}^2+4(-1)^n}}{2} \] Notice that this formula gives \(f_n\) in terms of one predecessor rather than two predecessors.

Exercise 1.35 Let \(F=\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}\). Show that \[ F^n= \begin{bmatrix}f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix} \] for all \(n\geq 1\).

Exercise 1.36 Let \(a_0=1\) and, for \(n>0\), let \(a_n=2 a_{n-1}+1\). The first few terms of the sequence are 1,3,7,15. What are the next fews terms? Prove that \(a_n=2^{n+1}-1\) for all positive integers.

Exercise 1.37 Let \(b_0=1\) and, for \(n>0\), let \(b_n=3 b_{n-1}-1\). What are the first five terms of the sequence? Prove that \(b_n=(3^{n}+1)/2\) for all positive integers.

Exercise 1.38 Find the first 50 Lucas numbers.

Exercise 1.39 Find and prove a formula for the sum of the first \(n\) Lucas numbers when \(n\) is a positive integer.

Exercise 1.40 Find and prove a formula for the sum of the first \(n\) Lucas numbers with odd indices when \(n\) is a positive integer.

Exercise 1.41 Find and prove a formula for the sum of the first \(n\) Lucas numbers with even indices when \(n\) is a positive integer.

Exercise 1.42 Show that \(f_{2n}=f_n L_n\) for all positive integers \(n\).

Exercise 1.43 Prove that \(L_{m+n}=f_{m+1}L_n+f_mL_{n-1}\) whenever \(m\) and \(n\) are positive integers with \(n>1\).

Exercise 1.44 Prove that \(L_n=\phi^n+\tau^n\) where \(\phi\) is the golden ratio and \(\tau\) its conjugate.

Exercise 1.45 Establish each of the following for all \(n\in \mathbb{N}\).

  • \(L_n-5 f_n^2=4(-1)^n\)
  • \(L_{2n}=L_n^2-2(-1)^n\)
  • \(f_{n+1}+f_{n-1}=L_n\)
  • \(L_{n+1}+L_{n-1}=5 f_n\)
  • \(L_{2n+1}=L_n L_{n+1}-(-1^n)\)
  • \(L_{n-1}L_{n+1}-L_n^2=5(-1)^{n-1}\), \(n\geq 2\)