TMUA Paper 2: Mathematical proof, set 1

• Answer all questions. No calculator.
• Each question has exactly one correct answer.

1. 11 mark

   A student wants to prove: 'If n is an even integer, then n^2 is divisible by 4.' Which of the following is a valid direct proof?

   1. A Since n is even, write n = 2k + 1 for some integer k. Then n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1, so n^2 is divisible by 4.
   2. B Since n is even, write n = 2k for some integer k. Then n^2 = (2k)^2 = 4k^2, which is divisible by 4.
   3. C Since n is even, write n = 2k for some integer k. Then n^2 = 2k^2, which is divisible by 4 because 2k^2 is always even.
   4. D Since n is even, n^2 is even (because even x even = even), and every even number is divisible by 4, so n^2 is divisible by 4.
2. 21 mark

   A student wants to prove: 'If m and n are both even integers, then mn is divisible by 4.' Which of the following is a valid direct proof?

   1. A Since m and n are even, write m = 2j and n = 2k for integers j and k. Then mn = 2jk, which is divisible by 4 because jk is an integer.
   2. B Since m and n are even, write m = 2k and n = 2k for the same integer k. Then mn = 4k^2, which is divisible by 4.
   3. C Since m and n are even, m + n is also even. As mn and m + n are both expressions in even numbers, mn must therefore also be divisible by 4.
   4. D Since m and n are even, write m = 2j and n = 2k for integers j and k. Then mn = (2j)(2k) = 4jk, so mn is divisible by 4.
3. 31 mark

   A student wants to prove: 'n^2 + n is even for every integer n.' Which of the following is a valid proof by cases?

   1. A Case n even: write n = 2k, so n^2 + n = 4k^2 + 2k = 2(2k^2 + k), which is even. Case n odd: write n = 2k + 1, so n^2 + n = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1), which is even. So n^2 + n is even for every integer n.
   2. B Case n even: write n = 2k, so n^2 + n = 4k^2 + 2k = 2(2k^2 + k), which is even. This algebraic form does not depend on which case was chosen, so testing the even case alone is enough, and n^2 + n is even for every integer n.
   3. C Case n even: write n = 2k, so n^2 + n = 4k^2 + 2k = 2(2k^2 + k), which is even. Case n odd: write n = 2k (the same form used for the even case), so n^2 + n = 2(2k^2 + k) again, which is even, so n^2 + n is even for every integer n.
   4. D Case n even: write n = 2k, so n^2 + n = 2(2k^2 + k), even. Case n odd: write n = 2k + 1, so n^2 + n = 2(2k^2 + 3k + 1), even. Since both cases give an expression of the form 2 times an integer, n itself must always be even.
4. 41 mark

   A student wants to prove: 'n^3 - n is divisible by 3 for every integer n.' Which of the following is a valid proof by cases?

   1. A Split into cases n even and n odd. Case n even: n^3 - n = 8k^3 - 2k = 2(4k^3 - k), even. Case n odd: n^3 - n = 8k^3 + 12k^2 + 4k = 2(4k^3 + 6k^2 + 2k), even. Since both cases give an even result, n^3 - n is divisible by 3 for every integer n.
   2. B Split into cases n = 3k, n = 3k + 1 and n = 3k + 2 for integer k. Case n = 3k: n^3 - n = 27k^3 - 3k = 3(9k^3 - k), divisible by 3. The same method applies to the other two residues, so checking this one case is enough, and n^3 - n is divisible by 3 for every integer n.
   3. C Split into cases n = 3k, n = 3k + 1 and n = 3k + 2 for integer k. n^3 - n works out to 3(9k^3 - k), 3(9k^3 + 9k^2 + 2k) and 3(9k^3 + 18k^2 + 11k + 2) respectively, all multiples of 3. So n^3 - n is divisible by 3 for every integer n.
   4. D Split into cases n = 3k, n = 3k + 1 and n = 3k + 2 for integer k. In the case n = 3k + 2, n^3 - n works out to 3(9k^3 + 18k^2 + 11k + 2); since 11k need not itself be a multiple of 3, this case does not actually give a multiple of 3, so the claim fails for n = 3k + 2.
