Structure of proof and proof by exhaustion

Structure of proof and proof by exhaustion Test

Spec 1.1–2 · Edexcel International A Level Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel International A Level Maths

Structure of proof and proof by exhaustion

Total 27 marks

Name

Class

Date

  1. 1
    A statement S is made: for every integer nn with 1≤n≤51\le n\le5, the value of n2+nn^2+n is even.
    (a)
    Which of the following is needed for a proof by exhaustion of S?
    [1 mark]
    • AShowing that S is true for n=3n=3 only
    • BShowing that S is true for each of n=1,2,3,4,5n=1,2,3,4,5
    • CFinding one value of nn for which S is true
    • DShowing that S is true for n=1n=1 and n=5n=5, and assuming the values in between must also work
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Find the value of n2+nn^2+n when n=4n=4.
    [1 mark]
    • A1616
    • B1212
    • C2525
    • D2020
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Prove that S is true by exhaustion.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: evaluates n2+nn^2+n for all five values n=1,2,3,4,5n=1,2,3,4,5, giving 2,6,12,20,302,6,12,20,30
    A1: all five values are even, so S is true for every
    nn in the range
    Accept:
    n(n+1)n(n+1) evaluated for each nn
    Do not accept: checking only some of the values

    Total for question 1: 4 marks

  2. 2
    xx and yy are odd positive integers, each less than 7.
    (a)
    How many different ordered pairs (x,y)(x,y) are possible?
    [1 mark]
    • A33
    • B66
    • C99
    • D2727
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Which of the following is a possible value of x+yx+y?
    [1 mark]
    • A1010
    • B77
    • C1212
    • D99
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Prove that x+yx+y is divisible by 22 for every possible pair.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: lists every possible value of xx and yy (1,3,51,3,5) and all the sums: 2,4,6,8,102,4,6,8,10
    A1: each sum is divisible by 2, so the statement is true in every case

    Accept: a table of all nine ordered pairs, or the six unordered pairs

    Do not accept: checking only some pairs

    Total for question 2: 4 marks

  3. 3
    Let f(n)=n3−nf(n)=n^3-n, where nn is an integer.
    (a)
    Use proof by exhaustion to show that f(n)f(n) is divisible by 66 for every integer nn with 2≤n≤62\le n\le6.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: evaluates f(n)=n3−nf(n)=n^3-n for each of n=2,3,4,5,6n=2,3,4,5,6
    A1:
    6, 24, 60, 120, 2106,\ 24,\ 60,\ 120,\ 210 all correct
    B1: each is divisible by 6 (quotients
    1,4,10,20,351,4,10,20,35) and a conclusion that the statement is true in every case
    Accept:
    n(n−1)(n+1)n(n-1)(n+1) used to find each value
    (b)
    A student claims that f(n)f(n) is divisible by 1212 for every integer nn with 2≤n≤62\le n\le6. Test this claim, and explain what your result shows about proof by exhaustion.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: checks the values f(2)=6, f(3)=24, f(4)=60, f(5)=120, f(6)=210f(2)=6,\ f(3)=24,\ f(4)=60,\ f(5)=120,\ f(6)=210 for divisibility by 12
    A1: identifies a failing case:
    f(2)=6f(2)=6 or f(6)=210f(6)=210 is not divisible by 12
    B1: the claim is false

    B1: proof by exhaustion needs the statement to hold in every case, so one failing case is enough to show a claim false

    Accept: follow-through from (a)

    Total for question 3: 7 marks

  4. 4
    Maya tests two statements about integers by checking every case. A calculator may be used.
    (a)
    Statement 1: for every odd integer nn with 3≤n≤93\le n\le9, n2−1n^2-1 is divisible by 88. (i) Use proof by exhaustion to prove Statement 1. (ii) Explain why this does not prove that n2−1n^2-1 is divisible by 88 for every odd integer nn.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) lists all four cases n=3,5,7,9n=3,5,7,9
    A1: (i)
    n2−1=8, 24, 48, 80n^2-1=8,\ 24,\ 48,\ 80
    A1: (i) each is a multiple of 8 (
    8×1, 8×3, 8×6, 8×108\times1,\ 8\times3,\ 8\times6,\ 8\times10)
    B1: (i) conclusion that the statement is true in every case

    B1: (ii) proof by exhaustion covers only the finite list of cases checked

    B1: (ii) there are infinitely many odd integers, so values such as
    n=11n=11 have not been checked
    (b)
    Statement 2: n2+n+11n^2+n+11 is prime for every integer nn with 0≤n≤100\le n\le10. Use proof by exhaustion to determine whether Statement 2 is true or false. Justify your answer fully.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: evaluates n2+n+11n^2+n+11 for each of n=0,1,…,10n=0,1,\ldots,10
    A1:
    11, 13, 17, 23, 31, 41, 53, 67, 83, 101, 12111,\ 13,\ 17,\ 23,\ 31,\ 41,\ 53,\ 67,\ 83,\ 101,\ 121
    B1: the values for
    n=0n=0 to 99 are all prime, with a reason for the larger ones (e.g. 101101 is not divisible by 2,3,52,3,5 or 77)
    M1: identifies that
    n=10n=10 gives 121121
    A1:
    121=112121=11^2, so it is not prime
    B1: the statement is false, because it fails for
    n=10n=10
    Accept:
    121=11×11121=11\times11

    Total for question 4: 12 marks

End of questions

Subtopic tests