1 Proof — coverage pack

1 specification leaves · notes, questions, answers and worked methods

1.1 · Understand and use the structure of mathematical proof, from assumptions through logical steps to a conclusion; use proof by deduction, exhaustion, disproof by counter example, and contradiction (irrationality of √2, infinity of primes).

A proof begins with stated assumptions, uses valid implications at every step and ends with a conclusion that matches the claim.
Choose the proof form deliberately: deduction for a general algebraic chain, exhaustion for finitely many cases, a counterexample to disprove a universal claim, or contradiction by assuming the opposite.
In the classic contradiction for $\sqrt2$ , writing $\sqrt2=a/b$ in lowest terms leads to both $a$ and $b$ being even, contradicting the lowest-terms assumption.
Checking several examples is not a proof of a universal statement; in contradiction proofs, also make clear exactly why the derived result conflicts with the assumption.

1. Disprove the claim that $n^2+n+41$ is prime for every non-negative integer $n$ .[2 marks]
Answer
- At $n=40$ , the expression equals $1681=41^2$ , which is not prime.
Method: A single counterexample defeats a universal claim. Taking $n=40$ gives $40^2+40+41=1681=41\times41$ , a composite number. Therefore the claim is false.

1. Prove by exhaustion that $n^2+n+2$ is even whenever $n$ is an integer.[4 marks]
Answer
- The expression is even in both the even and odd cases for $n$ .
Method: Every integer is even or odd. If $n=2k$ , then $n^2+n+2=4k^2+2k+2=2(2k^2+k+1)$ . If $n=2k+1$ , then $n^2+n+2=4k^2+6k+4=2(2k^2+3k+2)$ . Both forms are divisible by $2$ , so the result holds for every integer $n$ .

1. Suppose someone lists all primes as $p_1,p_2,\ldots,p_k$ . Construct an integer from this list and use contradiction to prove that the list cannot be complete.[5 marks]
Answer
- $N=p_1p_2\cdots p_k+1$ leads to a prime not on the alleged complete list.
Method: Assume for contradiction that the finite list contains every prime and form $N=p_1p_2\cdots p_k+1$ . Dividing $N$ by any listed prime $p_i$ leaves remainder $1$ , so none of the listed primes divides $N$ . Yet $N>1$ , so $N$ is prime or has a prime factor. That prime factor is absent from the list, contradicting its completeness. Hence there are infinitely many primes.