5. 51 mark

   In a proof by contradiction that sqrt(2) is irrational, which is the correct starting assumption?

   1. A Assume sqrt(2) is irrational, and derive a contradiction from that.
   2. B Assume sqrt(2) is rational, and show this leads to a contradiction.
   3. C Assume sqrt(2) is not equal to any integer, and show this is impossible.
   4. D Assume some integer a satisfies a^2 = 2, and show no such integer exists.
6. 61 mark

   A student wants to prove: 'If r is rational and x is irrational, then r + x is irrational.' Which of the following is a valid proof by contradiction?

   1. A Assume, for contradiction, that r + x is rational. Since r is also rational, x = (r + x) - r is the difference of two rational numbers, which is rational. This contradicts the given fact that x is irrational, so the assumption is false and r + x must be irrational.
   2. B Assume, for contradiction, that r + x is irrational. Since r is rational, this is already what we wanted to show, so the proof is complete.
   3. C Assume, for contradiction, that r + x is rational. Since x is irrational, r = (r + x) - x is the difference of a rational number and an irrational number, which must be irrational. This contradicts r being rational, so r + x is irrational.
   4. D Assume, for contradiction, that r + x is rational, equal to p/q. Since r is rational, equal to a/b, x = p/q - a/b = (pb - qa)/(qb). Since p, q, a and b are all integers, x is expressed as a fraction of integers, so x is irrational, giving the required contradiction.
7. 71 mark

   A student claims: 'For every positive integer n, n^2 + n + 41 is prime.' Which of the following correctly disproves this claim?

   1. A n = 1: 1^2 + 1 + 41 = 43, which is prime, so n = 1 disproves the claim.
   2. B n = 2: 2^2 + 2 + 41 = 47, which is not divisible by 2, so it is not prime, so n = 2 disproves the claim.
   3. C n = 0: 0^2 + 0 + 41 = 41, which is prime, so n = 0 disproves the claim.
   4. D n = 40: 40^2 + 40 + 41 = 1681 = 41 x 41, which is not prime, so n = 40 disproves the claim.
8. 81 mark

   A student claims: 'If a and b are irrational numbers, then a + b is always irrational.' Which of the following correctly disproves this claim?

   1. A a = sqrt(2), b = sqrt(3). Then a + b = sqrt(2) + sqrt(3), which is irrational, so this disproves the claim.
   2. B a = sqrt(2), b = sqrt(2). Both are irrational, and a + b = 2 sqrt(2), which is rational since it is 2 times a square root, so this disproves the claim.
   3. C a = sqrt(2), b = -sqrt(2). Both are irrational, and a + b = sqrt(2) + (-sqrt(2)) = 0, which is rational, so this disproves the claim.
   4. D a = 0.5, b = sqrt(2). Both are irrational, since 0.5 is a decimal, and a + b = 0.5 + sqrt(2), which is irrational, so this disproves the claim.
9. 91 mark

   You are told: 'If a shape is a square, then it is a rectangle' and 'This shape is not a rectangle.' Which of the following can be validly deduced?

   1. A The shape is not a square.
   2. B The shape is a square.
   3. C The shape is a rectangle.
   4. D Nothing can be deduced, because the statements are about different things.
