Example of a Proof by Smallest Counter-Example
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).