Proof by Exhaustion (Edexcel A-Level Mathematics): Revision Notes

Example: Prove that the sum of two odd numbers is always even for all cases involving single-digit odd numbers.

Step 1: Identify possible cases

The single-digit odd numbers are: 1, 3, 5, 7, 9

Step 2: List all pairings of odd numbers:

• $1 + 1$
• $1 + 3$
• $1 + 5$
• $1 + 7$
• $1 + 9$
• $3 + 3$
• $3 + 5$
• $3 + 7$
• $3 + 9$
• $5 + 5$
• $5 + 7$
• $5 + 9$
• $7 + 7$
• $7 + 9$
• $9 + 9$

Step 3: Calculate each sum

• $1 + 1 = 2$ (even)
• $1 + 3 = 4$ (even)
• $1 + 5 = 6$ (even)
• $1 + 7 = 8$ (even)
• $1 + 9 = 10$ (even)
• $3 + 3 = 6$ (even)
• $3 + 5 = 8$ (even)
• $3 + 7 = 10$ (even)
• $3 + 9 = 12$ (even)
• $5 + 5 = 10$ (even)
• $5 + 7 = 12$ (even)
• $5 + 9 = 14$ (even)
• $7 + 7 = 14$ (even)
• $7 + 9 = 16$ (even)
• $9 + 9 = 18$ (even)

Step 4: Conclusion

Since all possible cases yield even results, we conclude that the sum of two odd numbers is always even.

This is an example of proof by exhaustion, as we've checked every possible case.

Example: Prove by exhaustion that 47 is prime.

• The idea: Check every possible factor of $47$ to see if an integer is obtained.
• $\frac{47}{2} = 23.5$ : not a factor
• $\frac{47}{3} = 15.6$ : not a factor
• $\frac{47}{4} = 11.75$ : not a factor
• $\frac{47}{5} = 9.4$ : not a factor
• $\frac{47}{6} = 7.83$ : not a factor

Note: Only need to go up to the last integer less than $\sqrt{36} = 6$

Conclusion

• Since all integers $2 \leq n \leq \sqrt{47}$ are not factors of $47$,
• Therefore, 47 is prime.