10. 101 mark

    By evaluating 1, 1 + 3, 1 + 3 + 5, 1 + 3 + 5 + 7 (giving 1, 4, 9, 16), a student conjectures a formula for the sum of the first n odd positive integers. Which of the following gives both the correct conjecture and a valid justification for every n, not just the four cases checked?

    1. A Conjecture: the sum of the first n odd positive integers is n^2. Justification: the values 1, 4, 9, 16 are 1^2, 2^2, 3^2, 4^2; since the pattern holds for these four checked cases, and no counterexample has been found, it must hold for every n.
    2. B Conjecture: the sum of the first n odd positive integers is n^2. Justification: the odd integers form an arithmetic series, and summing the series algebraically proves n^2 in general.
    3. C Conjecture: the sum of the first n odd positive integers is 2n - 1. Justification: since the nth odd number itself is 2n - 1, and this term is the largest one added, the sum up to the nth term must also equal 2n - 1.
    4. D Conjecture: the sum of the first n odd positive integers is n(n + 1)/2, the familiar triangular-number formula. Justification: substituting n = 1, 2, 3, 4 into n(n + 1)/2 matches the observed sums 1, 4, 9, 16, so the formula should hold in general.
11. 111 mark

    A student is asked to prove: 'If n is a multiple of 6, then n is a multiple of 3.' The proof has been written as four separate lines, given here in a scrambled order:

    W: So n = 6k = 3(2k).

    X: Suppose n is a multiple of 6, so n = 6k for some integer k.

    Y: Since 2k is an integer, n is 3 times an integer, so n is a multiple of 3.

    Z: Therefore, if n is a multiple of 6, then n is a multiple of 3, as required.

    Which order of these four lines gives a valid direct proof?

    1. A W, X, Y, Z
    2. B X, Y, W, Z
    3. C X, W, Z, Y
    4. D X, W, Y, Z
12. 121 mark

    Suppose n is a positive integer for which n^2 + 1 is divisible by 5. Which of the following must be true?

    1. A n must be even.
    2. B n must be a multiple of 5.
    3. C n leaves a remainder of 2 or 3 when divided by 5.
    4. D n leaves a remainder of 1 or 4 when divided by 5.

Worked solutions

Every question below carries the reasoning, not just the answer. The official material for this test publishes a correct option letter and nothing else.

1. Question 1Answer: B

   1. To prove a statement about every even integer n, write n in the general form n = 2k, where k is an integer.
   2. Then n^2 = (2k)^2 = 4k^2.
   3. Since k is an integer, k^2 is also an integer, so 4k^2 is 4 multiplied by an integer, which is exactly what it means for a number to be divisible by 4.
   4. This chain, n even, so n = 2k, so n^2 = 4k^2, so n^2 is divisible by 4, is a complete direct deductive proof, so the answer is B.
   • Why not A: Uses the algebraic form of an odd integer, 2k + 1, instead of an even integer, 2k, so the working actually describes an odd number rather than the even n given in the statement.
   • Why not C: Squares 2k incorrectly as 2k^2 rather than 4k^2, an arithmetic slip that drops a factor of 2 and loses exactly the fact the proof needs.
   • Why not D: Asserts that every even number is divisible by 4 without justification; this is false in general (6 is even but not divisible by 4), so the deduction is invalid even though the conclusion happens to hold for n^2 here.

2. Question 2Answer: D

   1. To prove a statement about two even integers m and n, represent them independently: m = 2j and n = 2k for integers j and k, which need not be equal.
   2. Compute the product: mn = (2j)(2k) = 4jk.
   3. Since j and k are integers, jk is also an integer, so 4jk is 4 multiplied by an integer.
   4. This shows mn is divisible by 4 directly from the definitions of m and n, so the answer is D.
   • Why not A: Computes (2j)(2k) as 2jk instead of 4jk, an arithmetic slip that drops a factor of 2 and would, if left uncorrected, only show mn is divisible by 2.
   • Why not B: Silently sets m and n equal to the same variable k, effectively assuming m = n; the statement gives two independent even integers, so the proof needs two independent letters, j and k.
   • Why not C: Confuses the sum m + n, which is even, with the product mn, and treats 'even' as equivalent to 'divisible by 4'; neither substitution is justified, so this does not establish anything about mn.

