Proof by deduction, exhaustion and counter-example

Proof by deduction, exhaustion and counter-example Test

Spec 1.1 · Edexcel 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 A-Level Maths

Proof by deduction, exhaustion and counter-example

Total 27 marks

Name

Class

Date

  1. 1
    A student claims that n2+n+41n^2+n+41 is a prime number for every positive integer nn.
    (a)
    Which value of nn is a counter-example to the claim?
    [1 mark]
    • An=2n=2
    • Bn=5n=5
    • Cn=40n=40
    • Dn=10n=10
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    The student checks n=1,2,3,…,10n=1,2,3,\ldots,10 and finds that every value gives a prime. Which statement is correct?
    [1 mark]
    • AThis proves the claim, because ten cases is enough.
    • BThis is not a proof, because a finite number of cases does not cover every positive integer.
    • CThis proves the claim by exhaustion.
    • DThis disproves the claim.
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Show that the claim is false for n=41n=41, and state what type of proof this is.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: 412+41+41=41(41+1+1)=41×4341^2+41+41=41(41+1+1)=41\times43 (or =1763=41×43=1763=41\times43), so it is not prime
    B1: disproof by counter-example (one case that fails is enough)

    Accept: any correct factorisation of 1763

    Do not accept: 'proof by exhaustion'

    Total for question 1: 4 marks

  2. 2
    The function f(n)=n2−6n+10f(n)=n^2-6n+10 is defined for all real nn.
    (a)
    Which is the completed-square form of f(n)f(n)?
    [1 mark]
    • A(n−3)2+1(n-3)^2+1
    • B(n−6)2+10(n-6)^2+10
    • C(n−3)2+19(n-3)^2+19
    • D(n+3)2+1(n+3)^2+1
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    What is the minimum value of f(n)f(n) for real nn?
    [1 mark]
    • A00
    • B33
    • C1010
    • D11
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Hence prove that n2−6n+10n^2-6n+10 is positive for all real nn.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: n2−6n+10=(n−3)2+1n^2-6n+10=(n-3)^2+1 and (n−3)2⩾0(n-3)^2\geqslant0 for all real nn
    A1: so
    f(n)⩾1>0f(n)\geqslant1>0 for all real nn, hence always positive
    Accept:
    f(n)⩾1f(n)\geqslant1 so positive
    Do not accept: substituting some values of
    nn

    Total for question 2: 4 marks

  3. 3
    Two consecutive integers are nn and n+1n+1, where nn is an integer.
    (a)
    Prove that the sum of the squares of the two integers is always odd.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: n2+(n+1)2=n2+n2+2n+1n^2+(n+1)^2=n^2+n^2+2n+1
    A1:
    =2n2+2n+1=2(n2+n)+1=2n^2+2n+1=2(n^2+n)+1
    B1:
    n2+nn^2+n is an integer, so 2(n2+n)2(n^2+n) is even and the sum is odd
    Do not accept: testing numerical examples only
    (b)
    Prove that the sum of the squares of the two integers is always 1 more than a multiple of 4.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: sum −1=2n2+2n=2n(n+1)-1=2n^2+2n=2n(n+1)
    B1:
    n(n+1)n(n+1) is a product of consecutive integers, so one factor is even and n(n+1)n(n+1) is even
    M1:
    n(n+1)=2kn(n+1)=2k for an integer kk, so sum −1=4k-1=4k
    A1: sum
    =4k+1=4k+1 for every integer nn, which is 1 more than a multiple of 4
    Accept: considering
    nn even and nn odd separately

    Total for question 3: 7 marks

  4. 4
    Consider the statement: for every prime number p>3p>3, p2−1p^2-1 is a multiple of 24.
    (a)
    Prove by exhaustion that the statement is true for all primes pp with 3<p<253<p<25.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: the primes are 5,7,11,13,17,19,235,7,11,13,17,19,23 (all seven, and no others)
    M1: calculates
    p2−1p^2-1 for each
    A1:
    24, 48, 120, 168, 288, 360, 52824,\ 48,\ 120,\ 168,\ 288,\ 360,\ 528 (all correct)
    M1: shows each is a multiple of 24

    A1:
    24×1, 24×2, 24×5, 24×7, 24×12, 24×15, 24×2224\times1,\ 24\times2,\ 24\times5,\ 24\times7,\ 24\times12,\ 24\times15,\ 24\times22
    R1: all cases checked, so the statement is true for primes with
    3<p<253<p<25
    Accept: factorised form
    (p−1)(p+1)(p-1)(p+1) for each case
    (b)
    Prove by deduction that the statement is true for every prime p>3p>3.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: p2−1=(p−1)(p+1)p^2-1=(p-1)(p+1)
    B1:
    pp is odd, so p−1p-1 and p+1p+1 are consecutive even numbers
    M1: one of two consecutive even numbers is a multiple of 4, so the product is a multiple of
    2×4=82\times4=8
    B1:
    pp is not a multiple of 3, so p−1p-1 or p+1p+1 is the multiple of 3 among p−1, p, p+1p-1,\ p,\ p+1
    M1: the product is a multiple of both 8 and 3, which have no common factor, so a multiple of 24

    A1: conclusion that
    p2−1p^2-1 is a multiple of 24 for every prime p>3p>3
    Accept: writing
    p=6k±1p=6k\pm1 and expanding to get p2−1=12k(3k±1)p^2-1=12k(3k\pm1) with k(3k±1)k(3k\pm1) even

    Total for question 4: 12 marks

End of questions

Subtopic tests