Let G = {n\in N | 8n - 3n is divisible by 5}. We will use PMI to show that G = N, and it will then follow that 8n - 3n is divisible by 5 for all n\in N, which is what we need to prove. First, we observe that G \subseteq N by definition, and hence PMI is applicable. To use PMI, we need to show two things, which are that 1\in G, and that if n\in G then n + 1\in G. We start with the first of these. Observe that 8^1 - 3^1 = 5, and therefore 8^1 - 3^1 is indeed divisible by 5. Hence 1\in G, which is Part (a) of the statement of PMI.
To show Part (b) of the statement of PMI, let n\in G. We then need to deduce that n + 1\in G. Because n\in G, we know that 8n - 3n is divisible by 5, which means that there is some k\in Z such that 8n - 3n = 5k (recall the definition of divisibility in Section 2.2). To show that n+1\in G will require showing that 8n+1 -3n+1 is divisible by 5; we can make use of our hypothesis that 8n - 3n is divisible by 5 in this proof. We compute 8n+1 - 3n+1 = 8 · 8n - 3 · 3n = (5 · 8n + 3 · 8n) - 3 · 3n = 5 · 8n + 3 · (8n - 3n) = 5 · 8n + 3(5k) = 5(8n + 3k). Because n and k are integers, then 8n + 3k is an integer, and hence 8n+1 - 3n+1 is divisible by 5. It follows that n + 1\in G. We have therefore proved that Part (b) of the statement of PMI holds. PMI now implies that G = N, and the result is proved.
Proposition2.34.
If n\in N, then 1 + 2 + \cdots + n = n(n + 1) 2 .
Warning2.35.Horse Induction.
We will prove that all horses have the same color. More precisely, we will show that the statement “for any set of n horses, all the horses in the set have the same color,” is true for all n\in N. Because there are only finitely many horses in the world, it will then follow that all existing horses have the same color. First, suppose that n = 1. It is certainly true that for any set of one horse, all the horses in the set have the same color. Next, suppose that the result is true for n, so that for any set of n horses, all the horses in the set have the same color. We need to show that the result is true for n + 1. Let {H1, \dots, Hn+1} be a set of n + 1 horses. The set {H1, \dots, Hn} has n horses, so by the inductive hypothesis all the horses in this set have the same color. On the other hand, the set {H2, \dots, Hn+1} also has n horses, so all horses in this set have the same color. In particular, it then follows that Hn and Hn+1 have the same color. Combining this fact with the previous observation that horses H1, \dots, Hn all have the same color, it follows that H1, \dots, Hn+1 all have the same color. We have therefore proved the inductive step. Hence all horses have the same color.
Let k, m\in N, and let f : {1, \dots, m} \to {1, \dots, k} be a function. Prove that if m > k, then f is not injective. A combinatorial interpretation of this fact is known as the Pigeonhole Principle, which says that if m objects are placed in k boxes, where m > k, then there will be a box with more than one object in it. Though this principle may seem innocuous, it is very important in combinatorics.
