Example of a Proof by Smallest Counter-Example

Image
Proposition If n ∈ N, then 4 | (5n −1). Proof. We use proof by smallest counterexample. (We will number the steps to match the outline, but that is not usually done in practice.) (1) If n = 1, then the statement is 4 | (51 −1), or 4 | 4, which is true. (2) For sake of contradiction, suppose it’s not true that 4 | (5n −1) for all n. (3) Let k > 1 be the smallest integer for which 4 - (5k −1). (4) Then 4 | (5k−1 −1), so there is an integer a for which 5k−1 −1 = 4a. Then 5k−1 −1 = 4a 5(5k−1 −1) = 5·4a 5k −5 = 20a 5k−1 = 20a+4 5k −1 = 4(5a+1). This means 4 | (5k−1), a contradiction, because 4 - (5k−1) in Step 3. Thus, we were wrong in Step 2 to assume that it is untrue that 4 | (5n −1) for every n. Therefore 4 | (5n −1) is true for every n.

Explanation of the proof:

The given proof is a proof by contradiction using the method of smallest counterexample to show that for every natural number n, 4 | (5n - 1). Let's break down the steps of the proof: 1. Base case: Check the statement for n = 1. The base case shows that the proposition holds true for at least one natural number. For n = 1, we have 4 | (51 - 1) = 4 | 4, which is true. 2. Assumption for contradiction: Assume the proposition is false for some n. The proof begins by assuming that there exists a counterexample, i.e., there is at least one natural number n for which 4 does not divide (5n - 1). 3. Smallest counterexample: Find the smallest integer k for which the proposition fails. Among all the natural numbers where the proposition is false, let k be the smallest such number. 4. Express k in terms of a new integer a. Since the proposition is false for k, we have 4 does not divide (5k - 1). Thus, there is an integer a for which 5k - 1 = 4a. 5. Rewrite the expression for k in terms of a. Now, manipulate the equation 5k - 1 = 4a to express k in terms of a: 5k - 1 = 4a 5(5k - 1) = 5 * 4a 5k - 5 = 20a 5k - 1 = 20a + 4 5k - 1 = 4(5a + 1). 6. Reach a contradiction. Since 4 divides (5k - 1) (as expressed in step 5), it contradicts the assumption made in step 3 that k is the smallest counterexample. 7. Conclude the proof. The contradiction shows that our assumption in step 2 was wrong, and there is no smallest counterexample. Therefore, the proposition "4 | (5n - 1)" is true for every natural number n. In conclusion, the proof establishes that for every natural number n, 4 divides (5n - 1).