3. Question 3Answer: A

   1. Every integer n is either even or odd, so a proof by cases can split on this and cover every possibility.
   2. Case n even: write n = 2k, giving n^2 + n = 4k^2 + 2k = 2(2k^2 + k), an even number since 2k^2 + k is an integer.
   3. Case n odd: write n = 2k + 1, giving n^2 + n = (2k+1)^2 + (2k+1) = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1), also even.
   4. Since these two cases are exhaustive and both give an even value, n^2 + n is even for every integer n, matching option A.
   • Why not B: Checks only the even case and then falsely claims the algebraic form does not depend on which case was chosen, so testing one case is enough; a proof by cases must actually examine every case, and this never tests n odd at all.
   • Why not C: Represents the 'odd' case using n = 2k, the algebraic form for an even integer, so the odd case is never actually tested; both cases secretly test the same thing.
   • Why not D: Correctly shows n^2 + n is even in both cases, but then misreads this as showing n itself is always even, confusing the quantity that was proved even (n^2 + n) with the variable n.

4. Question 4Answer: C

   1. To show 3 divides n^3 - n for every integer n, split by remainder on division by 3, giving three cases: n = 3k, n = 3k + 1 and n = 3k + 2.
   2. Expanding each case shows n^3 - n equals 3 multiplied by an integer expression in every case: 3(9k^3 - k), 3(9k^3 + 9k^2 + 2k) and 3(9k^3 + 18k^2 + 11k + 2).
   3. Every integer n falls into exactly one of these three residue classes, so the three cases are exhaustive.
   4. Since all three give a multiple of 3, n^3 - n is divisible by 3 for every integer n, which is option C.
   • Why not A: Splits on parity (even and odd) and correctly shows n^3 - n is always even in both cases, but this only establishes divisibility by 2, not by 3; the case split does not match the claim being proved, and being even does not imply being divisible by 3.
   • Why not B: Checks only the case n = 3k and then wrongly asserts that the same method automatically applies to n = 3k + 1 and n = 3k + 2; each residue gives a different algebraic expression, so a proof by cases must actually compute and check every one rather than assume the pattern continues.
   • Why not D: Correctly reaches 3(9k^3 + 18k^2 + 11k + 2), but then wrongly worries that 9k^3 + 18k^2 + 11k + 2 must itself be divisible by 3 for the whole expression to be divisible by 3; it need not be, since 9k^3 + 18k^2 + 11k + 2 is simply some integer whenever k is, and 3 times any integer is divisible by 3.

5. Question 5Answer: B

   1. A proof by contradiction begins by assuming the negation of the statement to be proved.
   2. The statement here is 'sqrt(2) is irrational'; its negation is 'sqrt(2) is rational', that is, sqrt(2) can be written as a/b for integers a and b with no common factor.
   3. From this assumption a contradiction is derived (a and b both turn out to be even, contradicting 'no common factor'), which shows the assumption was false.
   4. The correct starting assumption is therefore option B.
   • Why not A: Assumes the very statement to be proved, that sqrt(2) is irrational, rather than its negation; a proof by contradiction must start from the opposite of the target statement.
   • Why not C: Is not the negation of 'sqrt(2) is irrational'. The negation of 'irrational' is 'rational', that is, expressible as a fraction of integers, not 'not equal to any integer'; every integer is already rational, so this framing misses most of the numbers that need ruling out.
   • Why not D: Only rules out sqrt(2) being an integer, a much weaker claim than sqrt(2) being irrational; it leaves open, for example, sqrt(2) = 3/2, so this does not address the actual statement.

6. Question 6Answer: A

   1. Assume, for contradiction, that r + x is rational, the negation of the statement to be proved.
   2. Since r is rational, x can be written as (r + x) - r, the difference of two rational numbers.
   3. A difference of two rational numbers is always rational: if r + x = p/q and r = a/b, then x = (pb - qa)/(qb), a ratio of integers.
   4. So x would have to be rational, contradicting the given fact that x is irrational; the assumption is therefore false, and r + x is irrational, matching option A.
   • Why not B: Assumes the conclusion itself, that r + x is irrational, rather than its negation; a contradiction proof must start from 'r + x is rational' and derive an impossibility, not restate the target.
   • Why not C: Relies on 'a rational number minus an irrational number is irrational' as an already-known fact, but that is essentially a restatement of the result being proved, with r and x relabelled, so the argument assumes what it needs to show rather than working from the definitions.
   • Why not D: Correctly derives that x = (pb - qa)/(qb), a ratio of integers, but then mislabels this as 'irrational'; a ratio of integers is, by definition, rational, so the arithmetic is right but the stated conclusion is the opposite of what the working shows.

