Appendix B: Mathematical Induction
- Page ID
- 77606
B.1: The Principle of Mathematical Induction
B.1.1: The Ideas Behind Mathematical Induction
There is a variant of one of the bijections we used to prove the Pascal Equation that comes up in counting the subsets of a set. In the next problem, it will help us compute the total number of subsets of a set, regardless of their size. Our main goal in this problem, however, is to introduce some ideas that will lead us to one of the most powerful proof techniques in combinatorics (and many other branches of mathematics), the principle of mathematical induction.
Exercise \(360\)
a. Write down a list of the subsets of \(\{1, 2\}\). Don’t forget the empty set! Group the sets containing \(2\) separately from the others.
b. Write down a list of the subsets of \(\{1, 2, 3\}\). Group the sets containing \(3\) separately from the others.
c. Look for a natural way to match up the subsets containing \(2\) in Part a. with those not containing \(2\). Look for a way to match up the subsets containing \(3\) in Part b. containing \(3\) with those not containing \(3\).
d. On the basis of the previous part, you should be able to find a bijection between the collection of subsets of \(\{1, 2,..., n\}\) containing \(n\) and those not containing \(n\). (If you are having difficulty figuring out the bijection, try rethinking Parts a and b, perhaps by doing a similar exercise with the set \(\{1, 2, 3, 4\}\).) Describe the bijection (unless you are very familiar with the notation of sets, it is probably easier to describe to describe the function in words rather than symbols) and explain why it is a bijection. Explain why the number of subsets of \(\{1, 2,..., n\}\) containing n equals the number of subsets of \(\{1, 2,..., n − 1\}\).
(e) Parts a. and b. suggest strongly that the number of subsets of a \(n\)-element set is \(2n\). In particular, the empty set has \(20\) subsets, a one-element set has \(21\) subsets, itself and the empty set, and in Parts a. and b. we saw that two-element and three-element sets have \(22\) and \(23\) subsets respectively. So there are certainly some values of \(n\) for which an \(n\)-element set has \(2n\) subsets. One way to prove that an \(n\)-element set has \(2n\) subsets for all values of \(n\) is to argue by contradiction. For this purpose, suppose there is a nonnegative integer \(n\) such that an \(n\)-element set doesn’t have exactly \(2n\) subsets. In that case, there may be more than one such \(n\). Choose \(k\) to be the smallest such \(n\). Notice that \(k − 1\) is still a positive integer, because \(k\) can’t be \(0\), \(1\), \(2\), or \(3\). Since \(k\) was the smallest value of \(n\) we could choose to make the statement “An \(n\)-element set has \(2n\) subsets” false, what do you know about the number of subsets of a \((k − 1)\)-element set? What do you know about the number of subsets of the \(k\)-element set \(\{1, 2,..., k\}\) that don’t contain \(k\)? What do you know about the number of subsets of \(\{1, 2,..., k\}\) that do contain \(k\)? What does the sum principle tell you about the number of subsets of \(\{1, 2,..., k\}\)? Notice that this contradicts the way in which we chose \(k\), and the only assumption that went into our choice of \(k\) was that “there is a nonnegative integer \(n\) such that an \(n\)-element set doesn’t have exactly \(2n\) subsets." Since this assumption has led us to a contradiction, it must be false. What can you now conclude about the statement “for every nonnegative integer \(n\), an \(n\)-element set has exactly \(2n\) subsets?"
Exercise \(361\)
The expression
\(1+3+5+ ··· + 2n − 1\)
is the sum of the first n odd integers. Experiment a bit with the sum for the first few positive integers and guess its value in terms of \(n\). Now apply the technique of Problem 360 to prove that you are right. (Hint).
In Problems 360 and 361, our proofs had several distinct elements. We had a statement involving an integer \(n\). We knew the statement was true for the first few nonnegative integers in Problem 360 and for the first few positive integers in Problem 361. We wanted to prove that the statement was true for all nonnegative integers in Problem 360 and for all positive integers in Problem 361. In both cases we used the method of proof by contradiction; for that purpose we assumed that there was a value of \(n\) for which our formula wasn’t true. We then chose \(k\) to be the smallest value of \(n\) for which our formula wasn’t true. This meant that when \(n\) was \(k − 1\), our formula was true, (or else that \(k − 1\) wasn’t a nonnegative integer in Problem 360 or that \(k − 1\) wasn’t a positive integer in Problem 361). What we did next was the crux of the proof. We showed that the truth of our statement for \(n = k −1\) implied the truth of our statement for \(n = k\). This gave us a contradiction to the assumption that there was an \(n\) that made the statement false. In fact, we will see that we can bypass entirely the use of proof by contradiction. We used it to help you discover the central ideas of the technique of proof by mathematical induction.
The central core of mathematical induction is the proof that the truth of a statement about the integer \(n\) for \(n = k − 1\) implies the truth of the statement for \(n = k\). For example, once we know that a set of size \(0\) has \(2^0\) subsets, if we have proved our implication, we can then conclude that a set of size \(1\) has \(2^1\) subsets, from which we can conclude that a set of size \(2\) has \(2^2\) subsets, from which we can conclude that a set of size \(3\) has \(2^3\) subsets, and so on up to a set of size \(n\) having \(2^n\) subsets for any nonnegative integer \(n\) we choose. In other words, although it was the idea of proof by contradiction that led us to think about such an implication, we can now do without the contradiction at all. What we need to prove a statement about \(n\) by this method is a place to start, that is a value \(b\) of \(n\) for which we know the statement to be true, and then a proof that the truth of our statement for \(n = k − 1\) implies the truth of the statement for \(n = k\) whenever \(k > b\).
B.1.2: Mathematical Induction
The principle of mathematical induction states that:
In order to prove a statement about an integer \(n\), if we can
- Prove the statement when \(n = b\), for some fixed integer \(b\)
- Show that the truth of the statement for \(n = k −1\) implies the truth of the statement for \(n = k\) whenever \(k > b\),
then we can conclude the statement is true for all integers \(n ≥ b\). As an example, let us return to Problem 360. The statement we wish to prove is the statement that “A set of size \(n\) has \(2n\) subsets.”
Our statement is true when \(n = 0\), because a set of size \(0\) is the empty set and the empty set has \(1=2^0\) subsets. (This step of our proof is called a base step.) Now suppose that \(k > 0\) and every set with \(k − 1\) elements has \(2^{k−1}\) subsets. Suppose \(S = \{a_1, a_2,... a_k \}\) is a set with \(k\) elements. We partition the subsets of \(S\) into two blocks. Block \(B_1\) consists of the subsets that do not contain an and block \(B_2\) consists of the subsets that do contain \(a_n\). Each set in \(B_1\) is a subset of \(\{a_1, a_2,... a_{k−1}\}\), and each subset of \(\{a_1, a_2,... a_{k−1}\}\) is in \(B_1\). Thus \(B_1\) is the set of all subsets of \(\{a_1, a_2,... a_{k−1}\}\). Therefore by our assumption in the first sentence of this paragraph, the size of \(B_1\) is \(2^{k−1}\). Consider the function from \(B_2\) to \(B_1\) which takes a subset of \(S\) including an and removes \(a_n\) from it. This function is defined on \(B_2\), because every set in \(B_2\) contains \(a_n\). This function is onto, because if \(T\) is a set in \(B_1\), then \(T ∪ \{a_k \}\) is a set in \(B_2\) which the function sends to \(T\). This function is one-to-one because if \(V\) and \(W\) are two different sets in \(B_2\), then removing \(a_k\) from them gives two different sets in \(B_1\). Thus we have a bijection between \(B_1\) and \(B_2\), so \(B_1\) and \(B_2\) have the same size. Therefore by the sum principle the size of \(B_1 ∪ B_2\) is \(2^{k−1} + 2^{k−1} = 2k\). Therefore \(S\) has \(2^k\) subsets. This shows that if a set of size \(k − 1\) has \(2^{k−1}\) subsets, then a set of size \(k\) has \(2^k\) subsets. Therefore by the principle of mathematical induction, a set of size \(n\) has \(2^n\) subsets for every nonnegative integer \(n\).
The first sentence of the last paragraph is called the inductive hypothesis. In an inductive proof, we always make an inductive hypothesis as part of proving that the truth of our statement when \(n = k − 1\) implies the truth of our statement when \(n = k\). The last paragraph itself is called the inductive step of our proof. In an inductive step, we derive the statement for \(n = k\) from the statement for \(n = k − 1\), thus proving that the truth of our statement when \(n = k − 1\) implies the truth of our statement when \(n = k\). The last sentence in the last paragraph is called the inductive conclusion. All inductive proofs should have a base step, an inductive hypothesis, an inductive step, and an inductive conclusion.
There are a couple details worth noticing. First, in this problem, our base step was the case \(n = 0\), or in other words, we had \(b = 0\). However, in other proofs, \(b\) could be any integer, positive, negative, or \(0\). Second, our proof that the truth of our statement for \(n = k − 1\) implies the truth of our statement for \(n = k\) required that \(k\) be at least \(1\), so that there would be an element \(a_k\) we could take away in order to describe our bijection. However, condition (2) of the principle of mathematical induction only requires that we be able to prove the implication for \(k > 0\), so we were allowed to assume \(k > 0\).
Exercise \(362\)
Use mathematical induction to prove your formula from Problem 361.
B.1.3: Proving Algebraic Statements by Induction
Exercise \(363\)
Use mathematical induction to prove the well-known formula that for all positive integers \(n\),
\(1+2+ ··· + n = \dfrac{n(n + 1)}{2}\).
Exercise \(364\)
Experiment with various values of \(n\) in the sum
\(\dfrac{1}{1 · 2} + \dfrac{1}{2 · 3} + \dfrac{1}{3 · 4} + ··· + \dfrac{1}{n · (n + 1)} = \sum_{i=1}^{n} \dfrac{1}{i · (i + 1)}\).
Guess a formula for this sum and prove your guess is correct by induction.
Exercise \(365\)
For large values of \(n\), which is larger, \(n^2\) or \(2^n\)? Use mathematical induction to prove that you are correct. (Hint).
Exercise \(366\)
What is wrong with the following attempt at an inductive proof that all integers in any consecutive set of \(n\) integers are equal for every positive integer \(n\)? For an arbitrary integer \(i\), all integers from \(i\) to \(i\) are equal, so our statement is true when \(n = 1\). Now suppose \(k > 1\) and all integers in any consecutive set of \(k −1\) integers are equal. Let \(S\) be a set of \(k\) consecutive integers. By the inductive hypothesis, the first \(k − 1\) elements of \(S\) are equal and the last \(k − 1\) elements of \(S\) are equal. Therefore all the elements in the set \(S\) are equal. Thus by the principle of mathematical induction, for every positive \(n\), every \(n\) consecutive integers are equal. (Hint).
B.1.4: Strong Induction
One way of looking at the principle of mathematical induction is that it tells us that if we know the “first” case of a theorem and we can derive each other case of the theorem from a smaller case, then the theorem is true in all cases. However, the particular way in which we stated the theorem is rather restrictive in that it requires us to derive each case from the immediately preceding case. This restriction is not necessary, and removing it leads us to a more general statement of the principle of mathematical induction which people often call the strong principle of mathematical induction. It states:
In order to prove a statement about an integer \(n\) if we can
- Prove our statement when \(n = b\) and
- Prove that the statements we get with \(n = b\), \(n = b+1,... n = k−1\) imply the statement with \(n = k\),
then our statement is true for all integers \(n ≥ b\).
Exercise \(367\)
What postage do you think we can make with five and six cent stamps? Is there a number \(N\) such that if \(n ≥ N\), then we can make \(n\) cents worth of postage?
You probably see that we can make n cents worth of postage as long as \(n\) is at least \(20\). However you didn’t try to make \(26\) cents in postage by working with \(25\) cents; rather you saw that you could get \(20\) cents and then add six cents to that to get \(26\) cents. Thus if we want to prove by induction that we are right that if \(n ≥ 20\), then we can make \(n\) cents worth of postage, we are going to have to use the strong version of the principle of mathematical induction.
We know that we can make \(20\) cents with four five-cent stamps. Now we let \(k\) be a number greater than \(20\), and assume that it is possible to make any amount between \(20\) and \(k − 1\) cents in postage with five and six cent stamps. Now if \(k\) is less than \(25\), it is \(21\), \(22\), \(23\), or \(24\). We can make \(21\) with three fives and one six. We can make \(22\) with two fives and two sixes, \(23\) with one five and three sixes, and \(24\) with four sixes. Otherwise, \(k − 5\) is between \(20\) and \(k − 1\) (inclusive) and so by our inductive hypothesis, we know that \(k − 5\) cents can be made with five and six cent stamps, so with one more five cent stamp, so can \(k\) cents. Thus by the (strong) principle of mathematical induction, we can make \(n\) cents in stamps with five and six cent stamps for each \(n ≥ 20\).
Some people might say that we really had five base cases, \(n = 20\), \(21\), \(22\), \(23\), and \(24\), in the proof above and once we had proved those five consecutive base cases, then we could reduce any other case to one of these base cases by successively subtracting \(5\). That is an appropriate way to look at the proof. A logician would say that it is also the case that, for example, by proving we could make \(22\) cents, we also proved that if we can make \(20\) cents and \(21\) cents in stamps, then we could also make \(22\) cents. We just didn’t bother to use the assumption that we could make \(20\) cents and \(21\) cents! So long as one point of view or the other satisfies you, you are ready to use this kind of argument in proofs.
Exercise \(368\)
A number greater than one is called prime if it has no factors other than itself and one. Show that each positive number is either a prime or a power of a prime or a product of powers of prime numbers.
Exercise \(369\)
Show that the number of prime factors of a positive number \(n ≥ 2\) is less than or equal to \(\log_2 n\). (If a prime occurs to the \(k\)th power in a factorization of \(n\), you can consider that power as \(k\) prime factors.) (There is a way to do this by induction and a way to do it without induction. It would be ideal to find both ways.)
Exercise \(370\)
One of the most powerful statements in elementary number theory is Euclid’s Division Theorem.a This states that if \(m\) and \(n\) are positive integers, then there are unique nonnegative integers \(q\) and \(r\) with \(0 ≤ r < n\), such that \(m = nq + r\). The number \(q\) is called the quotient and the number \(r\) is called the remainder. In computer science, it is common to denote \(r\) by \(m \text{ mod } n\). In elementary school, you learned how to use long division to find \(q\) and \(r\). However, it is unlikely that anyone ever proved for you that for any pair of positive integers, \(m\) and \(n\), there is such a pair of nonnegative numbers \(q\) and \(r\). You now have the tools needed to prove this. Do so. (Hint).