Practise › Questions › The structure of proof: deduction and exhaustion
The structure of proof: deduction and exhaustion questions
Checking a thousand examples proves nothing. A general argument can settle infinitely many cases in three lines. This lesson is about what a proof actually is, and about the two methods this course requires, deducing a result in general and checking a complete list of cases.
8 original questions · 26 marks · the the structure of proof: deduction and exhaustion notes · Proof
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Write down general algebraic forms for: an even number, an odd number, and a pair of consecutive odd numbers. In each case say what the letter stands for.
Worked answer
An even number is 2n and an odd number is 2n + 1, where n is an integer. Consecutive odd numbers are 2n + 1 and 2n + 3. B1 for 2n, B1 for 2n + 1, B1 for the consecutive odd pair. Declaring that n is an integer is part of the answer, because the letter is there precisely to stand for every integer at once.A student checks that a claim holds for n = 1 to n = 50 and writes “proved”. Explain why the work is not a proof, and name the kind of argument that would be.
Worked answer
Fifty checks are evidence, and evidence is not proof: case 51 could still fail. A proof must be a general argument that covers every case at once, by deduction from known facts, or by exhaustion when the cases form a complete finite list. B1 for why fifty checks are not a proof, B1 for naming a general deductive argument.Prove that n2 + 4n + 7 > 0 for all values of n.
Worked answer
Complete the square, giving n2 + 4n + 7 = (n + 2)2 + 3. A square is never negative, so (n + 2)2 ≥ 0 and therefore (n + 2)2 + 3 ≥ 3 > 0. M1 for completing the square, A1 for (n + 2)2 + 3, B1 for the non-negative square. Completing the square rewrites the expression so its sign becomes visible; that is the whole method. The sentence naming the square as non-negative carries a mark of its own, so the algebra alone is not the proof.Prove that the sum of any two consecutive odd numbers is divisible by 4.
Worked answer
Let the numbers be 2n + 1 and 2n + 3 for an integer n. Their sum is 4n + 4 = 4(n + 1), and n + 1 is an integer, so the sum is 4 times an integer. B1 for 2n + 1 and 2n + 3, M1 for forming the sum, A1 for 4(n + 1) with the conclusion. The final sentence matters: exhibiting the factor of 4 and saying the other factor is an integer is what “divisible by 4” means.Prove that the difference between the squares of any two consecutive odd numbers is divisible by 8.
Worked answer
Take the numbers as 2n + 1 and 2n + 3 for an integer n. Then (2n + 3)2 − (2n + 1)2 = (4n2 + 12n + 9) − (4n2 + 4n + 1) = 8n + 8 = 8(n + 1), which is 8 times an integer. B1 for the two forms, M1 for expanding and subtracting, A1 for 8n + 8, A1 for the conclusion. Expanding both squares fully before subtracting keeps the sign errors out, and the difference of two squares gives the same result in one line: (4n + 4)(2) = 8(n + 1). Testing 3 and 5 proves nothing on its own.Prove that every square number is either a multiple of 4 or one more than a multiple of 4.
Worked answer
Every integer is even or odd, so two cases cover everything. If k = 2n then k2 = 4n2, a multiple of 4. If k = 2n + 1 then k2 = 4n2 + 4n + 1 = 4(n2 + n) + 1, one more than a multiple of 4. B1 for splitting into even and odd, M1 for squaring each case, A1 for the even case, A1 for the odd case. This is proof by exhaustion over types rather than individual numbers: the two cases are exhaustive because every integer is one or the other.Given that p is a prime number with 5 < p < 20, prove by exhaustion that p2 − 1 is divisible by 24.
Worked answer
The complete list is 7, 11, 13, 17, 19. In turn, p2 − 1 gives 48, 120, 168, 288, 360, and dividing by 24 gives 2, 5, 7, 12, 15, all integers. Every case on the complete list has been checked, so the claim is proved. B1 for the complete list, M1 for computing p2 − 1, A1 for the five values, A1 for dividing by 24, B1 for the concluding statement. Listing the primes correctly is the first mark: miss one and the proof collapses.Explain why proof by exhaustion could not be used to prove that n2 + 4n + 7 > 0 for all integers n, even in principle.
Worked answer
Exhaustion needs a complete finite list of cases, and the integers go on for ever: however many are checked, infinitely many remain. B1 for exhaustion needing a finite list, B1 for the integers being infinite. A claim about all integers needs a general argument, so the deduction proof via the completed square is the only route.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise the structure of proof: deduction and exhaustion one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.