7. Question 7Answer: D

   1. To disprove a universal claim, 'for every positive integer n, ... is prime', it is enough to exhibit one positive integer n for which the expression is not prime.
   2. Testing n = 40: 40^2 + 40 + 41 = 1600 + 40 + 41 = 1681.
   3. 1681 = 41 x 41, so 1681 is composite, not prime.
   4. n = 40 is a positive integer for which the expression fails to be prime, so it is a valid counterexample, and the answer is D.
   • Why not A: n = 1 gives 43, which is prime; a counterexample to 'the expression is always prime' must be a value where the expression is NOT prime, so a value that keeps it prime supports the claim rather than disproving it.
   • Why not B: Argues 47 is not prime because it is not divisible by 2; not being divisible by 2 only rules out one specific factor and does not establish that a number is composite. In fact 47 is itself prime, so this does not disprove the claim at all.
   • Why not C: Uses n = 0, but the claim is stated only for positive integers, so n = 0 is outside its domain; and 41 is prime in any case, so neither the domain restriction nor the counterexample condition is satisfied.

8. Question 8Answer: C

   1. To disprove 'for all irrational a and b, a + b is irrational', it suffices to find one pair of irrational numbers whose sum is rational.
   2. Let a = sqrt(2) and b = -sqrt(2). Both are irrational, since sqrt(2) is irrational and the negative of an irrational number is irrational.
   3. Their sum is a + b = sqrt(2) + (-sqrt(2)) = 0.
   4. 0 is rational, since it equals 0/1, so this pair satisfies the hypothesis (both irrational) but violates the conclusion (sum irrational), giving a valid counterexample, matching option C.
   • Why not A: Produces sqrt(2) + sqrt(3), which is irrational; this is consistent with the claim rather than contradicting it, so it does not disprove anything. A counterexample must show the sum turning out rational.
   • Why not B: Claims 2 sqrt(2) is rational, but a nonzero rational multiple of an irrational number is always irrational; 2 sqrt(2) is irrational, so this pair does not actually give a rational sum and fails to disprove the claim.
   • Why not D: Treats 0.5 as irrational, but 0.5 = 1/2 is rational, since a terminating decimal is always a rational number; a is not irrational here, so this pair does not even satisfy the claim's hypothesis, and cannot be used to disprove it.

9. Question 9Answer: A

   1. The statement 'if a shape is a square, then it is a rectangle' has the form 'if A then B', with A = square and B = rectangle.
   2. We are also told the shape is not a rectangle, that is, 'not B' holds.
   3. A valid rule of deduction is that 'if A then B' together with 'not B' allows us to conclude 'not A': if the shape were a square, it would have to be a rectangle, but it is not, so it cannot be a square.
   4. Applying this, the shape is not a square, which is option A.
   • Why not B: Directly contradicts the correct deduction: from 'if A then B' and 'not B' we deduce 'not A' (not a square), not 'A' (a square).
   • Why not C: Contradicts the given premise outright; we were told the shape is not a rectangle, so concluding it is a rectangle ignores one of the two given facts.
   • Why not D: Misses that 'if A then B' together with 'not B' is exactly the pattern that licenses the deduction 'not A'; a valid conclusion is available here, it is simply not stated directly.

