Proof by Deduction and Exhaustion
Argue from what is given to what is claimed with every step justified, and settle a claim about a small finite set by checking every case in it.
What a learner can do afterwards
- Prove that two arbitrary odd integers have an even sum by writing them as 2n + 1 and 2m + 1
- Prove a claim about the integers 1 to 5 by checking every case, and explain complete coverage in a case split
- Explain why three confirming examples alone do not prove a claim for all integers
1 · Read
Deduction uses stated assumptions, definitions and proved results, with a reason for each step. An even integer is twice an integer; an odd integer is 2n + 1 for some integer n. For integers n and m, (2n + 1) + (2m + 1) = 2n + 2m + 2 = 2(n + m + 1). The bracket is an integer, so the sum is even.
The two odd integers may differ, so n and m must be chosen independently. Using (2n + 1) + (2n + 1) covers equal odd integers only. To list positive odd integers, use n = 0, 1, 2, and so on. The values are 1, 3, 5, and so on. The rth positive odd integer uses n = r - 1.
Exhaustion checks every case in a stated finite domain. The notation n^2 means n times n. To prove n^2 + 3n is even for n in {1, 2, 3, 4, 5}, calculate each value: 4, 10, 18, 28 and 40. Each is even. List the allowed inputs and verify each calculation. A failed case disproves the claim. Inputs outside the stated domain are not required.
Three confirming integer checks alone do not prove a claim for all integers. Other inputs remain unchecked. A proof needs an argument covering every allowed input. One counterexample, an allowed input where the claim fails, disproves a claim about every input. To find one, calculate another case and compare the result with the claim.
A case split must cover the whole domain and prove the claim in every group. Groups may overlap. General cases can cover infinitely many inputs. For any integer n, n^2 + n = n(n + 1). If n is even, n is an even factor. If n is odd, n + 1 is even. These cases cover every integer, so the product is always even.
A proof needs correct calculations, even when an incorrect result happens to fit the claim. Check a factorisation by expanding it. For an inequality, calculate and compare both sides at each allowed input. The sign <= means less than or equal to, so equality passes that test. Assuming the conclusion and repeating it is circular reasoning; it does not prove the claim.
Justify each deductive step. Exhaustion verifies every allowed case. Confirming examples alone do not prove an all-integer claim, but one counterexample disproves it.
Original lesson and practice questions written for this dataset.
Original readings, questions and flashcards written for this dataset. Mathematical ideas and task structure were studied using OpenStax Contemporary Mathematics and WeBWorK records.
More to read
Checking a deductive argument
A proof begins with assumptions, definitions or facts already established. Each new statement must follow from them by a justified step. Check the calculation as well as the conclusion it is meant to support.
Suppose two odd integers are written as 2n + 1 and 2m + 1. The parameters n and m are integers and can be chosen independently. Adding and factoring gives 2(n + m + 1). The bracket is an integer, which makes the sum twice an integer and therefore even.
Using one parameter twice would represent only equal odd integers. That calculation may be correct, but its starting point does not cover every pair. A proof needs both correct steps and a starting point broad enough for its claim.
Do not begin by assuming the conclusion you are supposed to prove. Repeating that assumption gives a circular argument, not a reason the claim must hold.
Matching checks to a finite claim
Write down the domain before checking cases. A claim about the integers 1 to 5 has five allowed inputs. Verify the claim at each one. If every calculation is correct and every case passes, exhaustion proves that finite claim.
An omitted input leaves a gap. An input outside the stated domain is not required. A failed allowed case disproves the claim, even when every other case passes.
For an inequality, work out both sides before comparing them. The sign <= includes equality. For example, 9 <= 9 is true, while 9 < 9 is false.
The calculations themselves must also be justified. An incorrect value does not become acceptable because it happens to have the expected parity. Repair the calculation, then test the claim using its actual value.
Individual checks and general cases
Checked groups must together cover every allowed input. They may overlap: verifying the same input twice is unnecessary, but it does not leave a missing case.
A general case can cover infinitely many inputs. Every integer is even or odd. In the product n(n + 1), an even n supplies an even factor. When n is odd, n + 1 supplies an even factor. Together these two arguments prove that the product is even for every integer.
Those are two general cases, not two numerical examples. A finite list of successful substitutions alone cannot establish a claim for all integers.
A counterexample works differently. It is an allowed input where the claim fails. One such input disproves a statement claiming that every allowed input works. Show the calculation and explain why its result fails the stated condition.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Optional connections
Where this leads
Jobs that lean on this skill. Follow one to see everything it is built on.
18 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.