Proof by Exhaustion

Applying Proof by Exhaustion: An Illustrative Example

Consider the conjecture that for any integer \(n\) that is not a multiple of 3, the expression \(n^2-1\) is divisible by 3. To apply proof by exhaustion, one must first categorize all possible forms of \(n\). Since \(n\) is not a multiple of 3, it must be of the form \(3k + 1\) or \(3k + 2\), where \(k\) is an integer. The next step is to verify the conjecture for each form of \(n\). For \(n = 3k + 1\), squaring \(n\) and subtracting one gives \(9k^2 + 6k\), which is divisible by 3. Similarly, for \(n = 3k + 2\), the expression becomes \(9k^2 + 12k + 3\), also divisible by 3. Since the conjecture holds for all cases, the proof by exhaustion confirms the statement's validity.

When to Use Proof by Exhaustion

Proof by exhaustion is most suitable when the conjecture can be broken down into a finite and manageable number of cases. The method is not practical for conjectures with an infinite or very large number of cases due to the impracticality of checking each one. It is ideal for scenarios where the conjecture can be segmented into a finite set of distinct conditions, each of which can be individually verified. This approach is particularly useful in discrete mathematics, where the elements under consideration are countable and the cases are well-defined.

Examples of Proof by Exhaustion in Action

Proof by exhaustion has been employed in various mathematical proofs. For example, to show that for any integer \(n\) between 2 and 7, the expression \(n^2 + 2\) is not a multiple of 4, one can evaluate the expression for each integer value of \(n\) within the range, confirming the statement for each case. Another instance is proving that for any prime number \(p\) between 3 and 25, the product \((p - 1)(p + 1)\) is divisible by 12. By examining each prime number within the specified range, the statement is validated. Additionally, the divisibility of \(n^7-n\) by 7 for all positive integers \(n\) can be confirmed by considering cases where \(n\) is a multiple of 7 or when \(n\) has a remainder of 1 through 6 upon division by 7. These examples showcase the effectiveness of proof by exhaustion in providing conclusive evidence for mathematical conjectures.

Key Takeaways from Proof by Exhaustion

Proof by exhaustion is a fundamental technique in mathematics for establishing the truth of statements that can be categorized into a finite set of cases. It involves a systematic process of identifying all possible scenarios and then proving the conjecture for each one. This method is comprehensive, as it accounts for every potential case, thereby offering a robust validation of the conjecture. While it can be labor-intensive, proof by exhaustion is an indispensable tool in the mathematician's toolkit for proving statements that are amenable to such an approach.