10. Question 10Answer: B

    1. Listing the sums 1, 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16 suggests the pattern 1^2, 2^2, 3^2, 4^2, leading to the conjecture that the sum of the first n odd positive integers is n^2.
    2. To justify this beyond four cases, note that the first n odd positive integers form an arithmetic sequence with first term 1, common difference 2, and nth term 2n - 1.
    3. The sum of an arithmetic series is (n/2)(first term + last term) = (n/2)(1 + (2n - 1)) = (n/2)(2n) = n^2.
    4. This algebraic argument proves the conjecture for every positive integer n, not just the four cases checked, matching option B.
    • Why not A: States the correct conjecture, n^2, but the justification only checks four small cases and then simply asserts the pattern 'must hold for every n' with no argument for why; agreement on finitely many cases suggests a conjecture but does not by itself justify it for all n.
    • Why not C: Confuses the nth odd number itself, 2n - 1, with the sum of the first n odd numbers, n^2; these are different quantities, and the sum is not equal to the last term added.
    • Why not D: Proposes n(n + 1)/2, the formula for the sum of the first n positive integers (1, 3, 6, 10, ...), which does not match the observed sums 1, 4, 9, 16; substituting n = 1, 2, 3, 4 into n(n + 1)/2 actually gives 1, 3, 6, 10, so the two sequences are being confused.

11. Question 11Answer: D

    1. A direct proof of an 'if... then...' statement should begin by assuming the hypothesis: line X, 'Suppose n is a multiple of 6, so n = 6k for some integer k.'
    2. The next step performs the algebra that follows from this assumption: line W, 'So n = 6k = 3(2k).'
    3. Then the reasoning explains why this form gives the desired property: line Y, 'Since 2k is an integer, n is 3 times an integer, so n is a multiple of 3.'
    4. Finally the overall conditional conclusion is stated: line Z, 'Therefore, if n is a multiple of 6, then n is a multiple of 3, as required', giving the order X, W, Y, Z, which is option D.
    • Why not A: Opens with W, 'n = 6k = 3(2k)', before the assumption in X has introduced k at all; the algebraic step must come after the assumption that defines k, not before it.
    • Why not B: States the conclusion in Y, 'n is a multiple of 3', immediately after the assumption in X, before the algebraic step in W that actually justifies it; the working must precede the claim it supports.
    • Why not C: Places the final conclusion in Z before the line in Y that explains why 3(2k) makes n a multiple of 3; the overall conclusion should come last, after every supporting step.

12. Question 12Answer: C

    1. Every integer n leaves a remainder of 0, 1, 2, 3 or 4 when divided by 5; checking each case in turn shows what n^2 + 1 leaves as a remainder.
    2. Remainder 0: n^2 leaves remainder 0, so n^2 + 1 leaves remainder 1. Remainder 1: n^2 leaves remainder 1, so n^2 + 1 leaves remainder 2. Remainder 4: n^2 = 16 leaves remainder 1, so n^2 + 1 leaves remainder 2.
    3. Remainder 2: n^2 = 4, so n^2 + 1 leaves remainder 0, divisible by 5. Remainder 3: n^2 = 9 leaves remainder 4, so n^2 + 1 leaves remainder 0, divisible by 5.
    4. So n^2 + 1 is divisible by 5 exactly when n leaves remainder 2 or 3 on division by 5, which is option C; checking every residue class systematically is needed here because no single small example settles the general claim.
    • Why not A: Checking a case such as n = 2 might suggest n must be even, but n = 3 also satisfies n^2 + 1 divisible by 5 (3^2 + 1 = 10) despite being odd; the condition depends on the remainder of n modulo 5, not on parity.
    • Why not B: Assumes that for n^2 + 1 to be divisible by 5, n itself must be a multiple of 5; but if n is a multiple of 5 then n^2 + 1 leaves remainder 1 (not 0) when divided by 5, so this is not merely unproven, it is false.
    • Why not D: Swaps the residues: n leaving remainder 1 or 4 gives n^2 + 1 leaving remainder 2 (mod 5), not remainder 0; these are exactly the residues for which the condition fails, not the ones for which it holds.