In this section, we will discuss a proof method that is used to prove statements that are true for all positive integers. Before we discuss the method, let us look at some motivating examples.
Subsection5.2Mathematical Induction
Suppose that we want to prove a statement \(S(n)\) that has a free variable \(n\), where \(n\) can be any natural number. A priori, we need to prove that \(S(1), S(2), S(3), \dots\)are all true. If we were to prove \(S(n)\) is true by proving that \(S(1), S(2), S(3), \dots\) are true one by one, we will never stop as there are infinitely many of them. Mathematical induction is designed to prove statements like this. Let us think of statements \(S(1), S(2), S(3), \dots\) as dominos and they are lined up in a row. Suppose that we can prove \(S(1)\), and symbolize this as domino \(S(1)\) being knocked down. Suppose that we can prove any statement \(S(k)\) being true implies that the next statement \(S(k + 1)\) to be true. This is equivalent to say that domino \(S(k)\) and domino \(S(k+1)\) are close enough that if \(S(k)\) is knocked down, then \(S(k+1)\) will also be knocked down. As \(k\) is an arbitrary natural number, this tells us that all the dominos \(S(k)\)’s are lined up close enough such that whenever the first domino \(S(1)\) falls, all the dominos will fall. There are infinitely many linkage between dominos, we have to prove infinitely many statements (and we cannot finish the job if we were to prove it one by one). But the trick is to establish all the links in one shot! Here is what the general structure using the mathematical induction to prove that \(S(n)\) is true for all natural number \(n\) looks like.
We proceed by induction on \(n\).
- Base step: Prove that the first statement \(S(1)\) is true.
- Inductive step: Given any integer \(k \geq 1\), suppose that \(S(k)\) is true. Then prove that \(S(k+1)\) is true. \begin{equation*}\text{(Use definitions and previous results)}\end{equation*}
- It follows by mathematical induction that every \(S(n)\) is true.
Task5.3
Show that for every \(n \in \mathbb{N}\), we have\begin{equation*}1^2+2^2+3^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}.\end{equation*}
Task5.4
Show that for every \(n \in \mathbb{N}\), we have\begin{equation*}1^3+2^3+3^3+\cdots+n^3=(1+2+3+\cdots+n)^2.\end{equation*}
Task5.5
Let \(n \in \mathbb{N}\). Conjecture a formula for \begin{equation*}a_n = \frac{1}{(1)(2)} + \frac{1}{(2)(3)} + \frac{1}{(3)(4)} + \cdots + \frac{1}{(n)(n+1)}\end{equation*} and prove your conjecture using mathematical induction.
Task5.6
Let \(x \neq 1\) be a real number. For all \(n \in \mathbb{N}\), we have \begin{equation*}\frac{x^n-1}{x-1} = x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1.\end{equation*}
Task5.7
Show that \(6\) divides \(2n^3+3n^2+n\) for all \(n \in \mathbb{N}\).
Task5.8
Show that \(12\) divides \(n^4-n^2\) for all \(n \in \mathbb{N}\).
Task5.9
Suppose that every car has only one color and we want to prove that every collection of \(n\) cars have the same color for all natural number \(n\). What do you think about the following proof using mathematical induction?
We proceed by induction on \(n\).
- Base step: If \(n=1\), then the collection has only one car and clearly all cars in that collection have the same color.
- Inductive step: Given any integer \(k \geq 1\), suppose that any collection of \(k\) cars have the same color. We want to prove that any collection of \(k+1\) cars have the same color. Let us pick a collection of \(k+1\) cars \begin{equation*}C = \{c_1, c_2, \dots, c_{k+1}\}\end{equation*} where each \(c_i\) stands for one car in the collection for all \(1 \leq i \leq k+1\). Let us denote\begin{equation*}C_1 = \{c_1, c_2, \dots, c_k\}\end{equation*} as a subcollection of \(C\). As \(C_1\) has \(k\) cars, we know that all cars in \(C_1\) have the same color by the inductive hypothesis. Let us denote \begin{equation*}C_2 = \{c_2, c_3, \dots, c_{k+1}\}\end{equation*} as another subcollection of \(C\). As \(C_2\) has \(k\) cars, we know that all cars in \(C_2\) have the same color by the inductive hypothesis. The car \(c_1\) has the same color as the cars in the middle, who in turn are of the same color as the last car \(c_{k+1}\). Hence the first car, middle cars, and the last car all have the same color.
- It follows by mathematical induction that every collection of \(n\) cars have the same color for all natural number \(n=1\).
Task5.10
Prove that every positive integer is either odd or even.
Task5.11
Prove your conjecture in Task 4.30.
Subsection5.3Generalized Strong Induction
Let us try to use mathematical induction to prove the following problem: Every natural number \(n \geq 2\) has a prime factor.
First we see that the natural number \(n\) does not start with \(1\) as we require in mathematical induction. But this is not a difficult problem to solve. For any natural number \(n\), let \(S(n)\) be the following statement: \(n\) has a prime factor. We need to show that \(S(n)\) is true for all \(n \geq 2\). If we think of the domino analogy, the only change that we have to make is to prove that \(S(2)\) is true in the basic step. This is not hard to show because \(2\) has a prime factor \(2\).
Now we come to the inductive step. Suppose that for some \(k \geq 2\), there exists a prime number \(p\) such that \(p \; | \; k\). Now we need to show that there exists some prime number \(q\) such that \(q \; | \; (k+1)\).
But if we look at some concrete examples, often prime factors of a number \(k\) has nothing to do with prime factors of \(k+1\). For example, the only prime factor of \(23\) is \(23\) but primes factors of \(24\) are \(2\) and \(3\). Note that \(12\) is a factor of \(24\) and prime factors of \(12\) are also \(2\) and \(3\). From this concrete example, we see that primes factors of \(k+1\) may have nothing to do with prime factors of \(k\) but may have a lot to do with prime factors of a factor (not necessarily prime factors) of \(k+1\). Put it in more general words, to show that \(S(k+1)\) is true, knowing that \(S(k)\) is true does not really help but maybe knowing that \(S(i)\) is true for \(i \leq k\) may help. Think of the domino analogy, this is saying that the first \(k\) dominos falling makes the \((k+1)\)-th domino fall, then all the dominos must fall.
Now let us go back to our problem. Suppose that for all \(2 \leq i \leq k\), the number \(i\) has a prime factor. We need to show that \((k+1)\) has a prime factor. If \((k+1)\) is a prime number, then we are done because \((k+1)\) is a factor of itself. If \((k+1)\) is not a prime number, then there must be some factor \(x\) of \((k+1)\) such that \(2 \leq x \leq k\). By the inductive hypothesis, we know that \(x\) has a prime factor \(p\). Because \(p \; | \; x\) and \(x \; | \; (k+1)\), we know that \(p \; | \; (k+1)\) by Task 3.22. Hence \((k+1)\) has a prime factor \(p\) and we are done with the induction.
What we did in the last paragraph is called the generalized strong induction. The word "generalized" means that the induction can start with any number and not just \(1\). The word "strong" means that in the inductive step, we can assume \(S(i)\) is true for all \(i \leq k\) and not just assuming \(S(k)\) is true alone.
Here is what the general structure using the generalized strong mathematical induction to prove that \(S(n)\) is true for all natural number \(n \geq m\) looks like.
We proceed by induction on \(n\).
- Base step: Prove that the first statement \(S(m)\) is true.
- Inductive step: Given any integer \(k \geq m\), suppose that \(S(i)\) is true for all \(m \leq i \leq k\). Then prove that \(S(k+1)\) is true. \begin{equation*}\text{(Use definitions and previous results)}\end{equation*}
- It follows by mathematical induction that every \(S(n)\) is true for \(n \geq m\).
Other than the fact that the generalized strong induction can start at any number we want (as opposed to \(n=1\) in the standard mathematical induction), the most important feature of the generalized strong induction is that instead of just having one inductive hypothesis like in the standard induction (\(S(k)\) is true), now we have lots of inductive hypotheses at our disposal (\(S(i)\) is true for all \(i \leq k\).) Every problem that can be solved by using the standard mathematical induction can be solved by the generalized strong induction. In fact, it is almost always easier to use the generalized strong induction because in the inductive step, there are more inductive hypotheses that we can use.
Task5.12
Prove that for any natural \(n \geq 4\), we have \(n! \gt 2^n\).
Let us prove something about the Fibonacci sequence. The Fibonacci sequence is defined as follows: \(f_1 = 1\) and \(f_2 = 1\); for all \(n \geq 3\), \(f_n = f_{n-1} + f_{n-2}\).
Task5.13
Calculate the first ten Fibonacci numbers \(f_1, f_2, \dots, f_{10}\). Use generalized strong induction to show that \(f_{n+6} = 4f_{n+3}+f_n\) for all natural number \(n\).
Task5.14
For any natural number \(a\), show that \begin{equation*}f_af_n+f_{a+1}f_{n+1} = f_{a+n+1}\end{equation*} for all natural number \(n\).
Task5.15
Let \begin{equation*}\alpha = \frac{1+\sqrt{5}}{2}, \qquad \beta = \frac{1-\sqrt{5}}{2}.\end{equation*} Show that for all natural numbers \(n\) that \begin{equation*}f_n =\frac{\alpha^n-\beta^n}{\alpha - \beta}.\end{equation*}
Clearly, every number in the Fibonacci sequence is an integer, but interestingly, the closed formula to compute it contains irrational number \(\sqrt{5}\).
